# turings machines and other machines?

Discussion in 'Computing and Networks' started by Mathematics!, May 14, 2012.

1. ### Mathematics! Thread Starter Senior Member

Jul 21, 2008
1,022
4
What I know is

Turings machines can recognize all phrase structure grammers (i.e all the chomsky hierarchy of grammers type 0,1,2,3 )

Turings machines have many different variations that all can be shown to be equivalent (i.e infinite tape , mulitape , multdimensional , and many other variations on the definitions of a turing machine )

What I am curious of is a few things

1) Turings machines reconginze all phrase structure grammers but is there grammers different from phrase structure grammers that turings machine cann't recongnize ?

2) If you define Turing machine with an infinite states / symbols on tape with a partial function that deals with these can this be show to be equivalent to the other turings machine. ( seems to me the term turing machines stand for the most general machines being analysised for theoritical or practical application)
But essentially question 2 asks does infinite turings machines = turing machines.... in all cases ,..i.e all orders of infinite.

3) Can all finite state machines (i.e the ones with input/output and the ones with just input aka. finite automata ) be modeled equivalently with a turing machines ( This seems trival for the finite automata ones since you just have to use the transistion function when constructing an equivalent turings machine but for the finite state machines that have output not sure yet)

4) same as 3 but for pushdown automata , linear bounded automata , and other special machines.... is it true that these would all be special cases of a type of turings machines. Thus the only real reason to have all these types of different machines is only in the easy of computing a certain type of thing since turing machines by definition would beable to do all the things done by any machine and then some. The only reason to use one type of machine/definition over the other is just in the easy of computing/constructing a particular problem at hand.

(i.e I believe that all these machines are just a special type of turings machine aka. just a subset of the most general turing machines to make life easier to work with/ model certain problems )

5) Church-Turing thesis states basically for any problem that can be solved with an "effective algorithm" there is a turings machine that can solve the problem. But I am really stuck on what effective algorithm means or is? Because I would think logically this would be to hard to even define precisely. In theory if one assumes that humans can only carry out effective algorithms (or problems that can be modeled with only finite effective algorithms ) then in theory it would be possible for another life form to program a computer to have the same capability of a human thus proving that in theory a computer could be made indistinguishable from a human (aka. turings test solved)

Note even if humans and computers can have the same capablitlies this does not imply that a human could ever create a computer to get to this level. And I believe it would take a different more intelligent life form aka. the cann't think out side the box theory. i.e humans I don't believe will ever create AI to learn exactly like a human it would take a 3rd party life form. This basically is the godel argument.

6)
Just an add on to counteract my bold statements above doesn't the ability for a human to solve the busy beaver problem prove that a human is different from what a turing machine can do? ( thus proving a human can compute more then effective algorithms and can be always made distinguishable from a turing machine/computer )

Last edited: May 14, 2012
2. ### Mathematics! Thread Starter Senior Member

Jul 21, 2008
1,022
4
well, I answered most of the questions except the question 5 and 6 issue yet.

Hypercomputation is probably one step more general then turings but ofcourse that is just definitional things... one could define a turings machine called hyper-turings instead to keep it in the same naming convention

But essentially the important part is how you define the machine and weather it is truely different in the since not equivalent to a turing machine. Because if it is equivalent then the system is essentially the same.

And essentially these Hypercomputation machines can compute the turing halting problem but they still fall to there own mathematically cooked up haltings problems. So in theory any machine is bounded loosely be something and this something may be the way to determine different machines

Last edited: May 15, 2012