5 ms·
Suppose O is the oracle for the halting problem. We create a machine: given a program P, ask O whether P halts given input P and negate the answer. λP. ~O (P
by g___ 2y ago
Suppose O is the oracle for the halting problem.
We create a machine: given a program P, ask O whether P halts given input P and negate the answer.
λP. ~O (P P)
Now we ask whether this machine will halt given its own source code as input. In symbols:
(λP. ~O (P P)) (λP. ~O (P P))
which is the Y-combinator in lambda calculus.
- thedudeabides5 2y agoaren't oracles, just attempts to escape the halting problem? assume you have an O which doesn't halt now feed P which DOES halt into O oh look it catches it! misses the boat
- bongodongobob 2y agoNo, in fact you can use oracles to prove the halting problem.