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.
