As I understand it in simple language the proof of this goes

Take a program (called oracle below) that will stop if the program it is examining never halts and never halts if the program it is examining halts.

Using this oracle program to examine itself results in a contradiction ...

The thing I do not understand is, why should the oracle not work as follows.

The program says 'never halts' if the program being examined never halts and 'halts' if the program being examined halts?

No contradiction there?

My tentative answer to this issue is that my second program could be used to generate the original program and hence expose the contradiction.

  • $\begingroup$ Yes, you could use your alternative oracle to implement the original oracle, which then still leads to the contradiction. As far as I know that's actually a more common way of laying out the proof. See en.wikipedia.org/wiki/Halting_problem#Proof_concept $\endgroup$ – Izaak van Dongen Jan 12 at 17:44
  • $\begingroup$ Thanks. I think that must be it. From reading Turing's work, he uses a lot of prose to present stuff which I like. Especially for discussion. $\endgroup$ – nerak99 Jan 12 at 18:20

In the light of no other answers forthcoming. The objection is solved by using the fact that the simple program could be used to generate the said oracle and hence the contradiction is still there.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.