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.
$\begingroup$
$\endgroup$
12
asked Nov 6, 2015 at 20:49
-
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$– vznNov 6, 2015 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 DeckerNov 6, 2015 at 21:23
-
$\begingroup$ @RickDecker could you please tell how that all languages would become recognizable ? $\endgroup$– advocateofnoneNov 6, 2015 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 DeckerNov 6, 2015 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 FilmusNov 6, 2015 at 22:20
|
Show 7 more comments
1 Answer
$\begingroup$
$\endgroup$
9
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.
-
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$ Nov 6, 2015 at 21:43
-
$\begingroup$ @RickDecker, good point -- thanks. Answer updated accordingly. $\endgroup$– D.W. ♦Nov 11, 2015 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$– abcNov 11, 2015 at 7:29
-
$\begingroup$ @ABD Explaining a bit informally, it's like the snapshot of the "state" the Turing machine is in. $\endgroup$ Apr 17, 2019 at 15:56
-
$\begingroup$ I am not convinced that this completely answers the question. The OP question had been based on an earlier question involving an infinitely long input tape. So an (extended) Turing Machine could have a finite number of control states, but over the range of possible inputs (finite or otherwise) and with the non-terminating computations the number of states could grow without bound. Thus when described formally one could describe this extended Machine as having an infinite state space. Some such machines will be isomorphic to a regular Turing Machine, some perhaps not. $\endgroup$ Jun 1, 2020 at 14:36