2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ see eg infinite state machines vs TMs / cstheory. basically one would have to define how the state table is built. then that would be an algorithm (nothing else is possible via church-turing thesis), and then this new construction would be TM equivalent also. however, there may be some literature relating to this eg via hypercomputation etc; may try to put together answer later. $\endgroup$ – vzn Nov 6 '15 at 21:08
  • 2
    $\begingroup$ Call the class of TMs with infinite states ITMs. With such machines, it's not hard to see that every language would be ITM-recognizable, meaning that you would lose the distinction that TMs provide between recognizable and non-recognizable languages. $\endgroup$ – Rick Decker Nov 6 '15 at 21:23
  • $\begingroup$ @RickDecker could you please tell how that all languages would become recognizable ? $\endgroup$ – sashas Nov 6 '15 at 21:28
  • 2
    $\begingroup$ I have no idea of how to do this algorithmically, but since the language exists, the DFA result mentioned shows that there must be a DFA-ish machine that recognizes it and hence there must be an ITM that does. The fact that we don't know what it is is immaterial here. $\endgroup$ – Rick Decker Nov 6 '15 at 21:56
  • 1
    $\begingroup$ @sasha I don't see the problem. Nobody said that the description of the ITM should be computable. If a real number is not computable, does it not exist? If you do insist on computability, you just get a glorified TM. $\endgroup$ – Yuval Filmus Nov 6 '15 at 22:20
10
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It seems that the OP was asking "Is it possible to construct machines like TMs, with the modification that they have infinitely many states?" and subsequently "what effect does this have on the languages accepted by such machines?" $\endgroup$ – Rick Decker Nov 6 '15 at 21:43
  • $\begingroup$ @RickDecker, good point -- thanks. Answer updated accordingly. $\endgroup$ – D.W. Nov 11 '15 at 1:14
  • $\begingroup$ @D.W. would you please explain what you mean with states ?? is it the steps performed to reach the halting status or the length that turing machine can operate on ? ...{en.wikipedia.org/wiki/Turing_machine#The_.22state.22} $\endgroup$ – ABD Nov 11 '15 at 7:29
  • $\begingroup$ @ABD Explaining a bit informally, it's like the snapshot of the "state" the Turing machine is in. $\endgroup$ – Reeshabh Ranjan Apr 17 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.