On Tue, Feb 25, 2020 at 8:34 AM Bruno Marchal <marc...@ulb.ac.be> wrote:
>> I have a halting oracle machine and it has 2 input slots, one slot for >> the logical blueprints of a computer in digital form and the other slot for >> a program, also in digital form, to run on that computer. The oracle >> machine will then output either the words "Halt" or "Not Halt" depending on >> what a program running on that computer will do. I decide to use the oracle >> machine as one part of a new 3 part machine I will call machine X. The >> first part of machine X is just a photocopier that makes two copies of its >> input and then feeds them into the 2 input slots of the oracle machine. The >> last part of machine X is the negator, if it receives a "Not Halt" input >> from the oracle machine then the negator will output "Halt" and then >> stop, if the negator receives a "Halt" input from the oracle the negator >> will go into an infinite loop and never stop. The entire X machine as >> constructed has one input slot and one output slot. >> I will now input machine X with machine X's own blueprints, so after the >> photocopier has done its work the oracle machine will receive identical >> inputs in both slots and the oracle machine will have to figure out what >> will happen to the X machine when the X machine is fed it's own blueprint >> as input. If the oracle says under those circumstances the X machine will >> halt then the X machine will never halt, and if the oracle says the X >> machine will not halt then the X machine will print "Halt" and stop. So the >> halting oracle machine always makes predictions that are wrong. So there is >> no such thing as a halting oracle machine. QED. > > > *> This shows that the machine+halting-oracle cannot solve the halting > (machine+halting-oracle) problem,* > Yes, it can't solve the halting problem. * > but the halting-oracle is supposed fro be concerned only for the > machine halting problem, i.e. the machine without oracle. * > Supposed? That's a rather silly thing to say, if the oracle machine is well defined and the machine is well defined then the new combined machine is also well defined and the so called halting oracle fails miserably when it tries to predict if this new well defined machine will halt or not. 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 view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv0nL7U1JpUKzzqUgCM8q_ko6htewkU4AkET4dNquWWHLA%40mail.gmail.com.
