Consider a Turing Machine which (1) reads all its input and (2) accepts inputs arbitrarily large. Given the affirmative answer to the previous question that there must be a loop in the finite-state control as its inputs get larger, could we conclude that there may be more than one loop in such a machine? That is, there could be several loops, not just one?

  • 1
    $\begingroup$ What are your thoughts? We prefer questions that you are actively thinking about and where you can show us what progress you've made and what prevents you from answering it yourself. You might try working through some examples and try applying the reasoning in the answer to that question. It might also help to tell us the context in which you encountered this question or the motivation. $\endgroup$
    – D.W.
    Oct 13, 2020 at 19:37
  • $\begingroup$ @D.W.: Thanks very much for responding. My thoughts on this are that one can make an analogy to programming languages where there are clearly multiple loops in a program, and that therefore there should be multiple loops in the corresponding Turing Machine. The obstacle is that this doesn't really feel mathematically rigorous. My motivation is to generalize this question still further by reasoning about Turing Machines and abstracting away from the comparison operation. $\endgroup$
    – ShyPerson
    Oct 14, 2020 at 0:39


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.