Does it make sense for a Turing machine to have infinite number of states ? I had previously asked a question Can Turing machines have infinite length input. From which I came to know about Type-2 Turing machines. If there can be infinite states, encoding of such a Turing machine would be infinite ( but again I am not sure if it make sense to encode a Turing machine with infinite states thus having an infinite description ). So it would make sense that if I have to give the encoding of such a Turing machines as input, I would give it as input to Type-2 Turing machines.
But is there any use of infinite states ( and what is there link to Type-2 Turing machines ? ) ? If I am not wrong there is no function which is uncomputable by normal Turing machine but computable by Turing machine with infinite states.
Asked By : sashas
Answered By : D.W.
No. The definition of Turing machines requires that the finite-state control unit have a finite number of states. It's not allowed to have an infinite number of states.
A machine that could have infinitely many states in its control could accept any language (unlike a Turing machine). However such a machine could not be implemented in practice. For these two reasons, it would not be a good model of the computational power of real computers.
In addition, once you allow an infinite-state automaton, there's no need to have any tape -- the tape doesn't add any computational power, because an infinite-state automaton can already do "everything". For these reasons, while it would be possible to construct machines that look like Turing machines but have infinite state, there would be little point: their power would be equivalent to an infinite-state automaton on their own, i.e., every language can be accepted by such a machine.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49163
0 comments:
Post a Comment
Let us know your responses and feedback