# Is there any way to get "around" the halting problem?

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.

• Just keep swimming... Feb 12, 2017 at 4:12

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$.
• 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. Jan 27, 2017 at 19:30