3
$\begingroup$

As I understand it, one proof of the Halting Theorem is done by contradiction; we assume we have program X which can determine if any program terminates. We input program X into program X (with some modifications at the output), and we arrive at a contradiction. However, is it possible for a program Y to exist, where program Y can determine if any program (except variants of Y itself, or most loosely any finite set exceptions) halts?

If the set of exceptions must be infinite, can we have at least the set of permissible inputs be infinite itself?

Please try to keep the answers at a lower level, I know a little bit of mathematics but I am a complete layman in computer science.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Just keep swimming... $\endgroup$ – wogsland Feb 12 '17 at 4:12
6
$\begingroup$

Say that two programs are equivalent if they have the same halting behaviour and output on every input. The problem for your "finite exceptions" idea is that there are infinitely many programs equivalent to any program you choose. Given a program $P$, we can always modify it in infinitely many ways without changing its output or halting behaviour: for each natural number $n$, we can write a program that essentially counts to $n$ and then runs $P$.

I suppose the good news is that this means we can decide the halting problem on an infinite class of programs. For example, let $P_n$ be the program for i = 1 to n do [nothing]; halt;: the halting problem is easily decidable on the set of all programs $P_n$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ It's worth mentioning that the Halting Problem is decidable on much larger infinite classes of programs, such as the Primitive Recursive functions, or even $\lambda \Pi_{\omega}$ from the Lambda Cube. Trivially decidable, since all programs in these systems halt. $\endgroup$ – jmite Jan 27 '17 at 19:30

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.