Since the same contradiction from the Turing machine is still there, we allow the oracle not always return an exact value, and say it solves the halting problem if the probability of returning "HALT" equals to the one that the program halt.

If not possible, can it solve a weaker halting problem?

  • $\begingroup$ In particular, it's interesting what there will be if we'd put $\mathsf{ALL}$ oracle. $\endgroup$ – rus9384 Oct 2 '17 at 15:45
  • $\begingroup$ The question in the title seems to be different from the one in the body. $\endgroup$ – David Richerby Oct 2 '17 at 17:10
  • $\begingroup$ @David Richerby Why not? $\endgroup$ – l4m2 Oct 2 '17 at 17:45

Your Answer

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

Browse other questions tagged or ask your own question.