## Halting Problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

Oracle is already part of Devious, by definition. As in, that's how we defined Devious.

Devious takes its one argument (the number corresponding to the Devious program, in the case where we want a contradiction), and it sends that argument to Oracle twice. Once as the program Oracle will consider, and once as the input Oracle will consider for that program.

In the example I've used multiple times now, Devious(2) checks what Oracle(2,2) says will happen when program 2 is given 2 as input. Then Devious does the opposite (so if Oracle(2,2) is HALT, Devious(2) gets stuck in an endless loop). The 2 doesn't have anything to do with Oracle *or* Devious. In my example, program 2 just divides its input in half. Devious checks Oracle because that's what we said Devious does.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote:Oracle is already part of Devious, by definition. As in, that's how we defined Devious.

How can Devious make Oracle do anything if Devious isn't taking Oracle as an argument? If arguments don't matter, then why do we go to pains to emphasize that Oracle takes two arguments, one of which is a program and the other of which is input to that program? I feel like the goalposts are being constantly.

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

Oracle is part of the Devious program.

A program that takes an input and divides that input by three doesn't need three as an argument, because the three is always part of that program.

Similarly, Devious checks what Oracle says about its input. It doesn't need Oracle as an argument, because Oracle is always just part of the Devious program.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote:Oracle is part of the Devious program.

A program that takes an input and divides that input by three doesn't need three as an argument, because the three is always part of that program.

Similarly, Devious checks what Oracle says about its input. It doesn't need Oracle as an argument, because Oracle is always just part of the Devious program.

So Oracle is part of the instructions that Devious automatically executes? If so, what's the point of supplying Devious with an argument? Or, for that matter, requiring Oracle to take two arguments?

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

What is either program going to do without any arguments?

Oracle tells us what a particular program does when given a particular input. It needs both of those arguments in order to do anything at all.

Devious responds to what Oracle tells us the program corresponding to the one argument for Devious does when given that same argument as input. Devious then does the opposite of what Oracle tells us.

Devious(2) loops infinitely, because it looks at Oracle(2,2), which is HALT (because in my example, program 2 just takes it input and divides it in half, and then stops).

If program 4 takes its input and then adds 1 and then adds 1 and then adds 1 and then adds 1..., then Oracle(4,4) is LOOP, because program 4, when given the input 4, loops. Therefore Devious(4) halts, as it always does when Oracle returns LOOP.

Devious needs an argument because different arguments give different results.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote:What is either program going to do without any arguments?

Oracle tells us what a particular program does when given a particular input. It needs both of those arguments in order to do anything at all.

Devious responds to what Oracle tells us the program corresponding to the one argument for Devious does when given that same argument as input. Devious then does the opposite of what Oracle tells us.

Devious(2) loops infinitely, because it looks at Oracle(2,2), which is HALT (because in my example, program 2 just takes it input and divides it in half, and then stops).

If program 4 takes its input and then adds 1 and then adds 1 and then adds 1 and then adds 1..., then Oracle(4,4) is LOOP, because program 4, when given the input 4, loops. Therefore Devious(4) halts, as it always does when Oracle returns LOOP.

Devious needs an argument because different arguments give different results.

How do its different arguments lead to different results if it's Oracle taking the program and input? And, to get back to another question of mine that has never been answered directly by anyone, how is it that Devious can be said to show that Oracle can't exist if Oracle is inside Devious and acts not on Devious but on things that merely look like Devious?

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

MathDoofus wrote:
gmalivuk wrote:What is either program going to do without any arguments?

Oracle tells us what a particular program does when given a particular input. It needs both of those arguments in order to do anything at all.

Devious responds to what Oracle tells us the program corresponding to the one argument for Devious does when given that same argument as input. Devious then does the opposite of what Oracle tells us.

Devious(2) loops infinitely, because it looks at Oracle(2,2), which is HALT (because in my example, program 2 just takes it input and divides it in half, and then stops).

If program 4 takes its input and then adds 1 and then adds 1 and then adds 1 and then adds 1..., then Oracle(4,4) is LOOP, because program 4, when given the input 4, loops. Therefore Devious(4) halts, as it always does when Oracle returns LOOP.

Devious needs an argument because different arguments give different results.

How do its different arguments lead to different results if it's Oracle taking the program and input?
I just gave two examples, with different results.

And, to get back to another question of mine that has never been answered directly by anyone, how is it that Devious can be said to show that Oracle can't exist if Oracle is inside Devious and acts not on Devious but on things that merely look like Devious?
What do you mean "acts on"? Oracle doesn't act on anything, it just looks at a number for a program and a number for input, and it tells us what that program will do with that input (in the sense of telling us whether the program loops or halts).

When we give Oracle "2" as its first argument, it looks at program 2, which is the one that divides things in half.
When we give Oracle "2" as its second argument, it looks at what the program corresponding to its first argument does with "2" as input.
When we give Oracle "2" as both of its arguments, then, it looks at what program 2 does when it receives "2" as input.
Program 2 just divides its input in half and stops, so Oracle(2,2) is HALT. (In fact, Oracle(2,anything) is HALT, because as it turns out program 2 halts for every input.)

But some programs can either halt or loop based on the input. If program 5 takes its input and prints out the decimal expansion for one-third of that input, then program 5 halts for multiples of 3 and loops infinitely for other inputs. So Oracle(5,3) and Oracle(5,6) are both HALT, but Oracle(5,4) is LOOP, because program 5 takes input "4" and divides it by three and then starts printing "1.3333333333333...".

Devious(5), by definition, looks at Oracle(5,5), which is also LOOP. Then Devious(5) halts, because we defined Devious so that it does the opposite of what Oracle says. We defined Devious so it gives Oracle the same argument twice. So Devious doesn't "care" about the fact that Oracle(5,3) is different from Oracle(5,5). Devious can only look at Oracle(5,5).
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

### Re: Halting Problem

I hope to God this doesn't confuse the issue further:

You could make a different Devious machine, called 2Fast2Devious or whatever, that takes two different inputs, just like Oracle. Otherwise it would work the same. If we play around with this new machine and feed it two copies of its own program, we end up in the same place but without having to internally duplicate anything.

MathDoofus, would this be easier for you to work with? If not feel free to ignore this post.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

Beyond all the notation, which I find too difficult to follow, how can it be that the Devious program is permitted to examine Oracle's result and do the opposite? How does that show anything meaningful about whether Oracle is right in the sense that normal people might use the concept?

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

What do you mean, "How can it be?" We've already given many examples of things that look at other things' outputs.

Sure, we're sort of tricking Oracle into making a false statement, but there's nothing illegal about that.

It's the same thing we'd to with someone who claimed to be able to predict the future. Ask for a prediction about something we can change, and then change that thing.

Oracle is making a kind of prediction, and we design Devious to thwart that prediction.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote:What do you mean, "How can it be?" We've already given many examples of things that look at other things' outputs.

Sure, we're sort of tricking Oracle into making a false statement, but there's nothing illegal about that.

It's the same thing we'd to with someone who claimed to be able to predict the future. Ask for a prediction about something we can change, and then change that thing.

Oracle is making a kind of prediction, and we design Devious to thwart that prediction.

Ah. Let me abstract away the problem and see if I've got it.

I am a Devious Person and always do the opposite of what someone says I will do. I have a friend, Psychic Person, who says that he can, when given a scenario, always tell me (correctly) what's going to happen next. I am dubious regarding his claims.

The situation is this - I have baseballs in both of my hands. I ask Psychic Person which hand will throw the baseball. He says "left hand." Because I always do the opposite of what someone says I will do--and that's particularly true when a putative clairvoyant is involved--I throw the baseball with my right hand.

Is that an abstracted-away version of describing the relationship between Oracle and Devious?

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

Pretty much, yes.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote:Pretty much, yes.

Gotcha. So the halting problem isn't particularly intellectually interesting but for the fact that it shows that there's at least one program about which Oracle cannot (by definition or design) make a correct prediction as to whether that program will halt or not - do I have that right?

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

Well more broadly we can use it to prove that no program can be a halting oracle, because any alleged oracle is susceptible the same proof. Also, there are many other things that we can prove by contradiction, by showing that something would imply the existence of a halting oracle.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote:Well more broadly we can use it to prove that no program can be a halting oracle, because any alleged oracle is susceptible the same proof. Also, there are many other things that we can prove by contradiction, by showing that something would imply the existence of a halting oracle.

It seems like the halting problem might be related to (or susceptible to) the induction stuff that I've been wrestling with contemporaneously. In particular, and this will of course sound naive, Oracle says "x" and Devious says "x + 1." Maybe there's also some relationship between the halting problem and the diagonalization proof, which (I think) says that the set of real numbers is larger than the set of natural numbers because Devious can always create a number not on the list by using the diagonals of the existing list. So the diagonalization proof is also a proof-by-contradiction, I think.

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

Yeah, the main similarity is that they're both proofs by contradiction. Another similarity, which is common in many nonexistence proofs, is that we get the contradiction by looking at one proposed solution and showing that it isn't really a solution. Then we notice or show that the argument doesn't depend on the particular proposed solution, but rather works equally for any such proposal. Therefore, *nothing* with those characteristics can exist.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote:Yeah, the main similarity is that they're both proofs by contradiction. Another similarity, which is common in many nonexistence proofs, is that we get the contradiction by looking at one proposed solution and showing that it isn't really a solution. Then we notice or show that the argument doesn't depend on the particular proposed solution, but rather works equally for any such proposal. Therefore, *nothing* with those characteristics can exist.

I see. And although the Devious program example is somewhat idiotic and definitely unsatisfying, it does defeat the claim that we could (ever) design a program that, in each and every case, tells us whether some program running some input will halt or not. Is that right?

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3364
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

### Re: Halting Problem

It's somewhat like countering a claim of "I've invented a Perpetual Motion Machine, that works via <whatever method this particular PMM apparently uses> and powers an external device!" with a rebuttal that neatly disposes of the other impractical PMM machines yet to be 'invented'.

(And I'm not sure I'd call Devious idiotic. It does a job and (with some other internal test than Oracle, or else Oracle just being a test of something else) it could be a perfectly cromulant program for a purpose other than weeding out any such fallacious claim.)

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

### Re: Halting Problem

No program, Oracle or otherwise, is entitled to special-case treatment that makes sure it's always the one with the ultimate right to react, in preference to anything else. In fact, the formal definition of the "programs" used in this context requires that if something exists as a program, it must be possible to construct an additional program that embeds the first one as a component, and the very reason for embedding it is so that at least in that particular case, the encapsulating program is entitled to the right to react to whatever its component program says. Having that right to react, combined with the assurance that any program that purports to be an Oracle must (by definition) reach a guaranteed halt in every case, is what ensures the Devious program would be able to say "okay, we're back, now do the opposite" and prove the contradiction.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

I've spent the past couple of days thinking about this problem. What I'm still confused about are the different levels of programs, input, etc. When Oracle is running within Devious, how can we say that Oracle decides (or doesn't) decide anything about Devious (at the outermost level) will or won't do? That's what I'm finding difficult to grasp; the setup seems very convoluted.

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3364
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

### Re: Halting Problem

I'm not sure I understand your question. But perhaps it'd be like asking you to give me a number from one to fifty two, you say twelve, then I'm dealing out that number of cards before announcing (to the world in general) the eight of diamonds.

If you say twelve then (with that precise pack setup, which one presumes you don't have knowledge of) I'm always going to say 8/D, and any other number gives a different card (consistently so, given consistency of initial shuffle), but you don't tell me what card I will reveal (you don't decide that, you just prompt me as to which direction my choice will go, my choice being limited to your unknowing guidance and my own unrevealed initial card shuffle), and it's not really aimed to affect you back again in this example.

Though, through the virtualisation of "if I were to ask you what you would say if I were to ask you what you would say ..., then what would you say?" the Devious asking Oracle about Devious (asking Oracle about Devious (asking Oracle about Devious)) potential1 does put one in mind of being an observer as well as a volounteer participant in the Devious's, little mind-games stage act. But that isn't the same "you", nor (in Devious/Oracle cases) multiple running copies, merely the idea of nested dependencies, soon proved as impossible to be correctly imagined.

Not sure if that even answers the question I think you asked, though.

1 Though we don't actually recurse, as mentioned, because we are told that Oracle has a method that doesn't risk actually running its asked-about program and invoking the unhalting loop. And top-layer Devious just has to contradict Oracle's next-layer 'infallable guess' about Devious, with increasing layers adding nothing to (nor wholly removing) the contradictions.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: Halting Problem

Big post, but I wanted to take a crack at explaining this and clearing up some of your problems. Let me know if and when something confuses you.

One thing to note is that programs by their very nature are required to give the same output when fed the same input, every time, without fail. Oracle isn't allowed to "change its mind" about Devious' halting state after Devious halts or doesn't. This is an important part of how Devious tricks the Oracle: by having Oracle evaluate Devious as part of Devious, Devious gets to see what Oracle's immutable opinion is and then react to it. It's just like your psychic person predicting what hand you'll open and then you reacting to that prediction by opening the other hand. The psychic doesn't get to say "oh, I meant the other hand". He's just wrong.

The reason we need all the convoluted layers is because Devious isn't allowed to have a copy of itself hardcoded inside itself. After all, to write the program, you'd first need to know the code for it to write inside the program, but you don't have that code yet because you haven't written the program. So how do we get Devious to run Oracle on itself? The trick to get around this is to write Devious to take any code as input, and then feed it the code for itself once that code is written. That's where all the layers business comes from: we're working through the problem that it's very hard to get code to talk about itself. It's not as simple as asking the psychic "what hand am I going to open?", because programs aren't allowed to say "I". We weasel around this by having the program ask "what hand is this code going to open?" and have that code happen to be an exact copy of the original program.

More precisely, we make Devious ask Oracle "What happens when <this code> is fed itself as input?" (where we'll replace "<this code>" with the input code that Devious is fed). That's an innocent enough question usually, and Oracle might get it right most of the time. But when Devious is fed itself as input, it asks Oracle "What happens when Devious is fed itself as input?". In other words, Oracle is being asked about the very code that's running! (And we've done this "legally", not by hardcoding Devious inside itself.) And Oracle has to give the same answer here as it would for the program that's currently running, because programs have to give the same output when you feed them the same input. So Devious gets to hear Oracle's answer about itself and react to it by proving it wrong, and there's nothing that Oracle, which is just a program that receives inputs and returns outputs, can do about it. It can't go "I know I said 'doesn't halt', but the outer one clearly just halted, so I'm changing my mind.". It's just wrong.

This means that Oracle does not solve the halting problem, because it gets it wrong at least once. But this argument is pretty general: it works no matter what program Oracle is. So really, no program solves the halting problem. That's not to say that there aren't programs that get close. I don't know a lot about computer science, but I'm sure there are semi-Oracles that can correctly analyze vast swaths of programs. But no proposed Oracle can be right about every program, and that's the bar the halting problem sets.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

Cauchy wrote:Big post, but I wanted to take a crack at explaining this and clearing up some of your problems. Let me know if and when something confuses you.

This is a helpful attempt - thank you.

Cauchy wrote:
One thing to note is that programs by their very nature are required to give the same output when fed the same input, every time, without fail. Oracle isn't allowed to "change its mind" about Devious' halting state after Devious halts or doesn't. This is an important part of how Devious tricks the Oracle: by having Oracle evaluate Devious as part of Devious, Devious gets to see what Oracle's immutable opinion is and then react to it. It's just like your psychic person predicting what hand you'll open and then you reacting to that prediction by opening the other hand. The psychic doesn't get to say "oh, I meant the other hand". He's just wrong.

How does Devious "see" what Oracle's immutable opinion is and react to it? I have difficulty keeping track of the various layers of Devious. Is Devious defined (not sure this is the right verb) to do the opposite of what Oracle returns? If so, how and where (i.e., does Devious have some set of instructions that differs from "have Oracle run two copies of Devious"?)?

Cauchy wrote:
The reason we need all the convoluted layers is because Devious isn't allowed to have a copy of itself hardcoded inside itself. After all, to write the program, you'd first need to know the code for it to write inside the program, but you don't have that code yet because you haven't written the program. So how do we get Devious to run Oracle on itself?

I don't understand the above at all - isn't Oracle essentially hard-coded inside Devious? Why can't Devious be hard-coded inside Devious? I don't know whether these questions are material, but I thought I'd ask them.

Cauchy wrote:
The trick to get around this is to write Devious to take any code as input, and then feed it the code for itself once that code is written. That's where all the layers business comes from: we're working through the problem that it's very hard to get code to talk about itself. It's not as simple as asking the psychic "what hand am I going to open?", because programs aren't allowed to say "I". We weasel around this by having the program ask "what hand is this code going to open?" and have that code happen to be an exact copy of the original program.

OK - so is it that you have to feed a program a copy of itself to get a program to opine on a program?

Cauchy wrote:
More precisely, we make Devious ask Oracle "What happens when <this code> is fed itself as input?" (where we'll replace "<this code>" with the input code that Devious is fed). That's an innocent enough question usually, and Oracle might get it right most of the time. But when Devious is fed itself as input, it asks Oracle "What happens when Devious is fed itself as input?". In other words, Oracle is being asked about the very code that's running! (And we've done this "legally", not by hardcoding Devious inside itself.) And Oracle has to give the same answer here as it would for the program that's currently running, because programs have to give the same output when you feed them the same input. So Devious gets to hear Oracle's answer about itself and react to it by proving it wrong, and there's nothing that Oracle, which is just a program that receives inputs and returns outputs, can do about it. It can't go "I know I said 'doesn't halt', but the outer one clearly just halted, so I'm changing my mind.". It's just wrong.

What I'm now struggling with is how all of this works (and I'm also struggling with how to analyze it (i.e., how to think about it). Oracle is set up so that it takes two arguments - one argument is a program and the other argument is input to that program. Is that much correct?

Devious takes only argument, but it also gets to have a copy of Oracle inside itself? That's hard for me to follow.

And, when Devious takes Oracle as an argument, Devious sends to Oracle (because Oracle takes two arguments) two copies of Devious? But do those copies of Devious being sent to Oracle themselves take one argument apiece?

Finally, what's it mean (i.e., how am I supposed to analyze/step through) when Devious asks Oracle what happens when Devious (the program) takes Devious (the input) as input? The problem has so many layers that I can't unwind them.

The examples above involving numbers (I realize that those examples aren't yours) don't make any sense to me at all (nor do the examples involving analogies to physical items like boxes, machines, etc. - those add only another layer of confusion because I have to use mental energy to relate them back to the problem!), but your prose-heavy explanation was very good as far as it went!

ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Halting Problem

MathDoofus wrote:Why can't Devious be hard-coded inside Devious?
Because then it wouldn't be Devious. It would be a different program.

You can have Oracle (represented as [Oracle])
You can have Devious, which contains Oracle: [somestuff[Oracle]morestuff]. We can represent it as [Devious]
But... if you want [somestuff[Devious]morestuff], you can write it, but you can't represent it as [Devious]. It's "bigger".

MathDoofus wrote:OK - so is it that you have to feed a program a copy of itself to get a program to opine on a program?
You always feed copies of programs into analysis programs to get them to opine on the subject program. It's just that in this case, the copy in question happens to be a copy of the analysis program itself.

MathDoofus wrote:Devious takes only argument, but it also gets to have a copy of Oracle inside itself? That's hard for me to follow.
Consider a program double() that doubles a number (and has one input), and another program add() that adds two numbers (and thus, has two inputs). If double() is implemented using add(), it simply feeds the same input twice to add.

double(input)
. output(result);
}

Same thing happens here.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

gmalivuk
GNU Terry Pratchett
Posts: 26412
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

Every complex program has smaller parts inside it, and part of Devious is Oracle.

If you think of them written in some programming language, then Devious is just the same program as Oracle, but with a few lines of code before and after all the lines of Oracle.

If you think of them as books, then Devious is an edition of Oracle with a prologue and epilogue. But the original Oracle still exists, as do other books that include Oracle with different prologues and epilogues, as do books that are actually anthologies with Oracle as just one small chapter, and so on.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

ucim wrote:Consider a program double() that doubles a number (and has one input), and another program add() that adds two numbers (and thus, has two inputs). If double() is implemented using add(), it simply feeds the same input twice to add.

double(input)
. output(result);
}

Same thing happens here.

Jose

Jose, thank you for this - but I don't know any code or pseudo-code.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote:Every complex program has smaller parts inside it, and part of Devious is Oracle.

If you think of them written in some programming language, then Devious is just the same program as Oracle, but with a few lines of code before and after all the lines of Oracle.

So why do we distinguish between arguments and programs in our setup if one program (Devious) gets to use Oracle without taking in Oracle as an argument? I find that terribly confusing.

ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Halting Problem

Ok, imagine a box that adds two numbers. It has two doors in, and one door out. If a three and a five go in, an eight comes out. And note also that a copy of a three is just as good as an "actual" three. (Copy boxes are on sale at Staples).

Imagine another box, that doubles a number. If a seven walks in, a fourteen walks out. We don't know how either box "works", but it does. Now, what if we had to make our own "double" box. We could do it by putting a copier next to the front door, and putting the add box right after the copier. Whatever comes in gets copied, and the original and the copy get shoved into the add box. Whatever comes out of the add box, we kick out the back door. Put a roof on it and we have our own "double" box.

So, our double box has one input, but uses an add box that has two inputs. It manages that by copying its input, which is perfectly legit.
Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

ucim wrote:Ok, imagine a box that adds two numbers. It has two doors in, and one door out. If a three and a five go in, an eight comes out. And note also that a copy of a three is just as good as an "actual" three. (Copy boxes are on sale at Staples).

Imagine another box, that doubles a number. If a seven walks in, a fourteen walks out. We don't know how either box "works", but it does. Now, what if we had to make our own "double" box. We could do it by putting a copier next to the front door, and putting the add box right after the copier. Whatever comes in gets copied, and the original and the copy get shoved into the add box. Whatever comes out of the add box, we kick out the back door. Put a roof on it and we have our own "double" box.

So, our double box has one input, but uses an add box that has two inputs. It manages that by copying its input, which is perfectly legit.
Jose

OK. That much I can follow. Thank you.

ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Halting Problem

So now, there's a box called Oracle, with two inputs, one labeled "program plans" and the other labeled "input data". (The plans for) a program walks in along with the input data we want to pretend to feed it. This gets examined by a doctor (or somebody who plays one on TV) and then a carnival barker walks out, reading what's on his card. This will be either "Come see the program stop!" or "Come see the program loop!", depending on what Oracle thinks the program would do with the data.

It's the future, so the doctors, lawyers, and carnival barkers are all robots; since in the future everything has been replaced by robots. (We're just their pets.) But since they are robots, there are plans for them on the internet; this is important because we can only examine plans, not actual running robots. (The plans will stand still during the exam; an actually running program would poke the doctor in the eye and then call his lawyer). We can download the plans for Oracle; the instructions include the plans for the doctor, the carnival barker, and a bunch of other important stuff. But, they are just plans; they allow us to figure out how to build one.

We do, and then we deviously surround it with a bigger box. This bigger box has one entrance, helpfully labeled "input". It has one exit, labeled "nyah nyah nyah". Sitting inside our deviously bigger box is an actual Oracle, built from the plans we downloaded (from the internet of course!). This Oracle has two inputs, so we put a copy machine at our front door and thus can feed the same slop to each of the Oracle's gaping maws. At the back end of the Oracle, we have a (robotic, of course) Ninja, who slays the carnival barker and takes his cue card. If the card says it would stop, then the ninja calculates the last digit of pi. (Not being very math savvy, he never finishes.) If the card says it would loop, the ninja himself exits and says "Come see the program stop!"

This "bigger box" we call "Devious". We upload the plans for Devious to the internet, where we win all teh internetz and bask in glory.

Our devious plan: to feed the plans for Devious into our actual Devious, inside of which it will be copied and fed into each of the actual Oracle's pie holes.

Essentially, we'll be asking whether the Oracle thinks that the Devious program would stop if it were fed the plans for Devious as data. But Devious is going to reverse Oracle's answer, and then do that (opposite) thing. This guarantees that Oracle will be wrong.

But by definition, Oracle cannot be wrong. Therefore Oracle cannot exist.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

Let me explain what I (think that I) get and everyone can fill in the gaps. Thanks to all for their help so far.

We have a program called Oracle. Oracle, we say, must do two things: (1) it must itself halt and (2) it must tell us (correctly) if any arbitrary program P will halt when that program (P) is given some arbitrary input, i. I'll use the notation O(P, i) to show that Oracle is doing something with P and i.

We have a second program called Devious. There are a handful of background principles about Devious that an observer must know. The first is that Devious uses Oracle. Second, Devious always does the opposite of what Oracle returns (with the result that if O(P, i) -> YES, IT HALTS, then D will enter into an infinite loop, and vice versa). Devious takes only one argument, a program.

So, moving forward, we have Devious and Oracle working together:

D(P)

D(D) *Devious's one argument, a program, is a copy of itself in this case.

O(D, D) *Devious runs Oracle and gives Oracle two copies of Devious, one as Oracle's program and the other as Oracle's input

Can someone help me figure out what happens next? Does Oracle itself get stuck in an infinite loop, or does Devious actually get to the do-the-opposite stage with respect to Oracle?

ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Halting Problem

MathDoofus wrote:Can someone help me figure out what happens next? Does Oracle itself get stuck in an infinite loop, or does Devious actually get to the do-the-opposite stage with respect to Oracle?
What happens next is a contradiction.

Oracle cannot loop. That's part of the magic of Oracle. It always gives an answer - the right answer - in finite time.

So Tevye sits there, considering:

On the one hand, Devious can loop, but the only way it loops is if Oracle says it won't. That would make Oracle wrong, so that can't happen.

On the other hand, Devious can say "yes it halts", but it will only do that if Oracle says it loops. Again, Oracle is never wrong, so that can't happen.

On the other hand... No! There is no other hand! There are no other possibilities. So, whatever led up to this conundrum cannot be, whether it be a program that does what Oracle does, or a daughter that turns her back on her family's faith and marries a Cossak. Only in this case there is no Golde.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

PM 2Ring
Posts: 3638
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

### Re: Halting Problem

MathDoofus wrote:Can someone help me figure out what happens next? Does Oracle itself get stuck in an infinite loop, or does Devious actually get to the do-the-opposite stage with respect to Oracle?

Oracle does NOT run Devious, it analyzes it to see how it would behave if passed the given data, which just happens to be a copy of Devious. If Oracle ran the program you pass it then it would have to wait forever if that program doesn't halt. Which would mean that Oracle itself wouldn't halt in that case. But we've been told that Oracle always halts, so its analysis process cannot involve running the program you pass it.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

MathDoofus wrote:Let me explain what I (think that I) get and everyone can fill in the gaps. Thanks to all for their help so far.

We have a program called Oracle. Oracle, we say, must do two things: (1) it must itself halt and (2) it must tell us (correctly) if any arbitrary program P will halt when that program (P) is given some arbitrary input, i. I'll use the notation O(P, i) to show that Oracle is doing something with P and i.

We have a second program called Devious. There are a handful of background principles about Devious that an observer must know. The first is that Devious uses Oracle. Second, Devious always does the opposite of what Oracle returns (with the result that if O(P, i) -> YES, IT HALTS, then D will enter into an infinite loop, and vice versa). Devious takes only one argument, a program.

So, moving forward, we have Devious and Oracle working together:

D(P)

D(D) *Devious's one argument, a program, is a copy of itself in this case.

O(D, D) *Devious runs Oracle and gives Oracle two copies of Devious, one as Oracle's program and the other as Oracle's input

Can someone help me figure out what happens next? Does Oracle itself get stuck in an infinite loop, or does Devious actually get to the do-the-opposite stage with respect to Oracle?

Would someone be able to help me step through what happens next given my description above? I'd like to shore up my understanding of this proof. Thank you.

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3364
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

### Re: Halting Problem

The internal Oracle (that Devious uses) proclaims something. Acting upon its unknown but claimed-perfect mechanism for working out what D(D) does.

Devious then acts upon this information, via its legitimate coding, to do make the actual D(D) do the opposite. Game over.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

Soupspoon wrote:The internal Oracle (that Devious uses) proclaims something. Acting upon its unknown but claimed-perfect mechanism for working out what D(D) does.

Devious then acts upon this information, via its legitimate coding, to do make the actual D(D) do the opposite. Game over.

So that's why the opening move is Devious(Devious), which is equivalent to Devious the program being given Devious as input.

Then, a layer below, Devious asks Oracle to evaluate (Devious, Devious), which in effect asks Oracle to opine on what Devious the program will do when it's given Deviois as input.

And it doesn't matter how Oracle actually attempts to answer this question because we've designed a Devious to do the opposite. So, at the top layer, Devious by definition does the opposite of whatever Oracle says. Is that right so far?

ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Halting Problem

MathDoofus wrote:So that's why the opening move is Devious(Devious), which is equivalent to Devious the program being given Devious as input.
Yup.

MathDoofus wrote:And it doesn't matter how Oracle actually attempts to answer this question because we've designed a Devious to do the opposite. So, at the top layer, Devious by definition does the opposite of whatever Oracle says. Is that right so far?
Yup. (Or almost yup. Devious does the opposite of whatever Oracle says that it would do. Oracle doesn't actually loop, but Devious can.)

The key is that this leads to a contradiction - an impossible scenario. So, the premises must be wrong. The only premise is that there is an Oracle that can answer the halting problem.

IF there is an Oracle that can answer the halting problem, THEN we reach a contradiction. Therefore, there cannot be such an Oracle, and thus the halting problem cannot be solved.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

Great! I think I may have (at least) a high-level understanding of both versions of the proof-by-contradiction. Let me summarize what I understand both of them to be and y'all can tell if each summary is good enough for our purposes. Thanks again to all of those who've helped me in this thread; I really appreciate your efforts to teach someone named "MathDoofus" (have I proved that the name is autological?) the elements of this proof.

We want to know if there's any computer (or computer program) that can tell us, when fed any arbitrary program and some input to that program, whether the program (with that input) will halt or not.

We accordingly create a program called "Oracle." Oracle takes two arguments--a program and some input to that program--and always does two things: (1) it halts (if it didn't halt, then it wouldn't be a useful oracle) and (2) it tells us (correctly) whether that particular program, when given that particular input, will halt or not.

But then we decide to see if Oracle really works in every possible case. To test Oracle, we create a second program called Devious.

Devious doesn't do much. It takes only one argument (a program) and, based on whether Oracle returns "DOES HALT" or 'DOESN'T HALT," Devious does the opposite.

But Devious can't do anything unless it tricks Oracle into evaluating Devious. Here's how we do that.

We call Devious and give Devious a copy of itself. Next, Devious uses (or calls) Oracle and, as Oracle's two argument, gives Oracle two copies of Devious (one as a program and other as input, although the distinction isn't that important).

This raises an important question, namely, what happens next:

One version of the proof (the simpler one) doesn't get into the weeds of what happens when Oracle evaluates Devious using Devious. Instead, it relies on the fact (using our premises) that, no matter what Oracle returns, Devious does the opposite. And the reason why this matters is because there's no difference (as a logical/proof matter) between the Devious that's sitting at the top layer and the two copies of Devious that are being evaluated by Oracle. Oracle--based on the way we've set up the proof--is invariably wrong about whether Devious halts or not, which shows that Oracle can't exist in the real world.

The other version of the proof does try to analyze (however superficially) what happens when Oracle evaluates Devious using Devious. Although I'm not clear on every single detail, the bottom line is that Oracle and Devious reach an impasse because Oracle must look to Devious but Devious must look to Oracle; the result is that Oracle never itself halts. Again, based on our premises, this shows that something with the properties of Oracle (i.e., that a useful Oracle must itself halt) can't exist in the real world.

Are the above summaries reasonably accurate and faithful to both versions of the proof?

ucim
Posts: 6351
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Halting Problem

Close.

MathDoofus wrote:We accordingly create a program called "Oracle."
We assume that such a program could be created. We then assume that we did create it. (This is a lot less work than actually creating such a program, especially since it will turn out to be impossible!). By following the consequences of Oracle's existence, we will find that it can't exist. (It's a good thing we discovered it before actually trying to create such a program, but perhaps we can still get some investors interested. )

MathDoofus wrote:But Devious can't do anything unless it tricks Oracle into evaluating Devious.
Devious can do stuff (if Oracle could actually exist). But the useful-to-us thing happens when we trick (the embedded) Oracle into evaluating Devious.

MathDoofus wrote:...when Oracle evaluates Devious using Devious...
"...when Oracle evaluates (a copy of) Devious from within (the actual running) Devious..." I think you have the right idea; I'm just trying to be more precise.

MathDoofus wrote: Oracle--based on the way we've set up the proof--is invariably wrong about whether Devious halts or not, which shows that Oracle can't exist in the real world.
Yup.

MathDoofus wrote:Oracle must look to Devious but Devious must look to Oracle
No. Or at least, I don't follow that version of the proof. Remember that the program being examined is not running at the time. It's just a copy of the plans for a program, and that copy can't "run" anything while it's being examined. (It's under anesthesia. )

The only important part is that IF {setup} THEN {contradiction} THEREFORE {setup can't happen}. That's how all proofs by contradiction work.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3364
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

### Re: Halting Problem

ucim wrote:That's how all proofs by contradiction work.

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

( Naw, only kidding. Insert ObPythonVideo here, though.)