patternMajor
Is halting problem computable for particular inputs/assumptions
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?
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.
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.