Page 6 of 6

### Re: Halting Problem

Posted: Sun May 07, 2017 11:37 pm UTC
Soupspoon wrote:(Altogether now...) Oh no it isn't!!

Jose

### Re: Halting Problem

Posted: Thu Dec 28, 2017 8:11 pm UTC
Returning to this after some months away to be sure that I understand the proof sufficiently. Any help would be appreciated.

Here's my high-level understanding of the proof:

We pretend that a program Oracle exists such that, for any program (P) with input (i), Oracle will tell us whether P halts when given i. Oracle accordingly can be represented like this: O(P, i)

Some background assumptions regarding Oracle that are necessary to the proof:

1. The proof works only if we assume that Oracle works for any program.

2. Oracle itself must halt every time or it's useless to us (because, if Oracle itself didn't halt, then it wouldn't be true that Oracle works for any program.

Next, we design a second program called Devious. Devious, unlike Oracle, takes only argument. And Devious has only one purpose: if Oracle says "yes" in response to the question of whether a program P will halt given input i, then Devious goes into an infinite loop and thus never halts. If Oracle says "no," then Devious halts. Devious is designed to do the exact opposite of what Oracle returns (or "predicts").

The steps below are where I'm having trouble and kindly request help:

We make Devious take itself as an argument: D(D)

But, somehow, the Devious-as-argument-to-Devious gets Oracle to run (I don't know how this happens). And then Oracle evaluates (Devious, Devious) (i.e., Devious as input to Devious). Oracle--because it's designed to answer the question of whether any given program P halts when given input i--returns a "yes" or "no" answer. But the outer layer of Devious always does the opposite, which shows that Oracle can't possibly exist.

### Re: Halting Problem

Posted: Thu Dec 28, 2017 9:06 pm UTC
MathDoofus wrote:1. The proof works only if we assume that Oracle works for any program.
Close. Maybe actually correct; I have to think about it.
Spoiler:
I figure that so long as for every program, there is an Oracle..., it should work. It doesn't have to be the same oracle, but if it is, the proof is easier to follow because you don't have to worry if you are using the "right" oracle. But I could be wrong about this - I wonder if the self reference actually makes this first condition necessary.
MathDoofus wrote:But, somehow, the Devious-as-argument-to-Devious gets Oracle to run (I don't know how this happens).
Devious contains (a copy of) the code for Oracle within it. Devious is essentially Oracle with its outputs reversed.

We feed a copy of Devious to itself as input. Devious "asks" its built-in Oracle if this combination would halt. The built-in Oracle gives an answer, and then Devious does the opposite. Haha gotcha nyah nyah nyah!

Given Oracle, Devious could be constructed. But Devious implies that Oracle can fail. Therefore, it must be that Oracle can't exist.

Jose

### Re: Halting Problem

Posted: Thu Dec 28, 2017 9:19 pm UTC
ucim wrote:
MathDoofus wrote:1. The proof works only if we assume that Oracle works for any program.
Close. Maybe actually correct; I have to think about it.
Spoiler:
I figure that so long as for every program, there is an Oracle..., it should work. It doesn't have to be the same oracle, but if it is, the proof is easier to follow because you don't have to worry if you are using the "right" oracle. But I could be wrong about this - I wonder if the self reference actually makes this first condition necessary.
MathDoofus wrote:But, somehow, the Devious-as-argument-to-Devious gets Oracle to run (I don't know how this happens).
Devious contains (a copy of) the code for Oracle within it. Devious is essentially Oracle with its outputs reversed.

We feed a copy of Devious to itself as input. Devious "asks" its built-in Oracle if this combination would halt. The built-in Oracle gives an answer, and then Devious does the opposite. Haha gotcha nyah nyah nyah!

Given Oracle, Devious could be constructed. But Devious implies that Oracle can fail. Therefore, it must be that Oracle can't exist.

Jose

Awesome! Thank you for the help. I'm still having trouble with Devious. I can get comfortable with Oracle and its two arguments (some program P given some input i) but I'm not entirely sure about Devious, in particular: (1) how Devious takes Devious as its argument and (2) then runs Oracle on Devious. Can you help with that? In other words, how is that Devious-as-argument itself get to take Oracle as an argument, which in turn takes two arguments (Devious and Devious)?

### Re: Halting Problem

Posted: Thu Dec 28, 2017 10:35 pm UTC
MathDoofus wrote:how Devious takes Devious as its argument
Any program can be written to take arguments (initial input). Any program is also just made up of data: to wit, the statements that make it up. So, you can feed (A COPY OF) any program into Oracle, or to Devious. It's just data.
Spoiler:
If you feed it into the CPU's instruction register, the CPU will execute the instructions, "running" the program. That's what distinguishes an "executable" program from other kinds of data, like a cat picture. If you feed a cat picture into the CPU's instruction register, it will do seemingly random stuff and cough up a hairball. Devious (the running program) is being fed into the instruction register; that's what makes it run. But a copy of Devious is being fed into Devious itself. That copy doesn't make it to the instruction register, instead it is analyzed by the running Devious.
MathDoofus wrote:then runs Oracle on Devious.
That's a shorthand way of saying "Devious contains a copy of Oracle's routines, and it feeds the input into those routines to see what Oracle would have said". In this case the input is the copy of Devious. So, its copy of Oracle's routines analyse Devious and says that Devious would do foo. But it tells Devious because those routines are part of Devious. Now that Devious knows what the prediction of its action is, it goes ahead and does the opposite, proving that Oracle isn't a very good oracle.

MathDoofus wrote:how is that Devious-as-argument itself get to take Oracle as an argument
It doesn't take Oracle "as an argument". It contains Oracle, like people contain hearts and livers.

Jose

### Re: Halting Problem

Posted: Thu Dec 28, 2017 10:41 pm UTC
ucim wrote:
MathDoofus wrote:how Devious takes Devious as its argument
Any program can be written to take arguments (initial input). Any program is also just made up of data: to wit, the statements that make it up. So, you can feed (A COPY OF) any program into Oracle, or to Devious. It's just data.
Spoiler:
If you feed it into the CPU's instruction register, the CPU will execute the instructions, "running" the program. That's what distinguishes an "executable" program from other kinds of data, like a cat picture. If you feed a cat picture into the CPU's instruction register, it will do seemingly random stuff and cough up a hairball. Devious (the running program) is being fed into the instruction register; that's what makes it run. But a copy of Devious is being fed into Devious itself. That copy doesn't make it to the instruction register, instead it is analyzed by the running Devious.
MathDoofus wrote:then runs Oracle on Devious.
That's a shorthand way of saying "Devious contains a copy of Oracle's routines, and it feeds the input into those routines to see what Oracle would have said". In this case the input is the copy of Devious. So, its copy of Oracle's routines analyse Devious and says that Devious would do foo. But it tells Devious because those routines are part of Devious. Now that Devious knows what the prediction of its action is, it goes ahead and does the opposite, proving that Oracle isn't a very good oracle.

MathDoofus wrote:how is that Devious-as-argument itself get to take Oracle as an argument
It doesn't take Oracle "as an argument". It contains Oracle, like people contain hearts and livers.

Jose

So Devious, in order for my explanation to work, must (in addition to taking itself as an argument, which I'll call Devious-as-argument) contain a copy of Oracle's code so that it can--when it takes itself as an argument--feed Oracle to Devious-as-argument? Do I have that right?

### Re: Halting Problem

Posted: Thu Dec 28, 2017 11:31 pm UTC
MathDoofus wrote:So Devious, in order for my explanation to work, must (in addition to taking itself as an argument, which I'll call Devious-as-argument) contain a copy of Oracle's code so that it can--when it takes itself as an argument--feed Oracle to Devious-as-argument? Do I have that right?
Almost. Devious contains Oracle's code, so that it can feed its input (in this case a copy of Devious(which contains Oracle) to Oracle's code. It feeds Devious-as-argument to Oracle('s guts contained in Devious-as-program), gets the response Oracle would have given, and then (nyah nyah) does the opposite.

Jose

### Re: Halting Problem

Posted: Fri Dec 29, 2017 2:15 am UTC
ucim wrote:
MathDoofus wrote:So Devious, in order for my explanation to work, must (in addition to taking itself as an argument, which I'll call Devious-as-argument) contain a copy of Oracle's code so that it can--when it takes itself as an argument--feed Oracle to Devious-as-argument? Do I have that right?
Almost. Devious contains Oracle's code, so that it can feed its input (in this case a copy of Devious(which contains Oracle) to Oracle's code. It feeds Devious-as-argument to Oracle('s guts contained in Devious-as-program), gets the response Oracle would have given, and then (nyah nyah) does the opposite.

Jose