1
$\begingroup$

Let the finite time halting problem to be one where the program is counted as "not halting" if the Turing machine takes more than a given time interval to run the program. Is this finite time halting problem undecidable?

$\endgroup$
3
$\begingroup$

This subject has annoying terminological redundancy - e.g. "decidable," "computable," and "recursive" all mean the same thing in this context. Below I'm using "computable" exclusively, since "recursive" is slightly old-fashioned and "decidable" does significant double-duty elsewhere in logic.

It is computable.

Precisely: the "general finite halting problem" $X$ of triples $(e,m,s)$ such that the $e$th Turing machine on input $m$ halts in at most $s$ steps is computable. Indeed, $X$ (or more precisely, the characteristic function of $X$) is even primitive recursive. (This is all related to Kleene's $T$ predicate.)

This is essentially a quick application of the universal Turing machine: to test whether $(e,m,s)\in X$ we want to run the $e$th Turing machine on input $m$ for $s$ steps and see what happens. And this is basically exactly what a universal Turing machine is for. It's a good exercise to write out the details, but there aren't any surprises.


Note that the halting problem $H=\{e:\Phi_e(e)\downarrow\}$ is a "projection" of $X$ in a sense: $$H=\{e:\exists s((e,e,s)\in X)\}.$$ In general, the image of a computable set under a computable function need not be computable but will always be computably enumerable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What if the Turing machine is not allowed to run for s steps? This is true in the normal Halting problem where the Halt machine (that checks if a program halts) does not (and need not) run forever to decide that a program never halts. $\endgroup$ – Danny Sep 26 '19 at 9:02
  • $\begingroup$ @Danny Sorry, I just saw this. Using Turing machines in a finite alphabet, if we demand that we tell whether $(e,m,s)\in X$ in fewer than $s$ steps then in general we can't even read the full input (what if $e,m$ are much greater than $s$?). If we use register machines so the first two "cells" can hold $e$ and $m$ "all at once," this problem goes away, but now we hit (via the Recursion Theorem) the more subtle issue that we can never always simulate a length-$s$ computation in time $<s$ which means (since we have to spend a moment reading $e$ and $m$) that we still can't "quickly" compute $X$. $\endgroup$ – Noah Schweber Oct 9 '19 at 17:49
1
$\begingroup$

In addition to the excellent answer already posted, I'd like to point out some intuition for why it must be computable.

If you wanted to compute the characteristic function for the finite time halting problem we could run the machine for s steps on the given input. If we assign the value of 1 to problems that have halted in s steps and the value of 0 otherwise, then we have an algorithm that halts on every input.

| cite | improve this answer | |
$\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.