Halting Problem

[ucim]

(Altogether now...) Oh no it isn't!!

That's not contradiction, that's abuse!

Jose

[MathDoofus]

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.

[ucim]

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.

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

[MathDoofus]

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.

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)?

[ucim]

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.

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.

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

[MathDoofus]

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.

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.

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?

[ucim]

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

[MathDoofus]

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

Thank you! I’m going to read this again in the morning and think about it a bit longer before asking additional questions.

[MartianInvader]

I just stumbled on this thread, but it might be a good thought-excercise to construct Devious yourself. In other words, solve the following problem:

Suppose you have an Oracle O(p, i) that correctly tells you whether any program will halt given any input (you can imagine this as just a bunch of code you can copy-paste at will, if it helps). Using this Oracle, write a program D(p) that takes a program p as input, and runs forever if p halts when passed itself as input, and halts if p runs forever when passed itself as input.

People in this thread have already given example code of such a program, but doing it yourself would really help understand what the program is.

Next, answer the question: What happens when you run D(D)? Will it halt or run forever?