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:
- 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$).
- 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".
- 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?