patternMinor
Is there any way to get "around" the halting problem?
Viewed 0 times
aroundproblemtheanywayhaltinggetthere
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.
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.
Solution
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
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$.Context
StackExchange Computer Science Q#69396, answer score: 6
Revisions (0)
No revisions yet.