Can a weaker version of the Halting Problem be solved?

Question

I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this:

1. Assume that some machine $H$ exists that can solve the halting problem on a given machine $A$ with input $x$ ($H$ determines whether the machine $A$ halts on input $x$).
2. Now build a machine $Q$ which consists of $H$ and an extra component that takes in the output of $H$ and functions by never halting whenever $H$ returns "true", and halts whenever $H$ returns "false".
3. Then feed into $Q$ itself as both its given machine and the machine's input. Now, what does $Q$ return? If the machine $H$ inside $Q$ determines that the system halts, thereby returning "true", then $Q$ does not halt, as outlined above. However, if $H$ determines that $Q$ does not halt, then it does halt, as outlined similarly above. Therefore $H$ cannot exist.

I understand how this prevents any machine from existing that provides a general solution to the halting problem for any input, but does it also prevent solutions to certain smaller problems as well?

Specifically, could there theoretically be a 1000-state or larger Turing machine which can solve the halting problem for all Turing machine inputs with 50 states or fewer (the specific values aren't relevant)? That way, the machine cannot be input itself as a parameter, and the contradiction above would not be relevant.

To be clear, I'm not asking whether such a machine could be feasibly built, but rather whether is it theoretically possible for such a program to exist that solves the problem for machines smaller than a certain limit?

Answer 1

If you define $H$ to take a 50-or-fewer state Turing machine (TM) and an arbitrarily large input, then if you can build a universal Turing machine (UTM) in 50-states, then you can simulate $H$ by encoding its description as well as its input into the input of the 50-state UTM.

If $H$ merely needs to tell whether any 50-or-fewer state TM halts with an empty tape as input, then, since there are finitely many such TMs, it can simply have a table hard-coded into it. Producing this table may be difficult, but it "exists" in the usual mathematical sense.¹ Given values of the Busy Beaver function, we can actually easily describe one potential implementation. Simply simulate the input TM up to the appropriate Busy Beaver number of steps, and if it hasn't halted by that point, then it never halts.

To give an idea of how difficult it is to produce the aforementioned table, just note that we can write a program that terminates only if ZFC set theory is inconsistent. Gödel's incompleteness theorem then implies that if ZFC is consistent, then it is not possible to prove that that program doesn't halt. The upshot of this is after a certain number of states (and not a very large number) even if you were outright given the (correct) TM to do what you describe, you could not prove that it was correct in ZFC. (This isn't particular to ZFC. ZFC is just the formal system that is usually considered the "foundation" of mathematics. Other formal systems will merely have different cut-offs.) In other words, even if you were given the answer, you could not convince yourself that it was correct.

¹ Actually, it exists in a stronger sense than many mathematical objects in that we can actually enumerate all the Turing machines and at some point the correct one will come up. We just won't realize it when it happens, in general.