Consider a Turing Machine which (1) reads all its input and (2) accepts inputs arbitrarily large. Can we conclude that there must be a loop in the finite-state control as its inputs get larger?

  • 1
    $\begingroup$ If by loop you mean two moments in which the transition function gets evaluated at the same input, then yes. There are only finitely many states and possible symbols that can be written in the tape. If the input is longer than the product of the cardinalities of the set of states and the alphabet, then a repetition on the input to the transition function must occur, by the pigeonhole principle. $\endgroup$
    – plop
    Jul 31, 2020 at 2:31
  • $\begingroup$ @plop, I encourage you to write that as an answer so we can upvote it and accept it. We discourage writing answers to the question in the comments. Thank you! $\endgroup$
    – D.W.
    Oct 13, 2020 at 19:37
  • $\begingroup$ @plop: I will accept your comment as an answer. $\endgroup$
    – ShyPerson
    Oct 14, 2020 at 0:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.