patternMinor
Oracle machine solving halting problem for other oracle machines
Viewed 0 times
problemsolvinghaltingotherformachinesmachineoracle
Problem
Could someone give me a simple explanation why an oracle machine that can solve the halting problem for standard Turing machines, is however unable to solve the halting problem for other such oracle machines?
I have tried searching for the answer online but could not find any that really answered the question.
I have tried searching for the answer online but could not find any that really answered the question.
Solution
The proof that a Turing machine with an oracle for $X$ can't solve the halting problem for Turing machines with an oracle for $X$ is identical to the proof that an ordinary Turing machine can't solve the halting problem for ordinary Turing machines.
Context
StackExchange Computer Science Q#96794, answer score: 7
Revisions (0)
No revisions yet.