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

Oracle machine solving halting problem for other oracle machines

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

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.