1
$\begingroup$

Is it possible for an ordinary Turing Machine, for some input x, to run for an infinite number of steps but also halt? Or do we say that Turing Machine does not halt on x?

$\endgroup$
2
  • 3
    $\begingroup$ No. Yes. It's somewhat related to the question "What is the last natural number?" $\endgroup$ – Rick Decker Apr 27 '17 at 17:08
  • $\begingroup$ For a Turing Machine that starts at the left of its input tape x and halts when it reaches the right of the input tape, and with each step it moves right by one on the input tape, as the input tape x's length grows towards infinity, will a normal Turing Machine ever be unable to halt? $\endgroup$ – Austin Maalk Apr 27 '17 at 17:22
5
$\begingroup$

The answer to your question, whether a Turing machine can run for infinitely many steps and subsequently halt, is negative. If a Turing machine runs for an infinite number of steps and never halts, then it just never halts. It runs forever. A Turing machine halts if it at some step, it halts. If this never happens, then it doesn't halt, and instead runs for infinitely many steps.

One can define infinite time Turing machines for which infinite computations do result in an output, but these are different from the ordinary Turing machines taught in your class. In particular, infinite time Turing machines can "compute" uncomputable functions.

$\endgroup$
0
0
$\begingroup$

Maybe you are confusing "arbitrarily large" and "infinite"? If a Turing Machine never halts, then any given step number will be arbitrarily large..but the step number will never be infinite.

$\endgroup$

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.