What's wrong with this proof of undecidability of bounded halting problem?

Question

For some arbitrary Turing Machine T and input X the problem

Does T halts on input X?

--- is undecideable as shown by the simple proof by contradiction in Wikipedia https://en.wikipedia.org/wiki/Halting_problem#Proof_concept

---

Now for an arbitrary natural number N, the problem

Does T halts on input X within N steps?

--- is supposedly decidable because - well - just run it for N steps and see if it halts. From looking at related discussions in StackExchange, this seems to be clear to most people.

But then we can also construct the same proof as the one for the general Halting problem, like as follows:

Suppose there exist a function halts_in_N_steps(f) that is computable within N-1 steps and returns True if the function f halts within N steps and False otherwise. Furthermore, consider the following function:

def g():
    if halts_in_N_steps(g):
        loop_for_N+1_steps()
        return 0
    else:
        return 0
        

If halts_in_N_steps(g) returns True, then g() ends up looping for N+1 steps. If halts_in_N_steps(g) returns False, then g() ends up running within N-1 steps. Both cases lead to contradiction.

I know I'm wrong on this proof but I don't know where exactly I am wrong.

Answer 1

Modulo some fuzziness (which gets resolved differently depending on the exact model of computation, and possibly involving replacing "$N-1$" with "$N-c$" for some other $c$), you have correctly shown that your assumption

there exist a function halts_in_N_steps(f) that is computable within N-1 steps and returns True if the function f halts within N steps and False otherwise

(emphasis mine) is false. However, this does not contradict the claim that halting in $\le N$ steps (for $N$ fixed) is decidable - simply that it isn't decidable "quickly."

---

It may be worth noting that this is a general theme with complexity results like this. "Global" complexity results such as "The halting problem is undecidable," "Truth is undefinable," and even "The reals are uncountable" have local analogues whose proofs can be automatically extracted from the global argument but which also permit a simplicity result:

• The proof of the undecidability of the halting problem yields proofs of results like "the $N$-step halting problem is not decidable in $N-1$ steps" (phrased appropriately, and for an appropriate computation model). But this doesn't contradict the decidability of the $N$-step halting problem.

• The proof of Tarski's undefinability theorem shows that there is no $\Sigma_n$ truth predicate for the class $\Sigma_n\cup\Pi_n$. But this doesn't contradict the existence of a $\Sigma_n$ truth predicate for the class $\Sigma_n$, let alone the overall definability of $\Sigma_n\cup\Pi_n$ truth. And indeed such bounded truth predicates, both in arithmetic and in set theory (the latter construed via the Levy hierarchy), are extremely useful tools.

• The diagonalization argument showing that $\mathbb{R}$ is uncountable also shows that for every "reasonable" complexity class $\mathfrak{C}$, the subset of reals $\mathbb{R}\cap\mathfrak{C}$ is not "$\mathfrak{C}$-countable" - e.g. the computable reals are not "computably countable," the polynomial-time computable reals are not "polynomial-time countable," etc. But this doesn't contradict the overall countability of $\mathbb{R}\cap \mathfrak{C}$ for many choices of $\mathfrak{C}$ (indeed, we often have "nearly $\mathfrak{C}$-countability" - the existence of a universal Turing machine, for example, at first glance comes very very close to establishing that the computable reals are computably countable!).