1
$\begingroup$

The halting problem is semi-decidable. Does that mean that:

  • If a program terminates it can always be established/determined?
  • If a program does not terminate
    • It can sometimes be established/determined?
    • It can sometimes not be established/determined?

When we write programs we can clearly proof in some instances that the program terminates or that it will never terminate. But, simply there are some programs for which we can't proof termination for all inputs.

$\endgroup$
2
  • $\begingroup$ A simple strategy is to run the program. If it halts before one year, you are done. Otherwise, say that you don't know. $\endgroup$
    – user16034
    Commented Oct 10, 2022 at 18:43
  • $\begingroup$ Since for all programs with a set of possible inputs which is countably infinite [except 0-arry functions i.e. constant functions], it would not be possible even to run the program until it terminates for all inputs. $\endgroup$
    – RFV
    Commented Oct 11, 2022 at 16:16

2 Answers 2

2
$\begingroup$

The Halting Problem is semi-decidable, also called recognizable, and that means there is a Turing Machine $H$ that will, given a Turing Machine $M$ as input, accept $\langle M, s\rangle$ if and only if it halts in finite time on bounded input $s$ and otherwise will reject or fail to halt itself. This means, in a certain sense, that a TM that halts in finite time on an input $s$ can always be recognized as such.

However, there is no upper bound on how long $H$ can run for an arbitrary input $\langle M, s\rangle$. This means the results of $H$ are useful only for establishing that certain machines halt, but never for establishing that other machines don't halt – after all, even after running $H(\langle M, s\rangle)$ for arbitrarily long we cannot say with certainty whether $M$ does not halt on $s$, or whether $H(\langle M, s\rangle)$ just needs more time to compute. Therefore we cannot, with perfect certainty, know which TMs halt and which ones don't – but fixing a string $s$ and running $H$ on different TMs will give us a set of TMs that certainly halt on $s$ that grows the more time $H$ is given.

There is no general procedure for recognizing non-halting TMs: any putative non-halting recognizer will fail to recognize some subset of non-halting TMs as non-halting. However, there are partial recognizers for non-halting: this is the simplest to see with restricted cases of TM. For instance a TM that moves right with every state transition can be determined to never halt if it visits the same state twice after reading to the right of its input.

$\endgroup$
0
$\begingroup$

I think you are right.

If a program terminates, it can always be determined by running the universal TM to simulate the program trivially. If a program does not terminate, it can be determined sometimes by recognizing some special structures like infinite loop; or cannot be determined when the input is something in the part that causes HALT to be undecidable.

$\endgroup$
7
  • $\begingroup$ "If a program terminates, it can always be determined by running the universal TM to simulate the program trivially": this does not work because you don't know how long you have to wait. $\endgroup$
    – user16034
    Commented Oct 10, 2022 at 18:45
  • $\begingroup$ It’s not that case. A decider only needs to know that it will halt eventually, with no need on guaranteeing its running time. $\endgroup$
    – Heda Chen
    Commented Oct 10, 2022 at 23:56
  • $\begingroup$ You contradict yourself. Running the program does not tell you that it will terminate. $\endgroup$
    – user16034
    Commented Oct 11, 2022 at 6:23
  • 1
    $\begingroup$ Please read the condition again... The original problem description says, "If the program terminates, it can always be determined", which just means that the algorithm only need to have correct behavior on these specified-to-terminate inputs (rather than all inputs). $\endgroup$
    – Heda Chen
    Commented Oct 11, 2022 at 9:19
  • $\begingroup$ I see. The condition can be understood as "If the program is a terminating one [for this input]". Hence the confusion. If the program under scrutiny indeed terminates, I can't see why you would still need to "determine" and "simulate" anything. This strengthens the confusion. $\endgroup$
    – user16034
    Commented Oct 11, 2022 at 9:43

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.