Consider a turing machine with infinite states. This machine is identical to a regular machine. Only that number of states could be infinite. Does this machine has more computational power than a regular machine ?

If yes - Then show that a machine with infinite states can recognize languages that cannot be recognized with a machine that has a finite number of states... ( and how this doesnt contradict the church turing hypothesis)

If no - show how a machine with a finite number of states could imitate the operation of a machine with an infinite number of states..

The main thing to notice above is that the question is about recognizing a language and not deciding a language.

  • 1
    $\begingroup$ what i can think right now is that a turing machine with infinite states could simply recognize any language... as give any string in that language i move to an accept state and otherwise i move to a reject state... since number of states are infinite so this will work.. But whether a normal turing machine could recognize all languages is not clear to me...(again the question here asks about recognizability not decidability) $\endgroup$ Aug 24 '20 at 6:06
  • $\begingroup$ With some details (i.e. how do you arrive to the state which corresponds to the string), your reasoning is correct. About "normal turing machine could recognize all languages": check e.g. cc.gatech.edu/~rpeng/CS4510_F18/Nov12Reductions.pdf $\endgroup$
    – user114966
    Aug 24 '20 at 6:13

Any language can be recognized by a Turing machine with an infinite number of states. Let the state graph be an infinite trie; scan over the input from left to right once, and you end up at a unique state for each possible input string.

By contrast, if you are familiar with different cardinalities of infinite set, it is easy to see that there must be some language not accepted by any Turing machine with a finite number of states. There are uncountably many languages and only countably many finite Turing machines. This argument works for any method of describing languages using descriptions of finite size: no such method can give a description for every language.

The Church-Turing thesis, according to Wikipedia, is the statement that

a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

This does not contradict that a "Turing machine with infinite states" could recognize any language, because the phrase "Turing machine" in unqualified form always refers to a machine with a finite number of states.

The very fact that extending the Turing machine model to permit an infinite state set would allow it to recognize any language means that such a model is mathematically almost useless. Saying that a language is recognized (in linear time!) by a "Turing machine with infinite states" adds no information, because that is true of every language.

  • $\begingroup$ Hi @Aaron Rotenberg.. I see that your argument is correct.there is also one more part to the question which says that explain how this does not contradict church Turing thesis ...I don't get that ..the sipser book on theory of computation gives a very vague idea about church Turing thesis...in short why does this doesn't contradict church Turing hypothesis ...thanks $\endgroup$ Aug 27 '20 at 13:36
  • $\begingroup$ @RobinSuri See my edit to the answer. $\endgroup$ Aug 27 '20 at 19:00

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.