https://en.m.wikipedia.org/wiki/Oracle_machine
Le lun. 5 nov. 2018 19:28, Quentin Anciaux <[email protected]> a écrit : > > > Le lun. 5 nov. 2018 19:17, John Clark <[email protected]> a écrit : > >> On Mon, Nov 5, 2018 at 8:51 AM Quentin Anciaux <[email protected]> >> 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 >> >> -- >> 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 post to this group, send email to [email protected]. >> Visit this group at https://groups.google.com/group/everything-list. >> For more options, visit 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 [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
