## Halting Problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

### Re: Halting Problem

Xanthir wrote:
MathDoofus wrote:
Xanthir wrote: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
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

gmalivuk wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

MathDoofus wrote:
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

me, in the exact post you're replying to wrote:A machine's behavior can change based on what you feed it, tho - some inputs make it explode, others don't.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote:
MathDoofus wrote:
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

me, in the exact post you're replying to wrote: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
GNU Terry Pratchett
Posts: 26577
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

MathDoofus wrote:
Xanthir wrote:
MathDoofus wrote:
Xanthir wrote: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 22*32) 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).
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: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 22*32) 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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

MathDoofus wrote:
Xanthir wrote:
MathDoofus wrote:
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

me, in the exact post you're replying to wrote: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?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote:
MathDoofus wrote:
Xanthir wrote:
MathDoofus wrote:
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

me, in the exact post you're replying to wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

MathDoofus wrote:
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.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote:
MathDoofus wrote:
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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

What's confusing about the fourth example that's not confusing about the third example? The two are, intentionally, almost identical.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
You have done something you shouldn't. Or are about to.
Posts: 3884
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

### Re: Halting Problem

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).
Last edited by Soupspoon on Tue May 02, 2017 10:03 pm UTC, edited 1 time in total.

Xanthir
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote:
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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

I'm quoting parts of my previous post that answer this exact issue. What part of those quotes are confusing you?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
My HERO!!!
Posts: 5366
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Halting Problem

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?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

### Re: Halting Problem

Xanthir wrote: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
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Halting Problem

Xanthir wrote: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
GNU Terry Pratchett
Posts: 26577
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Halting Problem

Devious takes one argument, but to get the contradiction, the argument it takes is (the number corresponding to) Devious itself, not 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: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?