A program that solves the Halting Problem for programs with N states

Question

My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in general. However, I think that this does not show that there is no program H_N(P,i) that computes the Halting problem for a program P with exactly N states. If we take H_N to be the program that does this computation with the fewest states possible, the proof does not necessarily work:

Defining the program X(A) that halts when H_N(A,A) returns "Does Not Halt" and loops forever when it returns "Halts" does not necessarily imply a contradiction. This is because when we compute H_N(X, X), we only get defined behavior if X has exactly N states, which is something that must be shown to continue the proof.

In fact, it could very well be the case that there are no programs that do this computation using N states, and that H_N just returns some undefined output if we were to run this simulation.

Is there something I'm missing? I am not super knowledgeable on this topic.

edit: This would not imply a flaw in the reasoning behind the Halting Problem as a counterexample, but it shows that the Halting Problem does not show that programs that solve the Halting Problem for any arbitrary program with fixed states.

• cody: Imagine $N$ happens to be the number of states for a given universal Turing machine. Does allow you to define $H(P, i)$ in general?
• Vincenzo Buselli: True, I did not think of this.
• Stack Exchange Broke The Law: I think it's possible to expand the program by expanding the alphabet while keeping the number of states the same.
• gnasher729: @StackExchangeSupportsIsrael That doesn’t make a difference. The set A of programs whose halting you want to determine, and the set B of those that determine halting, is not the same, so finding a program in B that determines whether each program in A halts doesn’t lead to a contradiction.

Answer 1

With the standard halting problem, the class A of programs whose halting you determine, and the class B of programs that we use to solve the problem, are the same. If we assume "there is a program in A which determines for every program in A that it halts" then we get a contradiction.

If you examine programs with n states, you can’t in general find whether they are halting using a program with n states. We might find a program that determines if programs with n states halt. But that doesn’t give us the contradiction if it is a program with more states.

Now we can write a simulator which simulates programs with n states. For many programs it will determine that they halt. For many it will determine they start running in a pattern that never halts. But many will be too difficult.

• Stack Exchange Broke The Law: If you examine programs with n states, you can’t in general find whether they are halting using a program with n states <- is this a theorem or is it a conjecture?
• gnasher729: It’s a simple theorem. If you found such a program you’d have the same argument as in the standard halting problem which shows it doesn’t exist.
• Li-yao Xia: This is not a simple theorem because the standard argument works by constructing another machine M on top of the one that is assumed to solve the halting problem, and then applying M to itself. But M will have more states than the initial machine so you won't derive a contradiction that way.
• user1937198: So long as are allowed four symbols, you can modify the standard argument, by adding a UTM U, which runs M, which runs M. It requires a UTM, which makes it more complex.
• user1937198: If you can't prove halting for n states => you can't prove halting for a UTM that can run any n state TM, 2 state 4 symbol UTM exists, any arbitrary states will always include all 2 state TMs, => arbitrary states will always include a pathological program.