# Can a Turing machine have infinite states?

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.

• 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. – vzn Nov 6 '15 at 21:08
• 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. – Rick Decker Nov 6 '15 at 21:23
• @RickDecker could you please tell how that all languages would become recognizable ? – sashas Nov 6 '15 at 21:28
• 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. – Rick Decker Nov 6 '15 at 21:56
• @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. – Yuval Filmus Nov 6 '15 at 22:20