> On 23 Feb 2020, at 14:34, John Clark <[email protected]> wrote: > > On Sun, Feb 23, 2020 at 7:12 AM Bruno Marchal <[email protected] > <mailto:[email protected]>> wrote: > > > The BB is computable already with the Halting oracle > > But a Halting oracle produces paradoxes,
I don’t see why you say this. The quantum oracle is just a (non computable) set of numbers, and it has been used by Turing and others to show that even with such oracle, we cannot solve some problem in arithmetic, like the totality problem TOT (deciding if a number code for a total or strictly partial computable functions). Of course, with an oracle for TOT you can solve the halting problem, but the pont is that with the halting oracle, you still cannot decide TOT. This shows that TOT is more unsolvable than HALT, or that HALT is simpler than TOT. This is the starting result of the study of the degrees of unsolvability, which is mainly Recursion Theory. All this means that adding “divine abilities” to machine, does NOT overcome incompleteness. The universal machine is Sigma_1 complete. HALT is Pi_1 complete, TOT is Pi_2 complete (like quantified G, btw). To be the code of a finite set is Sigma_2 complete, to be the code of a recursive set is sigma_3 complete, etc. > and I don't just mean weird situations I mean genuine logical contradictions. There is no contradiction coming from the existence of an oracle for the halting problem. See my older post to see how to modify a Turing machine so that the can consult an oracle. (I can explain again if you want). Bruno > > John K Clark > > -- > You received this message because you are subscribed to the Google Groups > "Everything List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected] > <mailto:[email protected]>. > To view this discussion on the web visit > https://groups.google.com/d/msgid/everything-list/CAJPayv0kygvSqQo0WhGOF-2rUQMmGfcoDeEv1FNroE93Lx3bQA%40mail.gmail.com > > <https://groups.google.com/d/msgid/everything-list/CAJPayv0kygvSqQo0WhGOF-2rUQMmGfcoDeEv1FNroE93Lx3bQA%40mail.gmail.com?utm_medium=email&utm_source=footer>. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/6AF8D338-E5AB-4B8E-944C-0C5B7BDCC774%40ulb.ac.be.
