Halting problem within a finite time interval?

Question

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?

Answer 1

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.

Answer 2

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.