-4
$\begingroup$

in here they claim: "there is an algorithm deciding almost all instances of [halting problem]"

so I'm wonder whether there is a computable function $h':\mathbb{N}\to\{0,1\}$ such that the following turing machine is a halting decider (for TMs running on blank input) except for itself

$$ \begin{align*} M(m) &= \begin{cases} \text{loop in state $q_{accept}$} & \text{if $h'(m)=1$} \\ \text{halt in state $q_{accept}$} & \text{if $h'(m)=0$} \\ \end{cases} \end{align*} $$

for me as a programmer $h'$ is very interesting function because it connect arithmetic to turing machines

$\endgroup$
19
  • $\begingroup$ don't you mean h' is a halting decider? since it returns 0 or 1 depending on whether a program halts? $\endgroup$ Commented Dec 5, 2022 at 23:18
  • $\begingroup$ The paper says that if you create programs at random, you're quite likely to get one that can be proven to halt or not halt. But it's also using a weird kind of Turing machines where it's possible to "halt without halting". I'm not sure it generalizes to the usual sort of Turing machines. $\endgroup$ Commented Dec 6, 2022 at 3:24
  • $\begingroup$ @user253751 if you trust the consistency of Peano Arithmetic then there is an algorithm that solve almost all instances of halting problem and all instances that it can't recognize are looping instances so if you print 0 first and try to search for a proof of halting status of the input program if you find a proof then you have 00 or 01 as output but if you don't find a proof then you have 0 as output $\endgroup$
    – raoof
    Commented Dec 7, 2022 at 6:27
  • $\begingroup$ then you haven't solved the halting problem. The halting problem has two answers but your program has 3 answers. $\endgroup$ Commented Dec 8, 2022 at 2:16
  • $\begingroup$ The paper has two kinds of halting. One of them isn't called "halting". They call them "halting" and "falling off the tape". But it's really the same as two kinds of halting. $\endgroup$ Commented Dec 8, 2022 at 2:23

1 Answer 1

3
$\begingroup$

No, you can't. If you had a procedure $M$ that would correctly solve the Halting problem for all but finitely many instances $p_0,p_1,\ldots,p_k$, then there would exist a computable solution to the Halting problem as follows:

Input $p$

if $p = p_0$, return $b_0$

elseif $p = p_1$, return $b_1$

...

elseif $p = p_k$, return $b_k$

else return M(p)

If the $b_i$ are correctly chosen, this is solving the Halting problem. (We don't necessarily have a way to figure out the correct choice, but it clearly exists.)

So if we take the usual reading of "almost all" to mean "all but finitely many exceptions", we cannot solve the Halting problem for almost all instances. But that is not what the paper you've linked is claiming. They say that for one natural encoding, we can solve the Halting problem for a set of instances $I$ such that $\frac{|I \cap \{0,1,\ldots,n-1\}|}{n}$ tends to $1$ as $n$ goes to infinity.

$\endgroup$
5
  • $\begingroup$ I linked to the paper as a motivation for my question but my question does not depend on the paper, I'm asking is there a TM that solves the halting problem for all instances except itself by adding a loop transition to the accepting state to avoid diagonalization meaning $M(M)$ is wrong and you can't use $M$ as a subroutine in another turing machine because it has a loop transition in it's accepting state $\endgroup$
    – raoof
    Commented Nov 19, 2022 at 12:22
  • 3
    $\begingroup$ @raoof And I'm telling you that you can't get "solves all but finitely many instances", no matter what you do. $\endgroup$
    – Arno
    Commented Nov 19, 2022 at 12:28
  • 3
    $\begingroup$ @raoof: You are asking whether one can build a Halting Decider that can Decide the Halting Problem for all except one instance and this answer explains why it is impossible to build a Halting Decider that can Decide the Halting Problem for all except a finite number of instances. Since one is a finite number, this more general answer also answers your question. $\endgroup$ Commented Nov 19, 2022 at 12:53
  • $\begingroup$ @JörgWMittag the problem with this answer is that you can't call $M(p)$ because it loops on infinitely many inputs, I'm arguing that if we use the counter example to $h'$ as the halting decider then there is no other counter example, the only counter example is $M$ itself $\endgroup$
    – raoof
    Commented Nov 19, 2022 at 13:02
  • $\begingroup$ The paper also seems to use a trick by redefining what halting is. IMO it is more natural to either consider a tape that is infinite in both directions. The paper's argument is: random programs move randomly on the tape; most random walks eventually go off the left edge of the tape; therefore most random programs do stop running eventually. $\endgroup$ Commented Jan 5, 2023 at 16:08

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.