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

Is halting problem computable for particular inputs/assumptions

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
probleminputscomputablehaltingassumptionsforparticular

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#89021, answer score: 22

Revisions (0)

No revisions yet.