On Mon, Nov 5, 2018 at 8:51 AM Quentin Anciaux <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. 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 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.
