A polynomially bounded Turing machine is the one which, on input $w$, uses no more than $f(|w|)$ cells on its tape, where $f$ is a polynomial. For this problem halting is decidable.

I do not understand why is halting decidable for this problem because $f$ is unknown to us.


1 Answer 1


You don't need to know $f$. It is sufficient to use the fact that there are only finite possible configurations.

Given an input $\langle \langle M\rangle,w\rangle$ where $M$ is a polynomially bounded TM, simulate $M$ on $w$ and record its configuration at every step. Whenever we find a repeated configuration, we can assert that $M$ does not halt on $w$.

Note if $M$ does not halt on $w$, it must experience a repeated configuration, so the process described above will always halt. Therefore this process is the decider for the halting problem.


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.