> On 5 Nov 2018, at 20:13, Quentin Anciaux <allco...@gmail.com> wrote: > > https://en.m.wikipedia.org/wiki/Oracle_machine > <https://en.m.wikipedia.org/wiki/Oracle_machine> > Le lun. 5 nov. 2018 19:28, Quentin Anciaux <allco...@gmail.com > <mailto:allco...@gmail.com>> a écrit : > > > Le lun. 5 nov. 2018 19:17, John Clark <johnkcl...@gmail.com > <mailto:johnkcl...@gmail.com>> a écrit : > On Mon, Nov 5, 2018 at 8:51 AM Quentin Anciaux <allco...@gmail.com > <mailto:allco...@gmail.com>> wrote: > > >>There is no evidence fire breathing dragons exist in nature but if one did > >>it would not produce a logical contradiction, however Turing proved over 80 > >>years ago that a oracle that could solve the Halting Problem would. > > > It does not, it "solves" it for turing machines... it does not for turing > > machine + oracle... there is no contradiction. > > In a way that's true but the price paid is one of ambiguity. You say the > oracle can predict if any Turing Machine will halt, OK but the oracle is not > a Turing Machine so can the oracle predict if it itself will halt? Nobody > known how the oracle works so nobody can say but if it can then it can't and > I can prove it. > > > It can't... Again, the oracle solves it for TM... Not for TMO.. But another > oracle... Call it O2... Can solve it for TMO... But not for TMO2... Etc > > Let's give the turing machine + oracle you mentioned a name, I'll call it a > TMO. If the TMO can solve the Halting problem then if I feed in any Turing > Machine it can tell me if it halts or not. Any computer that is not a oracle > can be reduced to a Turing Machine regardless of it circuit design, so let's > say the TMO has 2 slots for input and one slot for output, if I feed in the > circuit logic design blueprints of any computer into one slot the TMO can > simulate that computer, and if I feed in program data into the other slot > that TMO will output either "Halt" meaning the simulated machine operating on > that data will eventually stop or the TMO will output "not halt" meaning the > simulated machine operating on that data will never stop. > > I will now make a new machine called X, it has 3 parts to it. The first part > of X is just a Xerox copy machine, feed in one program and it outputs 2 > identical programs. The second part of X is the TMO and it receives the 2 > programs as input from the Xerox machine's outputs, and the TMO then outputs > either "halt" or "not halt". The third and last part of X is a very simple > machine called the negator, it receives as input the output of the TMO and if > the input to the negator is "Halt" the negator will go into a infinite loop > and if the input is "not halt" the negator will print "halt" and then stop. > > Now let's draw the blueprint circuit design of the entire X machine that > fully defines it, then make 2 copies of it and feed it into the TMO; so the > TMO is now trying to figure out if the X machine will halt if it is fed its > own blueprint as data. If the TMO says "halt" the X machine will not halt and > the TMO was wrong. If the TMO says "not halt" the X machine will halt and > the TMO was wrong again. Therefore the TMO that can tell if any Turing > Machine will halt or not can not logically exist. > > I suppose you could argue that the oracle operates according to some sort of > magic so you couldn't have the blueprints of it and therefore you couldn't > have the blueprints of the entire X machine, but then the very question of > whether the X machine halts is not a well defined question because the X > machine itself is not well defined and the properties of the oracle are > ambiguous. So oracle or no oracle, anything that can always tell if any well > defined program will halt or not halt when run on a well defined computer > will lead to a logical contradiction. > > John K Clark

Quentin is right. In fact oracle have been introduced by Turing to study if adding non computable information could overcome incompleteness, and what Turing did was that it does not. Machines with oracle, being for the PI_1 halting problem, or the PI_2 totality problem, or for qG (which is also PI_2-complete) remains arithmetically incomplete. qG* can be shown PI_1-complete with the oracle of the whole arithmetical truth. Even god (arithmetical truth) has to be invoked an infinity of times to solve an arbitrary self-reference problem. But this is of no use for us, as there are no more evidence for an oracle in nature, and worst, if we are machine, we cannot distinguish in a finite time if something is an oracle, or just a machine more complex than ourselves. The interest in Oracle is purely negative: they do not overcome the incompleteness phenomenon. In fact the theology of the machine (the G* theory) is valid for basically all reasonable non-machine-extensions. Bruno > > > -- > 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 everything-list+unsubscr...@googlegroups.com > <mailto:everything-list+unsubscr...@googlegroups.com>. > To post to this group, send email to everything-list@googlegroups.com > <mailto:everything-list@googlegroups.com>. > Visit this group at https://groups.google.com/group/everything-list > <https://groups.google.com/group/everything-list>. > For more options, visit https://groups.google.com/d/optout > <https://groups.google.com/d/optout>. > > -- > 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 everything-list+unsubscr...@googlegroups.com > <mailto:everything-list+unsubscr...@googlegroups.com>. > To post to this group, send email to everything-list@googlegroups.com > <mailto:everything-list@googlegroups.com>. > Visit this group at https://groups.google.com/group/everything-list > <https://groups.google.com/group/everything-list>. > For more options, visit https://groups.google.com/d/optout > <https://groups.google.com/d/optout>. -- 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 everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.