0
$\begingroup$

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 HN(P,i) that computes the Halting problem for a program P with exactly N states. If we take HN 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 HN(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 HN(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 HN 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.

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – cody
    Oct 24, 2023 at 22:36
  • 1
    $\begingroup$ True, I did not think of this. $\endgroup$ Oct 24, 2023 at 23:29
  • $\begingroup$ I think it's possible to expand the program by expanding the alphabet while keeping the number of states the same. $\endgroup$
    – user253751
    Nov 5, 2023 at 14:47

1 Answer 1

0
$\begingroup$

With the halting problem, the class of programs whose halting you determine, and the class of programs that we use to solve the problem, are the same.

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – user253751
    Nov 5, 2023 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.