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.

Reply via email to