HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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 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.