19
$\begingroup$

From my understanding of the proof that halting problem is not computable, this problem is not computable because if we have a program P(x) which computes if the program x halts or not, we got a paradox when giving P as an input to the same P, having: P(P), trying to decide if P halts or not using P itself.

So my question is: is halting problem computable by program P for all other programs used as input but P itself? In other words: is halting problem not computable only in this special case or the proof is more general and I'm missing something?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I think you're misunderstanding the proof that the halting problem is not computable. P(P) just returns true, because P always determines whether a program halts in finite time. You need to do some slightly trickier construction to reach a contradiction. $\endgroup$ – Dan Staley Mar 8 '18 at 23:38
  • $\begingroup$ I think you would get better and perhaps practically more relevant answers if you asked whether there are many programs for which the halting problem is solvable. After all, many programs are even formally verifiable, which certainly includes a determination whether they stop with given inputs. I strongly suppose that that group cannot be determined (because that would amount to solving..., you know), but that for the vast majority of real world programs there are no obstacles to tell whether they halt or not, for relevant inputs. $\endgroup$ – Peter - Reinstate Monica Mar 9 '18 at 14:29
10
$\begingroup$

If $f$ is any computable function, then $g$, defined as

$$ g(n) = \begin{cases} f(n) & \mbox{if } n \neq k \\ v & \mbox{otherwise} \end{cases} $$

is also computable, for any choice of $k,v$.

Basically, if you have a program $P'$ which computes $g(n)$ for all $n$'s except for $n=k$, you can "fix" that case (e.g. using an if then else) and obtain another program $P$ which computes $g(n)$ for all $n$.

Hence, if you could compute the halting function "except for one case", you could also compute the halting function (with no exceptions). From that, you can obtain a contradiction as usual.

Conclusion: no, you can't decide the halting problem "except one case" (nor "except finitely many cases").

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Ok, I think I got it mathematically... But I was wondering: if I would try to write a program which computes the H.P. what concrete problems would I face? Why and how at some point I would understand I can't write such a program? $\endgroup$ – Alessio Martorana Mar 7 '18 at 19:22
  • $\begingroup$ @AlessioMartorana It depends: how would you approach such problem? A main issue is that $P$ must always halt, even when its input is a non-halting program -- so you can't simply try to simulate the input program. $\endgroup$ – chi Mar 7 '18 at 19:40
  • $\begingroup$ And supposing we can see the code of the input program? Can't we from the code see if the program halts? $\endgroup$ – Alessio Martorana Mar 7 '18 at 20:40
  • 2
    $\begingroup$ @AlessioMartorana We can indeed see the code, but if there is e.g. a while loop we can't say much in general. A while loop might check all the possible proofs of an arbitrary mathematical conjecture, and stop only if a proof is found. Deciding whether this loop halts means deciding whether the conjecture is provable. Solving the HP would give us a machine that would answer Yes(provable)/No(not provable) to any formal mathematical question. That would be unrealistically powerful. $\endgroup$ – chi Mar 7 '18 at 21:12
  • 1
    $\begingroup$ @AlessioMartorana If you thought you had written a program that solves the HP, where your program would fail is in one of two ways: for some programs it might return the wrong result (saying something halts when it doesn't or saying something doesn't halt when it does) and/or your decider program itself wouldn't halt on many inputs with you unable to know whether it really won't halt or if it just needs more time to compute the answer. $\endgroup$ – Shufflepants Mar 9 '18 at 15:26
21
$\begingroup$

is halting problem computable by program P for all other programs used as input but P itself?

No. Consider the infinite sequence of programs $P_1, P_2, \dots$, where $P_i$ is "Move the head $i$ squares to the right, then $i$ squares to the left, then do exactly what $P$ would do." Every one of these programs produces exactly the same output as $P$ for every input (including looping forever if $P$ loops forever), but they're all different programs.

And you can't get around this by only requiring $P$ to work on programs that aren't functionally equivalent to itself, since that property is also undecidable. Perhaps the problem would be decidable when restricted to those instances (though I suspect it wouldn't) but the set of instances is undecidable, so you couldn't actually perform the restriction.

|cite|improve this answer
$\endgroup$
  • 15
    $\begingroup$ I suspect your last sentence is probably true, but I don't think it follows that because a property is undecidable that restricting the input set based on that property will leave the problem undecidable. As a dumb example, if you restricted the input set to terminating programs (an undecidable property), the problem would be decidable (by a program that always returned true). $\endgroup$ – Owen Mar 8 '18 at 0:07
  • 3
    $\begingroup$ @Owen When the restriction itself is undecidable, you can’t impose the restriction so it can’t buy you anything in reality. $\endgroup$ – David Richerby Mar 8 '18 at 8:07
5
$\begingroup$

There are algorithms to show that certain classes of programs do or don't halt. For example,

  • It is possible to determine algorithmically whether a program that models a finite-state machine halts.
  • It is possible to determine arithmetically whether a linear-bounded turing machine halts
  • If you know what complexity class a program is in, then you know that the program halts for finite inputs.

While there's no algorithm to determine if an arbitrary program halts, a majority of code was designed either to halt (like most subroutines) or not halt (like an infinite loop to handle events), and it's possible to algorithmically to determine which is which. In other words, you can have an algorithm that answers either "halts", "doesn't halt", or "I dunno", and such an algorithm can be designed to cover enough programs that it would be useful.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What does this have to do with goto? Can't we have a program that uses goto and still decide whether it halts, as long as it models a finite state machine? $\endgroup$ – Bergi Mar 8 '18 at 22:51
  • $\begingroup$ I was going to write about halting in terms of for-loops, and then changed it just to talk about finite state machines and whatnot $\endgroup$ – Antonio Perez Mar 9 '18 at 0:49
4
$\begingroup$

Proofs by contradiction don't have to be exhaustive, a single counter-example is enough. The proof of the halting problem being undecidable provides you with one example of P for which the halting property cannot be decided. This proof doesn't state that P is the only such program, in fact, there may exist independent proofs constructing completely different classes of P.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

The proof is indeed more general: the halting problem is a special case of Rice's theorem, which states

If $\Phi$ is a property of programs that is independent of representation, then it is either always true, always false, or undecidable.

where "independent of representation" means that if $A$ and $B$ are programs that have the same behaviour for all inputs, then $\Phi(A)$ holds iff $\Phi(B)$ holds.

This means in particular that for every input $x$, the set of programs that halt on $x$ is undecidable; you cannot get decidability by reducing the input space.

You can get some results by restricting the space of programs you want to work with, though these restrictions have to be fairly drastic. For example, if you are guaranteed that the program you are given either halts within 100 steps or runs forever, deciding whether it halts becomes easy.

A more complicated case is when you know that the program is at most 100 characters long. Since there are only finitely many programs of that length, there exists some number of steps $N$ that is an upper bound on how long such a program can run if it terminates. However, the function that maps a program length $k$ to a maximum number of steps $BB(k)$ is not computable.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Technically, $N$ is computable: it's just a single natural number and any natural number is computable. What you really mean is that any function that maps the number of characters in the program to an upper bound on the running time of programs of that length is uncomputable. $\endgroup$ – David Richerby Mar 8 '18 at 12:17
  • 1
    $\begingroup$ The last paragraph resembles Busy Beaver. $\endgroup$ – Evil Mar 8 '18 at 12:23
  • $\begingroup$ With regards the "fairly drastic" restrictions: total programming languages are a thing. They tend to require a relatively high degree of sophistication, so maybe you consider that drastic, but it's possible to solve real problems in a space of programs that provably halt. $\endgroup$ – Ben Millwood Mar 8 '18 at 16:14
  • $\begingroup$ Including a link to en.wikipedia.org/wiki/Rice%27s_theorem would make sense IMO. $\endgroup$ – Dmitry Grigoryev Mar 9 '18 at 8:29
  • $\begingroup$ Thanks, I've updated the answer. @BenMillwood Certainly, but given their solution is "make everything halt" I'm not sure it's really what Alessio is looking for. A case where the halting behaviour is decidable but non-trivial would be interesting, though: maybe Agda + coinductive types? $\endgroup$ – Anton Golov Mar 9 '18 at 21:33
0
$\begingroup$

Let R be any recursively enumerable but nonrecursive set. There are infinitely many such sets. Let T be a Turing machine that halts on input k if and only if k is in R. Such a T exists for any recursively enumerable set. It is impossible to write a program which can solve the halting problem for this T. This is because any algorithm to determine if T halts would yield an algorithm for determining membership in R, which is impossible if R is nonrecursive. Since there are infinitely many such R, each of which give different Turing machines, there are infinitely many Turing machines that any attempted halting program P would fail on.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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