In Turning Machine Halting Problem, is the memory of the Turing Machine infinite or finite?

Does the Turing Machine have access to infinite tape? Or limited tape?


1 Answer 1


By definition, every Turing machine has access to unlimited tape. At every point of execution the machine has inspected a finite portion of the tape, but it always has more available if needed. That is, it will never run out of it.

Mathematically, this is modeled by there being an infinite tape. However, as already stated, at every step of execution only a finite portion of the tape is used.

  • $\begingroup$ Thank you. Because if the Turing Machine had finite tape, then solving halting problem is easy. $\endgroup$ Commented Apr 16, 2022 at 9:11
  • 1
    $\begingroup$ Precisely. You could have made one more step of reasoning and ask: would this theorem really be famous and have a name if it were that easy? $\endgroup$ Commented Apr 16, 2022 at 23:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.