Halting Problem

[MathDoofus]

↶

They're just two inputs. The Oracle device takes two inputs. One *must* be a box of machine parts, the other can be *anything*.

OK. Why does Oracle take two inputs, and what's the significance?

Because Oracle's first input is a box of machine parts. Oracle wants to figure out what the machine will do if it's assembled. A machine's behavior can change based on what you feed it, tho - some inputs make it explode, others don't. So you have to give it an example input, so it can answer the question "If we assembled the machine in this box, and gave it this input, would it explode or not?".

Does this make sense so far?

Why do the machine and the input need to be separate? How about just giving the Oracle a machine and asking whether it'll blow up or not?

[MathDoofus]

At some point I have to believe that you're either trolling, or you have serious memory problems on top of math difficulties.

The first input to Oracle is the number of a program. The second input to Oracle is the input we give that program. Oracle(4,5) tells us what program number 4 does when it receives "5" as input.

I have admitted several times that I have a serious mental obstacle relating to the manipulation and understanding of non-language abstract symbols.

Devious(3) asks Oracle what would happen if we ran Devious on input 3. Devious(3) is then explicitly designed to do the opposite of what Oracle says would happen. Therefore Oracle can't possibly be right about what Devious does.
---
DeviousTable is designed to end up being a dresser if IkeaOracle says it should be a table, and end up being a table if IkeaOracle says it should be a dresser. Therefore IkeaOracle is sometimes wrong about boxes of furniture parts.

Why does Oracle take two arguments but Devious takes only one? I'm now confused about that.

[Xanthir]

↶
Why do the machine and the input need to be separate? How about just giving the Oracle a machine and asking whether it'll blow up or not?

Because

A machine's behavior can change based on what you feed it, tho - some inputs make it explode, others don't.

[MathDoofus]

↶
Why do the machine and the input need to be separate? How about just giving the Oracle a machine and asking whether it'll blow up or not?

Because

A machine's behavior can change based on what you feed it, tho - some inputs make it explode, others don't.

OK. That makes sense. So we're passing both a machine and some parts to Oracle every time that we use (invoke?) Oracle, yes?

[gmalivuk]

↶

They're just two inputs. The Oracle device takes two inputs. One *must* be a box of machine parts, the other can be *anything*.

OK. Why does Oracle take two inputs, and what's the significance?

Because Oracle's first input is a box of machine parts. Oracle wants to figure out what the machine will do if it's assembled. A machine's behavior can change based on what you feed it, tho - some inputs make it explode, others don't. So you have to give it an example input, so it can answer the question "If we assembled the machine in this box, and gave it this input, would it explode or not?".

Does this make sense so far?

Why do the machine and the input need to be separate? How about just giving the Oracle a machine and asking whether it'll blow up or not?

Because machines don't explode by themselves.

Boxes of furniture parts are assembled into particular pieces of furniture based on the instructions that also come in the box. You need both the instructions and the parts to end up with a piece of furniture.

Programs halt or don't halt depending on the input they're given. If a program is designed to divide its input by 3 and print the resulting number digit by digit, then input 6 results in an output of 2 and a halt, while input 5 results in an output of 1.666666666666... and no halt.

We can design Oracle to take one input, but it still has to interpret this input as a program together with input for that program. For example, we could have a different oracle that takes input 72 (which is 2²*3²) and tells us what program 2 does with input "2", but it's still answering a question about two things (a program and that program's input).

[MathDoofus]

We can design Oracle to take one input, but it still has to interpret this input as a program together with input for that program. For example, we could have a different oracle that takes input 72 (which is 2²*3²) and tells us what program 2 does with input "2", but it's still answering a question about two things (a program and that program's input).

OK, so Oracle must always take two arguments whenever it's used, yes? And those arguments are a machine and some loose parts?

[Xanthir]

↶

↶
Why do the machine and the input need to be separate? How about just giving the Oracle a machine and asking whether it'll blow up or not?

Because

A machine's behavior can change based on what you feed it, tho - some inputs make it explode, others don't.

OK. That makes sense. So we're passing both a machine and some parts to Oracle every time that we use (invoke?) Oracle, yes?

The second argument isn't *necessarily* machine parts. It's just some input you'd like to feed to the (currently disassambled, in a box) machine. It so happens that it will be another box of machine parts when we use it, yes, but it doesn't have to be.

In other words, say I have a LightsThingsOnFire machine that I just ordered. It's still in the box. I can pass the box to Oracle along with a block of iron, and Oracle will correctly report that this machine, if assembled and fed this block of iron, won't explode. On the other hand, if I pass Oracle the box along with a jug of gasoline, it'll correctly report that, if assembled and fed this jug of gasoline, the machine will explode.

This make sense so far?

[MathDoofus]

↶

↶
Why do the machine and the input need to be separate? How about just giving the Oracle a machine and asking whether it'll blow up or not?

Because

A machine's behavior can change based on what you feed it, tho - some inputs make it explode, others don't.

OK. That makes sense. So we're passing both a machine and some parts to Oracle every time that we use (invoke?) Oracle, yes?

The second argument isn't *necessarily* machine parts. It's just some input you'd like to feed to the (currently disassambled, in a box) machine. It so happens that it will be another box of machine parts when we use it, yes, but it doesn't have to be.

In other words, say I have a LightsThingsOnFire machine that I just ordered. It's still in the box. I can pass the box to Oracle along with a block of iron, and Oracle will correctly report that this machine, if assembled and fed this block of iron, won't explode. On the other hand, if I pass Oracle the box along with a jug of gasoline, it'll correctly report that, if assembled and fed this jug of gasoline, the machine will explode.

This make sense so far?

Yes, although to keep me less confused can we keep the two arguments consistent (i.e., machine and loose parts)?

[Xanthir]

↶
Yes, although to keep me less confused can we keep the two arguments consistent (i.e., machine and loose parts)?

Maybe. I'm reluctant to do this because you're talking about the first argument as a "machine", which sounds like you're meaning a fully-assembled one. This confusion between an assembled, working machine, and its loose parts, is precisely what was confusing you before.

What's confusing so far about my examples of the Oracle machine working on the LightsThingsOnFire box? I'll run thru examples again, you tell me if any of them confuse you:

* Feed Oracle a LightsThingsOnFire box of parts, and a block of iron => Oracle says "COOL"
* Feed Oracle a LightsThingsOnFire box of parts, and a jug of gasoline => Oracle says "BOOM"
* Feed Oracle a LightsThingsOnFire box of parts, and a PlaysSomeMusic box of parts => Oracle says "COOL"
* Feed Oracle a LightsThingsOnFire box of parts, and another LightsThingsOnFire box of parts => Oracle says "BOOM"

Do these all make sense? (The actual answer the Oracle gives doesn't matter here, just the concept of feeding it these things, and what it means for each.)

[MathDoofus]

↶
Yes, although to keep me less confused can we keep the two arguments consistent (i.e., machine and loose parts)?

Maybe. I'm reluctant to do this because you're talking about the first argument as a "machine", which sounds like you're meaning a fully-assembled one. This confusion between an assembled, working machine, and its loose parts, is precisely what was confusing you before.

What's confusing so far about my examples of the Oracle machine working on the LightsThingsOnFire box? I'll run thru examples again, you tell me if any of them confuse you:

* Feed Oracle a LightsThingsOnFire box of parts, and a block of iron => Oracle says "COOL"
* Feed Oracle a LightsThingsOnFire box of parts, and a jug of gasoline => Oracle says "BOOM"
* Feed Oracle a LightsThingsOnFire box of parts, and a PlaysSomeMusic box of parts => Oracle says "COOL"
* Feed Oracle a LightsThingsOnFire box of parts, and another LightsThingsOnFire box of parts => Oracle says "BOOM"

Do these all make sense? (The actual answer the Oracle gives doesn't matter here, just the concept of feeding it these things, and what it means for each.)

Makes sense so far except for the final example.

[Xanthir]

What's confusing about the fourth example that's not confusing about the third example? The two are, intentionally, almost identical.

[MathDoofus]

What's confusing about the fourth example that's not confusing about the third example? The two are, intentionally, almost identical.

I don't see why the fourth result should be BOOM.

[Xanthir]

Like I said, it doesn't matter. (I answered that way because I assume a machine that lights things on fire would contain some flammable material, perhaps a propane tank, and this would explode when fed to a running LightsThingsOnFire machine.)

[MathDoofus]

Like I said, it doesn't matter. (I answered that way because I assume a machine that lights things on fire would contain some flammable material, perhaps a propane tank, and this would explode when fed to a running LightsThingsOnFire machine.)

Can we distinguish between machines and boxes containing the parts to build that machine? I just want to avoid any confusion.

[Soupspoon]

None of the things fed to that Oracle were Machines. There was always at least one Box Of Parts (the first one) that was not a Machine, but was there for the Oracle to study so as to consider what the Machine you could get would be like, and then a Something Else (which is the thing the Oracle would ponder feeding to <its idea of the Machine one could get from the first Box>) that in a couple of cases were Boxes Of Parts but immaterially so (except insofar as they affect the result, just as different non-BsOP affect the result).

[Xanthir]

Yeah. We do distinguish the two, *right now*, and that's important - the Oracle doesn't *actually* feed the example input to a machine, because that might explode it; it just analyzes the box of parts, and tells you whether it would explode if it were constructed and fed the example input.

[MathDoofus]

Yeah. We do distinguish the two, *right now*, and that's important - the Oracle doesn't *actually* feed the example input to a machine, because that might explode it; it just analyzes the box of parts, and tells you whether it would explode if it were constructed and fed the example input.

Awesome. Let's keep going.

[Xanthir]

Okay. So now we can finally move the Devious machine. Tell me where this stops making sense:

* The Devious machine is large, and contains an Oracle machine inside of itself.
* The Devious machine expects to be fed a box of parts. It'll then either explode, or print a smiley face.
* It does this by feeding that box of parts to its internal Oracle machine.
* But the Oracle machine needs two inputs, as we already established. So the Devious machine first *duplicates* the box of parts you gave it, then feeds both of those boxes to the Oracle.

In other words, if you feed the Devious machine a LightsThingsOnFire box, it'll duplicate the box so it has two boxes, then feed the Oracle machine both boxes of LightsThingsOnFire, exactly like my fourth example from earlier (and the Oracle will report "BOOM").

Does all this work so far?

[MathDoofus]

Okay. So now we can finally move the Devious machine. Tell me where this stops making sense:

* The Devious machine is large, and contains an Oracle machine inside of itself.
* The Devious machine expects to be fed a box of parts. It'll then either explode, or print a smiley face.
* It does this by feeding that box of parts to its internal Oracle machine.
* But the Oracle machine needs two inputs, as we already established. So the Devious machine first *duplicates* the box of parts you gave it, then feeds both of those boxes to the Oracle.

In other words, if you feed the Devious machine a LightsThingsOnFire box, it'll duplicate the box so it has two boxes, then feed the Oracle machine both boxes of LightsThingsOnFire, exactly like my fourth example from earlier (and the Oracle will report "BOOM").

Does all this work so far?

No, as an initial matter, I don't understand the contains-an-Oracle-machine inside itself part (recall that before Oracle accepted only two arguments), and I don't know how containing-a-machine-inside relates to what we've established that machines in our universe can do. This is very, very convoluted and I'm having difficulty even trying to parse these steps.

[Xanthir]

I don't understand the contains-an-Oracle-machine inside itself part (recall that before Oracle accepted only two arguments),

We've hit this point before - it's like your phone containing smaller machines in it - a CPU, a screen, a speaker, etc. The Oracle is a piece inside the large Devious machine.

This isn't a weird hypothetical universe where you have to accept non-intuitive things. I'm talking about real, actual machines here. You build large machines out of smaller machines, all the time. An assembly-bot contains linear actuators inside, which are tiny pushing-machines.

[MathDoofus]

I don't understand the contains-an-Oracle-machine inside itself part (recall that before Oracle accepted only two arguments),

We've hit this point before - it's like your phone containing smaller machines in it - a CPU, a screen, a speaker, etc. The Oracle is a piece inside the large Devious machine.

This isn't a weird hypothetical universe where you have to accept non-intuitive things. I'm talking about real, actual machines here. You build large machines out of smaller machines, all the time. An assembly-bot contains linear actuators inside, which are tiny pushing-machines.

OK. But is the Devious machine accepting two arguments in the same way that the Oracle machine did (or does?), or what's going on in that regard?

[Xanthir]

No, it only takes one. Why would you think that it needs to take two?

* The Devious machine expects to be fed a box of parts. It'll then either explode, or print a smiley face.
* It does this by feeding that box of parts to its internal Oracle machine.
* But the Oracle machine needs two inputs, as we already established. So the Devious machine first *duplicates* the box of parts you gave it, then feeds both of those boxes to the Oracle.

[MathDoofus]

No, it only takes one. Why would you think that it needs to take two?

* The Devious machine expects to be fed a box of parts. It'll then either explode, or print a smiley face.
* It does this by feeding that box of parts to its internal Oracle machine.
* But the Oracle machine needs two inputs, as we already established. So the Devious machine first *duplicates* the box of parts you gave it, then feeds both of those boxes to the Oracle.

Because Oracle takes two.

[Xanthir]

Yeah. What's the relevance of that?

It does this by feeding that box of parts to its internal Oracle machine.
* But the Oracle machine needs two inputs, as we already established. So the Devious machine first *duplicates* the box of parts you gave it, then feeds both of those boxes to the Oracle.

[MathDoofus]

Yeah. What's the relevance of that?

It does this by feeding that box of parts to its internal Oracle machine.
* But the Oracle machine needs two inputs, as we already established. So the Devious machine first *duplicates* the box of parts you gave it, then feeds both of those boxes to the Oracle.

The potential relevance is that when the Devious machine feeds Oracle, doesn't Oracle have to take two arguments to be consistent with how we've set this up? So isn't Devious in effect taking two (or more) arguments itself?

[Xanthir]

I'm quoting parts of my previous post that answer this exact issue. What part of those quotes are confusing you?

[MathDoofus]

I'm quoting parts of my previous post that answer this exact issue. What part of those quotes are confusing you?

I don't understand the duplication of parts by Devious and how that doesn't mean that Devious doesn't take two arguments.

[Xanthir]

Devious takes one box of parts. It then magically duplicates that box, inside itself, for its own internal reasons.

But you only *gave* it one box. It takes one argument, not two.

[MathDoofus]

Devious takes one box of parts. It then magically duplicates that box, inside itself, for its own internal reasons.

But you only *gave* it one box. It takes one argument, not two.

Then I don't understand. Is Oracle involved in the duplication?

[Xanthir]

No. Devious just also has a magic duplicator as one of its internal components. Just like it also has bomb and smiley-face printer components.

[MathDoofus]

Let me discard the physical objects example and explain what I've got so far:

Oracle is supposed to tell us whether a given program with a certain input will halt or not. And Oracle is also supposed to itself halt (i.e., Oracle must return an answer of "halt" or "won't halt"). Oracle accepts two arguments (program, input-to-program). Oracle then evaluates those two arguments and returns an answer to the (rough) question of "will the program I'm being fed as Argument One halt or not with the input I'm being fed as Argument Two?"

Devious is a program that takes only argument. That argument is another program.

Here, we design a world in which we have Devious call Oracle as its sole argument. Oracle of course takes two arguments, and those two arguments are Devious (as a program) and Devious (as input to the program). Then Oracle is tasked by Devious with answering the question of "will Devious the program halt or not when Devious the program is given itself as input?"

Is that correct so far?

[Xanthir]

Almost! There's one part where I'm unclear what you're referring to, so let's clear that up:

Here, we design a world in which we have Devious call Oracle as its sole argument.

It sounds like you're saying here that Devious takes Oracle as its sole argument. Is this what you meant? If so, then this is wrong. (And we haven't gotten there yet in my explanation, anyway.) Devious will take a copy of itself as its sole argument.

The stuff before and after that line is all correct, tho.

[MathDoofus]

Almost! There's one part where I'm unclear what you're referring to, so let's clear that up:

Here, we design a world in which we have Devious call Oracle as its sole argument.

It sounds like you're saying here that Devious takes Oracle as its sole argument. Is this what you meant? If so, then this is wrong. (And we haven't gotten there yet in my explanation, anyway.) Devious will take a copy of itself as its sole argument.

The stuff before and after that line is all correct, tho.

I must be mistaken about that. I'm trying to figure out how Devious gets Oracle to do work. I know that Devious must take at least one argument in order to get Oracle to do anything.

[Xanthir]

I'm going back to machines, because otherwise I don't understand how to suss out the issues.

Oracle is already built into Devious; it's one of Devious's sub-components. Devious takes a box of parts as its input, magically duplicates the box, then passes both boxes to Oracle.

The "trick" then is passing Devious a box of its own parts; this causes Devious to ask Oracle about how Devious itself would act.

[MathDoofus]

I'm going back to machines, because otherwise I don't understand how to suss out the issues.

Oracle is already built into Devious; it's one of Devious's sub-components. Devious takes a box of parts as its input, magically duplicates the box, then passes both boxes to Oracle.

The "trick" then is passing Devious a box of its own parts; this causes Devious to ask Oracle about how Devious itself would act.

Now I'm lost again. Where did I go wrong?

[Xanthir]

I dunno. Here's the steps again:

* The Devious machine is large, and contains an Oracle machine inside of itself.
* The Devious machine expects to be fed a box of parts. It'll then either explode, or print a smiley face.
* It does this by feeding that box of parts to its internal Oracle machine.
* But the Oracle machine needs two inputs, as we already established. So the Devious machine first *duplicates* the box of parts you gave it, then feeds both of those boxes to the Oracle.

Continued to get to the "trick":

* We then feed the Devious machine a box of Devious machine parts.
* Internally, it magically duplicates this box, so it now has two boxes of Devious machine parts inside itself.
* It feeds both of these to its Oracle component: one is the first argument, the machine to be analyzed, the other is the second argument, the example input to the analyzed machine.
* The Oracle component returns an answer: if it says COOL, Devious activates its bomb component and explodes; if it says BOOM, Devious activates its printer component and prints out a happy face.

Where in these steps are you getting confused?

[MathDoofus]

I dunno. Here's the steps again:

* The Devious machine is large, and contains an Oracle machine inside of itself.
* The Devious machine expects to be fed a box of parts. It'll then either explode, or print a smiley face.
* It does this by feeding that box of parts to its internal Oracle machine.
* But the Oracle machine needs two inputs, as we already established. So the Devious machine first *duplicates* the box of parts you gave it, then feeds both of those boxes to the Oracle.

Continued to get to the "trick":

* We then feed the Devious machine a box of Devious machine parts.
* Internally, it magically duplicates this box, so it now has two boxes of Devious machine parts inside itself.
* It feeds both of these to its Oracle component: one is the first argument, the machine to be analyzed, the other is the second argument, the example input to the analyzed machine.
* The Oracle component returns an answer: if it says COOL, Devious activates its bomb component and explodes; if it says BOOM, Devious activates its printer component and prints out a happy face.

Where in these steps are you getting confused?

The first four steps aren't clear to me.

[MathDoofus]

Almost! There's one part where I'm unclear what you're referring to, so let's clear that up:

Here, we design a world in which we have Devious call Oracle as its sole argument.

It sounds like you're saying here that Devious takes Oracle as its sole argument. Is this what you meant? If so, then this is wrong. (And we haven't gotten there yet in my explanation, anyway.) Devious will take a copy of itself as its sole argument.

The stuff before and after that line is all correct, tho.

I thought Devious took only one argument (a program, Oracle) and then Oracle (while inside Devious and being called by it) did stuff. If that's not the case, then I'm thoroughly confused and probably need to quit trying to understand this line of proof.

[gmalivuk]

Devious takes one argument, but to get the contradiction, the argument it takes is (the number corresponding to) Devious itself, not Oracle.

[MathDoofus]

Devious takes one argument, but to get the contradiction, the argument it takes is (the number corresponding to) Devious itself, not Oracle.

OK. So Devious takes only one argument (a program, Devious). How does Oracle get into the picture if Devious takes only one argument?