Halting Problem

[MathDoofus]

1. The “willHalt” program halts for any input.
2. The return value of “willHalt” answers the question “Will the input program halt when run on the input data?”

Now, let us run “willHalt” by dragging onto it a program and a data file. The program is our new program, and the data file is *also* our new program.

If the “willHalt” program does what is claimed, then it will halt (by claim 1) and its return value (by claim 2) will answer the question “Will our program halt when run with itself as input data?”

So let us consider every possible outcome:

If “willHalt” runs forever with these inputs, then claim 1 was false.

If “willHalt” returns “true”, then we know, by looking at how our program is written, that our program will loop forever, so claim 2 is false.

If “willHalt” returns “false”, then we know, by looking at how our program is written, that our program will exit quickly, so claim 2 is false.

If “willHalt” returns something other than “true” or “false”, then claim 2 is false.

I am working through your example with pen and paper, and I'm comfortable with treating the willHalt program as a black box that does only the two things you've described (i.e., willHalt always halts and willHalt always correctly tell us whether a given program, with a particular set of input data, will halt or not).

What I don't get is how the program that's fed to willHalt works. Can you help with that?

[Qaanol]

I am working through your example with pen and paper, and I'm comfortable with treating the willHalt program as a black box that does only the two things you've described (i.e., willHalt always halts and willHalt always correctly tell us whether a given program, with a particular set of input data, will halt or not).

What I don't get is how the program that's fed to willHalt works. Can you help with that?

Sure. It is a short program, so I will write it again for easy reference:

Code: Select all

main(input: file) {
  if willHalt(program: file, data: file) {
    while true {}   // infinite loop
  }
} 

This program takes an input file, called “file”. Then it calls the “willHalt” program. The “willHalt” program takes two parameters which are both files. One is a program and one is a data file. We pass in “file” as the program, and we pass in “file” as the data file.

If “willHalt” return true, then our program goes into an infinite loop and never ends.

If “willHalt” returns false, then our program simply exits.

That’s all there is to it.

[MathDoofus]

Code: Select all

main(input: file) {
  if willHalt(program: file, data: file) {
    while true {}   // infinite loop
  }
}

This program takes an input file, called “file”. Then it calls the “willHalt” program. The “willHalt” program takes two parameters which are both files. One is a program and one is a data file. We pass in “file” as the program, and we pass in “file” as the data file.

If “willHalt” return true, then our program goes into an infinite loop and never ends.

If “willHalt” returns false, then our program simply exits.

That’s all there is to it.

This is my hangup. I can't keep straight how willHalt can be called by the very thing it's supposed to evaluate, and how all of that affects the ultimate result of willHalt (i.e., the second premise that willHalt always gives a correct answer as to whether a particular program and the input to that program will halt).

[Qaanol]

This is my hangup. I can't keep straight how willHalt can be called by the very thing it's supposed to evaluate, and how all of that affects the ultimate result of willHalt (i.e., the second premise that willHalt always gives a correct answer as to whether a particular program and the input to that program will halt).

Okay, there are two separate things going on:

(A) We run our program, passing in itself as input. When we do so, our program calls “willHalt”, which (the claim goes) will return either true or false. Then our program either loops forever or exits.

(B) We drag our program onto “willHalt” as both program and data file. When we do so (the claim goes) “willHalt” will return either true or false.

The claim, furthermore, is that if our program exits in (A), then “willHalt” returns “true” in (B). And if our program loops forever in (A), then “willHalt” returns “false” in (B). That’s what it means for “willHalt” to solve the halting problem.

So far so good.

However, we run “willHalt” with the same inputs in (A) and (B). So when we call “willHalt” in (A), we expect to get the same answer as in (B).

But, by construction, our program in (A) will loop forever exactly when “willHalt” returns “true”, which means (B) is supposed to return “false” because our program does not halt.

Similarly, our program in (A) will exit exactly when “willHalt” returns “false”, which means (B) is supposed to return “true” because our program does halt.

[madaco]

Code: Select all

main(input: file) {
  if willHalt(program: file, data: file) {
    while true {}   // infinite loop
  }
} 

This program takes an input file, called “file”. Then it calls the “willHalt” program. The “willHalt” program takes two parameters which are both files. One is a program and one is a data file. We pass in “file” as the program, and we pass in “file” as the data file.

If “willHalt” return true, then our program goes into an infinite loop and never ends.

If “willHalt” returns false, then our program simply exits.

That’s all there is to it.

This is my hangup. I can't keep straight how willHalt can be called by the very thing it's supposed to evaluate, and how all of that affects the ultimate result of willHalt (i.e., the second premise that willHalt always gives a correct answer as to whether a particular program and the input to that program will halt).

The file being created here has a copy of the willHalt program embedded in it. It isn't referring to an external program called willHalt. There is a copy of willHalt inside of it.

The file which is created this way is just an ordinary file. You can do anything with it that you could could do to any other file. (Including passing it to any program that takes a file as input.)

Then you pass this file to (a separate copy of) the willHalt program as both arguments.

Then you see the contradiction implied by the assumption that a working willHalt program exists.

There needn't be a contradiction if the will Halt program doesn't work properly for some inputs.

And there are programs that act as imperfect willHalt programs. This process allows one to find a specific case where the given imperfect willHalt program doesn't work right.

(Either the imperfect willHalt won't halt, or it will give the wrong answer.)

[MathDoofus]

(A) We run our program, passing in itself as input. When we do so, our program calls “willHalt”, which (the claim goes) will return either true or false. Then our program either loops forever or exits.

(B) We drag our program onto “willHalt” as both program and data file. When we do so (the claim goes) “willHalt” will return either true or false.

So the willHalt program calls itself twice? I'm not trying to be dense, but I'm having trouble figuring out how the program and data file interact (if at all).

Edited

I have decided after putting pen to paper that there are too many interrelated parts for me to follow and that I won't ever be able to understand the proof-by-contradiction example involving the various programs. As I mentioned before, I have an abstract-symbol-related learning disability. Thanks to all for their efforts and their patience.

[Sizik]

Our program calls willHalt. willHalt takes a program and data determines if the program will halt if called with that data. It does not necessarily have to call the program do this, all that matters is that willHalt returns true or false correctly.

[MathDoofus]

Our program calls willHalt. willHalt takes a program and data determines if the program will halt if called with that data. It does not necessarily have to call the program do this, all that matters is that willHalt returns true or false correctly.

Is there a way to describe the proof by contradiction without three layers' worth of programs and input? I find that hopelessly confusing, particularly because all three layers appear to call themselves.

[gmalivuk]

A program calling itself isn't really that strange. You can do it on your own computer.

Here's what notepad++.exe looks like viewed inside Notepad++

[MathDoofus]

A program calling itself isn't really that strange. You can do it on your own computer.

Here's what notepad++.exe looks like viewed inside Notepad++

That's fair. What I'm having trouble making sense of is how the three layers interact, and why three layers are necessary.

[Sizik]

We want to prove that a halting oracle program can't exist, by showing that one existing would lead to a contradiction.
The naive way to do this is to write a program that calls the oracle on our program, and halts if the oracle predicts it won't, and loops forever otherwise.

However, we can't have our program pass itself to the oracle, since that would require our program to contain an exact copy of itself. Instead, we have our program take another program as an input, and pass that program on to the oracle, so then we can call our program with itself as an argument. Now that we've changed our program input, in order for our program to call the oracle properly to cause a contradiction, we then have to pass the argument we receive as both the program and data arguments to the oracle. Then, calling our program with itself as the input will end up contradicting what the oracle predicts it will do, so the oracle can't exist.

[Qaanol]

That's fair. What I'm having trouble making sense of is how the three layers interact, and why three layers are necessary.

I only see 2 layers.

We have a program “willHalt” which somebody claims can analyze programs to determine whether they halt with given input data.

And we concoct a program to trick it.

Our program just asks what “willHalt” says about our program, and then does the opposite.

This is a general-purpose trick. It is not limited to the halting problem. If somebody sends you a program and says, “This program can analyze other programs and determine whether they do XYZ with given input data,” then you can make a program to trick it. All your program has to do is ask what their program says about your program, and do the opposite.

You are forcing the other program to be wrong, by asking what the other program says and then doing something else.

Since you can always write such a program to trick any given analyzer, it follows that there is *no* program which can correctly analyze every program for every possible input, no matter *what* the analysis is supposed to determine.

[MathDoofus]

We want to prove that a halting oracle program can't exist, by showing that one existing would lead to a contradiction.
The naive way to do this is to write a program that calls the oracle on our program, and halts if the oracle predicts it won't, and loops forever otherwise.

However, we can't have our program pass itself to the oracle, since that would require our program to contain an exact copy of itself. Instead, we have our program take another program as an input, and pass that program on to the oracle, so then we can call our program with itself as an argument. Now that we've changed our program input, in order for our program to call the oracle properly to cause a contradiction, we then have to pass the argument we receive as both the program and data arguments to the oracle. Then, calling our program with itself as the input will end up contradicting what the oracle predicts it will do, so the oracle can't exist.

Let me see if I get this (I don't know any code, so the pseudo-code that others have written goes over my head).

We pretend that there's an oracle program that will (1) tell us whether any particular program that we feed to it will halt and (2) itself (i.e., the oracle) halt.

If we could, we'd feed the oracle program a devious program that, if the oracle said that the devious program would halt, the devious program would do the opposite and loop infinitely. Similarly, if the oracle said that the devious program would loop infinitely, then the devious program would halt.

But there's some reason that the thought experiment can't be designed that way? Is it because the devious program isn't allowed to "react" (that's a bad word, I know) to what the oracle does post hoc?

[ConMan]

We want to prove that a halting oracle program can't exist, by showing that one existing would lead to a contradiction.
The naive way to do this is to write a program that calls the oracle on our program, and halts if the oracle predicts it won't, and loops forever otherwise.

However, we can't have our program pass itself to the oracle, since that would require our program to contain an exact copy of itself. Instead, we have our program take another program as an input, and pass that program on to the oracle, so then we can call our program with itself as an argument. Now that we've changed our program input, in order for our program to call the oracle properly to cause a contradiction, we then have to pass the argument we receive as both the program and data arguments to the oracle. Then, calling our program with itself as the input will end up contradicting what the oracle predicts it will do, so the oracle can't exist.

Let me see if I get this (I don't know any code, so the pseudo-code that others have written goes over my head).

We pretend that there's an oracle program that will (1) tell us whether any particular program that we feed to it will halt and (2) itself (i.e., the oracle) halt.

If we could, we'd feed the oracle program a devious program that, if the oracle said that the devious program would halt, the devious program would do the opposite and loop infinitely. Similarly, if the oracle said that the devious program would loop infinitely, then the devious program would halt.

But there's some reason that the thought experiment can't be designed that way? Is it because the devious program isn't allowed to "react" (that's a bad word, I know) to what the oracle does post hoc?

This relates a bit to my post in your induction thread. In particular, where I say that "Assume x" means "Let's jump into a universe where we know x is true".

For a proof by contradiction, we want to do the following:

1. Assume the thing we're trying to disprove - i.e. let's jump into a universe where we know the thing we want to prove is false. In the case of the Halting Problem, we're jumping into an imaginary universe where the Oracle machine exists.
2. Reach a contradiction - that is, prove something that cannot possibly be true.
3. Therefore, state that this universe cannot exist, and therefore our assumption cannot ever be true.

Sometimes, we might break a situation into a few different cases, and show that each of those cases leads to a contradiction, meaning that all possibilities lead to a contradiction. For example, in the case of the Halting Problem, we do this:

1. Assume that the Oracle machine exists (i.e. jump into a universe where it exists, call it universe 1).
2. Within this universe 1, we can write the Devious Program (which just runs the Oracle on itself and decides to do the opposite of what the Oracle says it should do).
3. Since the Devious Program is a program, it must either Halt or Not Halt.
4. Let's assume that it Halts. In other words, let's jump into a sub-universe in which the DP Halts (call it Universe 1A).
5. In this universe 1A, since the DP Halts, the Oracle can tell us that it halts.
6. But, still in universe 1A, the DP will see that the Oracle says that the DP halts.
7. As a result (still in 1A), the DP will decide to Not Halt.
8. But we already know that in 1A, the DP is supposed to Halt, but we've just shown it does Not Halt.
9. So the universe in which the DP Halts cannot exist.
10. So we jump back to universe 1, knowing that universe 1A is impossible, i.e. there is no universe in which the DP Halts.
11. Thus, we have to conclude that the DP does Not Halt.
12. But since it does Not Halt, the Oracle can tell us that it does Not Halt.
13. So when we run the DP, it will run the Oracle, and learn that it is expected to Not Halt. And hence it will Halt.
14. But we just said that there is no universe in which the DP Halts. Which means that the universe we're currently in cannot exist.
15. So universe 1 is impossible, and hence the thing we assumed about it is not true.
16. The assumption we used to create universe 1 was "The Oracle program exists", so that cannot be true, hence the Oracle does not exist.

[MathDoofus]

We want to prove that a halting oracle program can't exist, by showing that one existing would lead to a contradiction.
The naive way to do this is to write a program that calls the oracle on our program, and halts if the oracle predicts it won't, and loops forever otherwise.

However, we can't have our program pass itself to the oracle, since that would require our program to contain an exact copy of itself. Instead, we have our program take another program as an input, and pass that program on to the oracle, so then we can call our program with itself as an argument. Now that we've changed our program input, in order for our program to call the oracle properly to cause a contradiction, we then have to pass the argument we receive as both the program and data arguments to the oracle. Then, calling our program with itself as the input will end up contradicting what the oracle predicts it will do, so the oracle can't exist.

Let me see if I get this (I don't know any code, so the pseudo-code that others have written goes over my head).

We pretend that there's an oracle program that will (1) tell us whether any particular program that we feed to it will halt and (2) itself (i.e., the oracle) halt.

If we could, we'd feed the oracle program a devious program that, if the oracle said that the devious program would halt, the devious program would do the opposite and loop infinitely. Similarly, if the oracle said that the devious program would loop infinitely, then the devious program would halt.

But there's some reason that the thought experiment can't be designed that way? Is it because the devious program isn't allowed to "react" (that's a bad word, I know) to what the oracle does post hoc?

This relates a bit to my post in your induction thread. In particular, where I say that "Assume x" means "Let's jump into a universe where we know x is true".

For a proof by contradiction, we want to do the following:

1. Assume the thing we're trying to disprove - i.e. let's jump into a universe where we know the thing we want to prove is false. In the case of the Halting Problem, we're jumping into an imaginary universe where the Oracle machine exists.
2. Reach a contradiction - that is, prove something that cannot possibly be true.
3. Therefore, state that this universe cannot exist, and therefore our assumption cannot ever be true.

Sometimes, we might break a situation into a few different cases, and show that each of those cases leads to a contradiction, meaning that all possibilities lead to a contradiction. For example, in the case of the Halting Problem, we do this:

1. Assume that the Oracle machine exists (i.e. jump into a universe where it exists, call it universe 1).
2. Within this universe 1, we can write the Devious Program (which just runs the Oracle on itself and decides to do the opposite of what the Oracle says it should do).
3. Since the Devious Program is a program, it must either Halt or Not Halt.
4. Let's assume that it Halts. In other words, let's jump into a sub-universe in which the DP Halts (call it Universe 1A).
5. In this universe 1A, since the DP Halts, the Oracle can tell us that it halts.
6. But, still in universe 1A, the DP will see that the Oracle says that the DP halts.
7. As a result (still in 1A), the DP will decide to Not Halt.
8. But we already know that in 1A, the DP is supposed to Halt, but we've just shown it does Not Halt.
9. So the universe in which the DP Halts cannot exist.
10. So we jump back to universe 1, knowing that universe 1A is impossible, i.e. there is no universe in which the DP Halts.
11. Thus, we have to conclude that the DP does Not Halt.
12. But since it does Not Halt, the Oracle can tell us that it does Not Halt.
13. So when we run the DP, it will run the Oracle, and learn that it is expected to Not Halt. And hence it will Halt.
14. But we just said that there is no universe in which the DP Halts. Which means that the universe we're currently in cannot exist.
15. So universe 1 is impossible, and hence the thing we assumed about it is not true.
16. The assumption we used to create universe 1 was "The Oracle program exists", so that cannot be true, hence the Oracle does not exist.

I will respond further in the morning, but how do we disprove the existence of the oracle by the DP's running the oracle on itself? That seems like cheating. Isn't the point to have the oracle do something, as opposed to the DP having the final word by reacting to what the oracle says when the DP runs it?

[ConMan]

The Oracle is just a program. It takes an input, and gives an output. The DP is also a program, and it is allowed to run the Oracle program as part of its process.

(Small sidenote - it's very important that in this context, programs are always self-contained: they take an input at the start, they provide an output at the end, and nothing is allowed to interfere with them in the middle, unlike, say, a computer game which is constantly taking input from the player. Additionally, these programs *always* provide the same output when given the same input; there's no way to say that it does something different when you run it a second time with the same input.)

The thing is, that we have assumed that the Oracle program exists, and that given any program, it can definitively say either "This program halts with the given input", or "This program does not halt with the given input". So it acts as an ultimate source of truth on whether a particular program halts. And, as a program, other programs can give it an input and take its output to use in whatever way they see fit - just like you might take a list of numbers, punch them into a calculator and add them together, and then use that sum as the input for some other process.

Or to look at it another way, if the Oracle program exists, then it must be possible to write it as code. So it must be possible to take that code, and wrap the DP's code around it.

[MathDoofus]

The Oracle is just a program. It takes an input, and gives an output. The DP is also a program, and it is allowed to run the Oracle program as part of its process.

(Small sidenote - it's very important that in this context, programs are always self-contained: they take an input at the start, they provide an output at the end, and nothing is allowed to interfere with them in the middle, unlike, say, a computer game which is constantly taking input from the player. Additionally, these programs *always* provide the same output when given the same input; there's no way to say that it does something different when you run it a second time with the same input.)

The thing is, that we have assumed that the Oracle program exists, and that given any program, it can definitively say either "This program halts with the given input", or "This program does not halt with the given input". So it acts as an ultimate source of truth on whether a particular program halts. And, as a program, other programs can give it an input and take its output to use in whatever way they see fit - just like you might take a list of numbers, punch them into a calculator and add them together, and then use that sum as the input for some other process.

Or to look at it another way, if the Oracle program exists, then it must be possible to write it as code. So it must be possible to take that code, and wrap the DP's code around it.

So how does the DP's being designed doing the opposite of whatever the oracle says show that the oracle can't exist? My understanding throughout is that it's the oracle that must act last, and not the program that it's evaluating.

[gmalivuk]

Because if the oracle existed, we would have a contradiction. When we reach a false or impossible conclusion through valid logic, it means at least one premise is false.

The only new premise in the present line of reasoning is that the oracle could exist. Therefore, we conclude that the oracle can't exist

[MathDoofus]

Because if the oracle existed, we would have a contradiction. When we reach a false or impossible conclusion through valid logic, it means at least one premise is false.

The only new premise in the present line of reasoning is that the oracle could exist. Therefore, we conclude that the oracle can't exist

That much I understand, at least in part. Because when we assume that something is true, and that assumption leads to an absurdity, then under the law of the excluded middle, the thing that we assumed cannot possibly be true. What I am now struggling with is the interaction between the Oracle and the devious program.

[MathDoofus]

1. Assume that the Oracle machine exists (i.e. jump into a universe where it exists, call it universe 1).
2. Within this universe 1, we can write the Devious Program (which just runs the Oracle on itself and decides to do the opposite of what the Oracle says it should do).
3. Since the Devious Program is a program, it must either Halt or Not Halt.
4. Let's assume that it Halts. In other words, let's jump into a sub-universe in which the DP Halts (call it Universe 1A).
5. In this universe 1A, since the DP Halts, the Oracle can tell us that it halts.
6. But, still in universe 1A, the DP will see that the Oracle says that the DP halts.
7. As a result (still in 1A), the DP will decide to Not Halt.
8. But we already know that in 1A, the DP is supposed to Halt, but we've just shown it does Not Halt.
9. So the universe in which the DP Halts cannot exist.
10. So we jump back to universe 1, knowing that universe 1A is impossible, i.e. there is no universe in which the DP Halts.
11. Thus, we have to conclude that the DP does Not Halt.
12. But since it does Not Halt, the Oracle can tell us that it does Not Halt.
13. So when we run the DP, it will run the Oracle, and learn that it is expected to Not Halt. And hence it will Halt.
14. But we just said that there is no universe in which the DP Halts. Which means that the universe we're currently in cannot exist.
15. So universe 1 is impossible, and hence the thing we assumed about it is not true.
16. The assumption we used to create universe 1 was "The Oracle program exists", so that cannot be true, hence the Oracle does not exist.

This what I don't understand - my assumption (perhaps mistaken) is that the Oracle program must have the last move (i.e., it must say that whatever's been fed to it will halt or that what's been fed to it will loop forever). Is that assumption incorrect? If it is incorrect, then the whole exercise looks too cute because I get to observe which state the Oracle program is in and say, post hoc, "not that."

[jaap]

This what I don't understand - my assumption (perhaps mistaken) is that the Oracle program must have the last move (i.e., it must say that whatever's been fed to it will halt or that what's been fed to it will loop forever). Is that assumption incorrect?

That is correct. If you had a perfect Oracle program, you would be able to use it and it would always have to give the correct answer. The problem is that it would also have to give the correct answer for the Devious Program. It cannot, because the Devious Program is deviously constructed (by containing a copy of the Oracle program inside it) such that whichever answer the Oracle would give about it, it would be wrong. Therefore, there is no such perfect Oracle program. If you try to make one, however sophisticated it becomes, there would always be some Devious Program for which it would be wrong.

[MathDoofus]

This what I don't understand - my assumption (perhaps mistaken) is that the Oracle program must have the last move (i.e., it must say that whatever's been fed to it will halt or that what's been fed to it will loop forever). Is that assumption incorrect?

That is correct. If you had a perfect Oracle program, you would be able to use it and it would always have to give the correct answer. The problem is that it would also have to give the correct answer for the Devious Program. It cannot, because the Devious Program is deviously constructed (by containing a copy of the Oracle program inside it) such that whichever answer the Oracle would give about it, it would be wrong. Therefore, there is no such perfect Oracle program. If you try to make one, however sophisticated it becomes, there would always be some Devious Program for which it would be wrong.

Thank you! My next question is a quotation from someone else who (at one time, at least) had the same issue that I do:

Maybe I am missing something or maybe I am not, but I can't give in to the "circular reasoning" that lurks in the proof of the Halting Problem. In standard English, the solution goes like this... P has the task of predicting Q's output (or behavior). But Q has the final say in the matter and waits till P makes its prediction, after which Q conveniently adapts its behavior only to violate that prediction.
So, as I see it, P has to look at "Q AND Q's Input" in order to predict its behavior (or output). But Q's INPUT is P's OUTPUT. So, effectively, P has to look at "Q AND P's OUTPUT". But P's OUTPUT is obtained only by looking at "Q AND Q's Input". Back to square one! It's important to understand that by Q's INPUT I don't mean Q's parameter values; I mean information that Q eventually uses to behave the way it does.
P needs information which is obtained from Q, who in turn needs the "same" information from P. But according to the proof, that information is generated on the fly and P is given the credit (or discredit) for generating it. That information (i.e the prediction P makes) couldn't have been generated because P doesn't know Q's complete Input information, information which can come only AFTER P makes it's prediction (i.e the prediction itself).
Where exactly am I going wrong? -- Mohyneen Mehdi

Why is it that the devious program gets to look at the oracle program's output and then take the contrary position? How is that a proof that the oracle program can't possibly exist?

[MathDoofus]

We want to prove that a halting oracle program can't exist, by showing that one existing would lead to a contradiction.
The naive way to do this is to write a program that calls the oracle on our program, and halts if the oracle predicts it won't, and loops forever otherwise.

However, we can't have our program pass itself to the oracle, since that would require our program to contain an exact copy of itself. Instead, we have our program take another program as an input, and pass that program on to the oracle, so then we can call our program with itself as an argument. Now that we've changed our program input, in order for our program to call the oracle properly to cause a contradiction, we then have to pass the argument we receive as both the program and data arguments to the oracle. Then, calling our program with itself as the input will end up contradicting what the oracle predicts it will do, so the oracle can't exist.

This is exactly what I can't understand. Can someone please break down why the devious program--by doing the opposite of what the oracle says it will--is said to show by contradiction that the oracle can't exist? Also, what do "program and data arguments" mean? Finally, what's the difference (if any) between "calling" a program, taking a program as input, and passing a program?

[Soupspoon]

Why is it that the devious program gets to look at the oracle program's output and then take the contrary position? How is that a proof that the oracle program can't possibly exist?

It cares not that it is taking a contrary view. Its function is to check something, and do something if that check comes out one particular way. No individual element is devious (making any test on any data is not invalid, running into an infinite loop is valid) and there is also no syntactic reason not to put these things together (no-one has specified, for example, that infinite loops may only be containers of branching mechanisms and not contained by), so the program whose intimate operation we know is possible.

The program whose intimate operation we do not know, except in proposed outline, could use any kind of advanced programming phlobotium in its function (probably loop-state tracking that identifies when circumstances (program pointer, variable contents, registry states, polled system states, etc) are encountered identically to a prior iteration) and a few moments thought show that to do this job properly gives us a headache (e.g. at least some of the potentially loop-repeating variable contents must hold all the virtualised loop-repeating variable contents from the layer being tested, which contains knowledge of another layer being tested, etc).


Interestingly, what if our program was not contradicting itself, but supporting itself? Not "I am lying right now" but "I am currently telling the truth" (if the referenced test shows no halt, then do not halt oneself). At which point, in the turtles all the way down way that we have, do we even obtain the base state of the situation, thusly to propagate outwards as each inceptional layer reveals its fate to guide the fate of its progenitor. A similar problem, but instead of flip-flop paradox a creationless one.

[MathDoofus]

Why is it that the devious program gets to look at the oracle program's output and then take the contrary position? How is that a proof that the oracle program can't possibly exist?

It cares not that it is taking a contrary view. Its function is to check something, and do something if that check comes out one particular way. No individual element is devious (making any test on any data is not invalid, running into an infinite loop is valid) and there is also no syntactic reason not to put these things together (no-one has specified, for example, that infinite loops may only be containers of branching mechanisms and not contained by), so the program whose intimate operation we know is possible.

The program whose intimate operation we do not know, except in proposed outline, could use any kind of advanced programming phlobotium in its function (probably loop-state tracking that identifies when circumstances (program pointer, variable contents, registry states, polled system states, etc) are encountered identically to a prior iteration) and a few moments thought show that to do this job properly gives us a headache (e.g. at least some of the potentially loop-repeating variable contents must hold all the virtualised loop-repeating variable contents from the layer being tested, which contains knowledge of another layer being tested, etc).


Interestingly, what if our program was not contradicting itself, but supporting itself? Not "I am lying right now" but "I am currently telling the truth" (if the referenced test shows no halt, then do not halt oneself). At which point, in the turtles all the way down way that we have, do we even obtain the base state of the situation, thusly to propagate outwards as each inceptional layer reveals its fate to guide the fate of its progenitor. A similar problem, but instead of flip-flop paradox a creationless one.

This is gobbledygook to me. If the proof-by-contradiction method is simply that we can create a second program that (somehow) uses the oracle program, looks at what the oracle program declares, and does the opposite, then why do we need so many layers of programs and input?

[gmalivuk]

We need a couple layers because that's how we force a contradiction.

Devious does the opposite of what Oracle declares its input (a program we want to check for halting) to do. There's no contradiction there because nothing says or does two opposite things.

[Soupspoon]

There are a number of answers to that, some of which others have already covered at least in passing.

One way of putting it that might help you more might be that of disallowing "X=not(X)" directly, as an obvious "devious contrarian statement" that no logic should allow. Not as a "reverse whatever X is, then continue with the new version of X" statement (viable, and easily confused with this), but in the "in this reality X always is, and only is, what it forever is not" sense, like Russel's barber.

Instead, Y=not(X), X=Y ("this thing halts only if something does not halt", "that something is this thing") gets around any self-referential limitations by abdicating the references to a proxy.


But it has been put better (and differently) by others, really, and I'd rather not rewrite their words for their explanations, so I leave this to you as a feeble stop-gap. Especially as this does not directly answer what I still presume was the original question of this thread.

(PPE: Ah, gmalivuk came to the rescue...)

[MathDoofus]

We need a couple layers because that's how we force a contradiction.

Devious does the opposite of what Oracle declares its input (a program we want to check for halting) to do. Nothing in that is contradictory, because nothing is saying something and the opposite at the same time. We basically need to invoke Oracle twice in order to get it to say two (contradictory) things.

Why is it necessary to invoke Oracle twice? Here's how I'm currently understanding (or not) the proof by contradiction.

Imagine that we have a program called "Oracle." Oracle, in our thought experiment, must always do two things: (1) halt (i.e., there's no way for Oracle to loop indefinitely) and (2) tell us (correctly) whether some program that Oracle is evaluating will halt or not (I'll call the second thing "returning a result").

Now what's the second step, and what am I missing?

[gmalivuk]

Basically, a lot of this sort of thing depends on self-reference. Hence the mention of the liar's paradox ("This statement is false.") We often need something to refer to itself in order to get the contradiction.

We can't do that with one layer of nesting, because there's no contradiction:
1) Oracle takes some input and halts with the output "halts" or "doesn't halt".
2) Oracle takes Oracle as input and outputs "halts", because we know Oracle itself always halts and gives an answer. (If it didn't, it wouldn't be an oracle.)

But instead
1) Oracle takes some input and halts with the output "halts" or "doesn't halt".
2) Devious takes some input and halts if Oracle would say "doesn't halt" and doesn't halt if Oracle would say "halts".
3) Devious takes Devious as input and halts if Oracle would say "doesn't halt" and doesn't halt if Oracle would say "halts".
- This third line has the contradiction, because if Oracle always gives a true response we've forced it to be false. So Oracle must not always give a true response.

There's a bit more work to make sure the inputs are actually the same (otherwise it just halts with one input and doesn't halt with another, which isn't contradictory), but that's basically the shape of what's going on.

[MathDoofus]

Basically, a lot of this sort of thing depends on self-reference. Hence the mention of the liar's paradox ("This statement is false.") We often need something to refer to itself in order to get the contradiction.

We can't do that with one layer of nesting, because there's no contradiction:
1) Oracle takes some input and halts with the output "halts" or "doesn't halt".
2) Oracle takes Oracle as input and outputs "halts", because we know Oracle itself always halts and gives an answer. (If it didn't, it wouldn't be an oracle.)

OK, I see why when Oracle takes Oracle as input (whatever that means, and my guess is that the details don't matter for our purposes), Oracle (by definition) looks at Oracle and (1) declares that Oracle will halt and (2) itself halts. Is that right?

But instead
1) Oracle takes some input and halts with the output "halts" or "doesn't halt".
2) Devious takes some input and halts if Oracle would say "doesn't halt" and doesn't halt if Oracle would say "halts".
3) Devious takes Devious as input and halts if Oracle would say "doesn't halt" and doesn't halt if Oracle would say "halts".
- This third line has the contradiction, because if Oracle always gives a true response we've forced it to be false. So Oracle must not always give a true response.

There's a bit more work to make sure the inputs are actually the same (otherwise it just halts with one input and doesn't halt with another, which isn't contradictory), but that's basically the shape of what's going on.

This is where I'm lost. What input is Devious taking? Are Devious and Oracle working on the same input simultaneously?

[gmalivuk]

Devious is a program, which means it's also a string of characters or bits. When I say "Devious takes Devious as input", I mean it takes that string of characters or bits as input. Like when Notepad++ takes notepadd++.exe as input.

[MathDoofus]

But instead
1) Oracle takes some input and halts with the output "halts" or "doesn't halt".
2) Devious takes some input and halts if Oracle would say "doesn't halt" and doesn't halt if Oracle would say "halts".
3) Devious takes Devious as input and halts if Oracle would say "doesn't halt" and doesn't halt if Oracle would say "halts".
- This third line has the contradiction, because if Oracle always gives a true response we've forced it to be false. So Oracle must not always give a true response.

There's a bit more work to make sure the inputs are actually the same (otherwise it just halts with one input and doesn't halt with another, which isn't contradictory), but that's basically the shape of what's going on.

So, following (or trying to follow) the second half of your explanation, we need Oracle and Devious to reach opposite results regarding some third program (call it "Third")? Is that right? Oracle would need to declare that Third halts at the same time that Devious--by its design--guarantees that Third won't halt? I'm still confused, clearly.

[Xanthir]

Okay, now:

1. Recall Gmal's earlier post showing how you can interpret a program as a number, and even combine the program with a predefined input and then interpret the whole thing as a number. This is one way a program can take another program as input. (For example, we can say that it's how Oracle takes a program as input this way - by accepting a numeric argument.) (This isn't *directly* useful here in this proof, it's just a reminder that you can pass "programs" around as inputs to other programs.)

2. Oracle takes two arguments: a program to analyze, and an input for that program. It then does the HALT/LOOP determination just by analyzing the program+input. (Note: it does *not* run the program! Doing so would make Oracle infinite-loop if the input program infinite-looped. It just looks very carefully at the program and proves it with clever logic.)

3. So now we have Devious. Devious takes a program as its only input. It then calls Oracle, passing it the program as the first argument, and then the program again as the second argument. (Recall that, per point #1, we have ways of representing programs so that we can pass them as input to other programs.)
It then does the opposite of what Oracle returns - if Oracle returns "HALT", Devious will infinite-loop, if Oracle says "LOOP", then Devious will immediately stop. Devious thus looks something like:

Code: Select all

Program Devious (input someProgram):
    if Oracle(someProgram, someProgram) equals HALT:
        infinite loop!
    otherwise:
        stop immediately.


As you can see, this is a pretty simple program.

4. Now, recall again that we can represent programs as inputs for another program. In particular, we can represent Devious as an input to another program. Per Gmal's method, for example, say that we find the number representing Devious. (It's too large to easily list here, but it's not hard to compute.)

5. So now we call Devious(Devious), and get the contradiction. In line 2 of Devious's code, it calls "Oracle(Devious, Devious)". This has to return either HALT or LOOP. Let's assume it returns HALT, for the sake of argument. So Devious then infinite loops.

6. But that contradicts what the oracle just said! The whole point of calling "Oracle(Devious, Devious)" is to ask the question "if I were to call Devious(Devious), would it halt or loop?", and the Oracle said it would halt. But here, we just called Devious(Devious), and it looped!

7. If, in step 5, we assume that Oracle returns LOOP, then we get the same contradiction, just the other way around - Devious(Devious) will halt, but the Oracle tells us that Devious(Devious) will loop.

8. Thus, the Oracle can't be trusted for all inputs; it gives the wrong answer on Devious(Devious), at least, and might give the wrong answer for other inputs. We have no way of knowing!

[MathDoofus]

Okay, now:

1. Recall Gmal's earlier post showing how you can interpret a program as a number, and even combine the program with a predefined input and then interpret the whole thing as a number. This is one way a program can take another program as input. (For example, we can say that it's how Oracle takes a program as input this way - by accepting a numeric argument.) (This isn't *directly* useful here in this proof, it's just a reminder that you can pass "programs" around as inputs to other programs.)

2. Oracle takes two arguments: a program to analyze, and an input for that program. It then does the HALT/LOOP determination just by analyzing the program+input. (Note: it does *not* run the program! Doing so would make Oracle infinite-loop if the input program infinite-looped. It just looks very carefully at the program and proves it with clever logic.)

3. So now we have Devious. Devious takes a program as its only input. It then calls Oracle, passing it the program as the first argument, and then the program again as the second argument. (Recall that, per point #1, we have ways of representing programs so that we can pass them as input to other programs.)
It then does the opposite of what Oracle returns - if Oracle returns "HALT", Devious will infinite-loop, if Oracle says "LOOP", then Devious will immediately stop. Devious thus looks something like:

Code: Select all

Program Devious (input someProgram):
    if Oracle(someProgram, someProgram) equals HALT:
        infinite loop!
    otherwise:
        stop immediately.


As you can see, this is a pretty simple program.

4. Now, recall again that we can represent programs as inputs for another program. In particular, we can represent Devious as an input to another program. Per Gmal's method, for example, say that we find the number representing Devious. (It's too large to easily list here, but it's not hard to compute.)

5. So now we call Devious(Devious), and get the contradiction. In line 2 of Devious's code, it calls "Oracle(Devious, Devious)". This has to return either HALT or LOOP. Let's assume it returns HALT, for the sake of argument. So Devious then infinite loops.

6. But that contradicts what the oracle just said! The whole point of calling "Oracle(Devious, Devious)" is to ask the question "if I were to call Devious(Devious), would it halt or loop?", and the Oracle said it would halt. But here, we just called Devious(Devious), and it looped!

7. If, in step 5, we assume that Oracle returns LOOP, then we get the same contradiction, just the other way around - Devious(Devious) will halt, but the Oracle tells us that Devious(Devious) will loop.

8. Thus, the Oracle can't be trusted for all inputs; it gives the wrong answer on Devious(Devious), at least, and might give the wrong answer for other inputs. We have no way of knowing!

So it's not Oracle that we have to call on itself, but Devious? And Devious itself has Oracle built in somehow? And there's a third program that does something or other? Apologies for the barrage of questions, but I'm confused.

[gmalivuk]

Okay, now:

1. Recall Gmal's earlier post showing how you can interpret a program as a number, and even combine the program with a predefined input and then interpret the whole thing as a number. This is one way a program can take another program as input. (For example, we can say that it's how Oracle takes a program as input this way - by accepting a numeric argument.) (This isn't *directly* useful here in this proof, it's just a reminder that you can pass "programs" around as inputs to other programs.)

2. Oracle takes two arguments: a program to analyze, and an input for that program. It then does the HALT/LOOP determination just by analyzing the program+input. (Note: it does *not* run the program! Doing so would make Oracle infinite-loop if the input program infinite-looped. It just looks very carefully at the program and proves it with clever logic.)

3. So now we have Devious. Devious takes a program as its only input. It then calls Oracle, passing it the program as the first argument, and then the program again as the second argument. (Recall that, per point #1, we have ways of representing programs so that we can pass them as input to other programs.)
It then does the opposite of what Oracle returns - if Oracle returns "HALT", Devious will infinite-loop, if Oracle says "LOOP", then Devious will immediately stop. Devious thus looks something like:

Code: Select all

Program Devious (input someProgram):
    if Oracle(someProgram, someProgram) equals HALT:
        infinite loop!
    otherwise:
        stop immediately.


As you can see, this is a pretty simple program.

4. Now, recall again that we can represent programs as inputs for another program. In particular, we can represent Devious as an input to another program. Per Gmal's method, for example, say that we find the number representing Devious. (It's too large to easily list here, but it's not hard to compute.)

5. So now we call Devious(Devious), and get the contradiction. In line 2 of Devious's code, it calls "Oracle(Devious, Devious)". This has to return either HALT or LOOP. Let's assume it returns HALT, for the sake of argument. So Devious then infinite loops.

6. But that contradicts what the oracle just said! The whole point of calling "Oracle(Devious, Devious)" is to ask the question "if I were to call Devious(Devious), would it halt or loop?", and the Oracle said it would halt. But here, we just called Devious(Devious), and it looped!

7. If, in step 5, we assume that Oracle returns LOOP, then we get the same contradiction, just the other way around - Devious(Devious) will halt, but the Oracle tells us that Devious(Devious) will loop.

8. Thus, the Oracle can't be trusted for all inputs; it gives the wrong answer on Devious(Devious), at least, and might give the wrong answer for other inputs. We have no way of knowing!

So it's not Oracle that we have to call on itself, but Devious? And Devious itself has Oracle built in somehow? And there's a third program that does something or other? Apologies for the barrage of questions, but I'm confused.

What third program? There is no third program. There's just Oracle and Devious.

"someProgram" in Xanthir's post means any program you decide to use as input. In this case, we're using Devious itself as input.

(Also, I explained why calling Oracle on itself doesn't give a contradiction. We need to call Devious on itself to get the contradiction.)

[MathDoofus]

"someProgram" in Xanthir's post means any program you decide to use as input. In this case, we're using Devious itself as input.

(Also, I explained why calling Oracle on itself doesn't give a contradiction. We need to call Devious on itself to get the contradiction.)

Calling Oracle on itself doesn't result in a contradiction because we've defined Oracle that way, right?

I don't understand the process of calling Devious on itself and how that relates to showing that Oracle is wrong at the time that all of this stuff is happening, and not after. My apologies.

[Xanthir]

So it's not Oracle that we have to call on itself, but Devious?

Yeah.

And Devious itself has Oracle built in somehow?

Sure. Oracle is written in code as well, you can just put that code in there. There's no self-reference or anything; Oracle doesn't contain Devious in its own code.

And there's a third program that does something or other? Apologies for the barrage of questions, but I'm confused.

I didn't mention a third program. You just literally follow the steps I provided. If you call Oracle(Devious, Devious) (which is meant to answer the question "does Devious(Devious) HALT or LOOP?") it reports one thing, but when you actually run Devious(Devious), it does the opposite thing.

If the references are still tricking you into thinking there's some self-reference, try this sentence instead: If you call Oracle(NumberForDevious, NumberForDevious) (which is meant to answer the question "does Devious(NumberForDevious) HALT or LOOP?") it reports one thing, but when you actually run Devious(NumberForDevious), it does the opposite thing. No self-referencing at all - you've got the Oracle program, you've got the Devious program (which includes the Oracle program's code), and then the Devious program has a number associated with it. You're just passing that number around.

[MathDoofus]

So it's not Oracle that we have to call on itself, but Devious?

Yeah.

And Devious itself has Oracle built in somehow?

Sure. Oracle is written in code as well, you can just put that code in there. There's no self-reference or anything; Oracle doesn't contain Devious in its own code.

And there's a third program that does something or other? Apologies for the barrage of questions, but I'm confused.

I didn't mention a third program. You just literally follow the steps I provided. If you call Oracle(Devious, Devious) (which is meant to answer the question "does Devious(Devious) HALT or LOOP?") it reports one thing, but when you actually run Devious(Devious), it does the opposite thing.

If the references are still tricking you into thinking there's some self-reference, try this sentence instead: If you call Oracle(NumberForDevious, NumberForDevious) (which is meant to answer the question "does Devious(NumberForDevious) HALT or LOOP?") it reports one thing, but when you actually run Devious(NumberForDevious), it does the opposite thing. No self-referencing at all - you've got the Oracle program, you've got the Devious program (which includes the Oracle program's code), and then the Devious program has a number associated with it. You're just passing that number around.

I'm sorry; I can't follow code. Are you saying this:

Oracle is being used to decide whether Devious--when Devious calls Devious--will halt or loop infinitely. Devious has been written such that, when it calls itself, it will do the opposite of whatever Oracle decides about Devious-calling-itself. Is that what you're saying?

[Xanthir]

I'm sorry; I can't follow code.

Okay, that explains a lot of the difficulty. Lets go back to machines, which were briefly tried earlier in the thread.

1. We have some machines. You put material in one side, press the GO button, they do something internally, then pop a product out the other end. Most of the time; sometimes they explode instead. You want to find out when this'll happen so you can avoid accidentally exploding.

2. Machines, obviously, can also be disassembled. Instead of a fully constructed running machine, you can have a smaller crate of machine parts and assembly instructions; an IKEA box for the machine. It won't run in this state, obviously.

3. So now you build an Oracle machine. This takes an IKEA crate for a machine you want to analyze, and an input material. The Oracle machine then paws thru the IKEA crate, analyzing what the box contains, figures out how it'll react to the material, and tells you whether, when the crate's contents are assembled into a machine and fed this material, it'll produce some product or explode.

4. Now someone builds a Devious machine. The Devious machine is really big - it contains the Oracle machine inside of it. It also takes an IKEA create as its input. It duplicates the crate, then passes both crates to its internal Oracle machine. If the Oracle machine says COOL, the Devious machine explodes; if it says BOOM, the Devious machine outputs a happy face from its other end.

5. Now, take the Devious machine, and put an IKEA crate full of Devious machine parts into it. Does it explode, or not?

Impossible to have self-reference now - everything is a physical object. The process is:

1. The Devious machine receives the box of Devious parts.

2. It duplicates it, so now it has two boxes of parts.

3. Then it feeds both boxes to its internal Oracle machine.

4. The Oracle machine analyzes these boxes, and says COOL or BOOM. The Devious machine then explodes or prints a happy face, based on the result. Let's assume it says COOL.

5. As a result, the Devious machine explodes.

6. Thus, the Oracle machine must be flawed - it analyzed the Devious machine parts and said it wouldn't explode when fed another box of Devious machine parts, but we just fed a working Devious machine a box of Devious machine parts, and it exploded. (Or vice versa.)

[MathDoofus]

1. The Devious machine receives the box of Devious parts.

2. It duplicates it, so now it has two boxes of parts.

3. Then it feeds both boxes to its internal Oracle machine.

4. The Oracle machine analyzes these boxes, and says COOL or BOOM. The Devious machine then explodes or prints a happy face, based on the result. Let's assume it says COOL.

5. As a result, the Devious machine explodes.

6. Thus, the Oracle machine must be flawed - it analyzed the Devious machine parts and said it wouldn't explode when fed another box of Devious machine parts, but we just fed a working Devious machine a box of Devious machine parts, and it exploded. (Or vice versa.)

So Oracle is being fed--at the same time--two versions of Devious on which it reaches contrary results? I'm more confused than before. Can you explain using words only and not with a physical example or pseudo-code?