Halting Problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 6:07 pm UTC

No, that's the most concrete way I can possibly explain it. The Oracle machine takes a box of machine parts and some stuff that you want to put in that machine. Inside of the Devious machine, you feed it exactly that - it receives a box of machine parts (specifically, the IKEA crate full of Devious parts) and the stuff you want to feed to that machine (another IKEA crate full of Devious parts).

There's nothing tricky or subtle going on. It's just boxes of machine parts being passed around.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 6:21 pm UTC

Xanthir wrote:No, that's the most concrete way I can possibly explain it. The Oracle machine takes a box of machine parts and some stuff that you want to put in that machine. Inside of the Devious machine, you feed it exactly that - it receives a box of machine parts (specifically, the IKEA crate full of Devious parts) and the stuff you want to feed to that machine (another IKEA crate full of Devious parts).

There's nothing tricky or subtle going on. It's just boxes of machine parts being passed around.


I don't understand the concrete example, I'm sorry. I'm going to think for a bit and then draft another post to explain where I am.

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 6:31 pm UTC

Here's how I currently conceive of the problem and the proof-by-contradiction.

We have a program, Oracle, that must do two and only two things. First, it must tell us whether any program fed to it will halt or not. Second, it must itself halt.

We have a second program, Devious. Devious is designed to foil Oracle.

Devious runs Oracle and--because we can make Oracle accept as much input of any kind as we like--asks Oracle what will happen if Devious runs Devious. Now, I'm not yet clear on what the effect of Devious's running Devious is (someone please explain this to me using words!, but Oracle's only job in this context is to tell us whether Devious, when it runs Devious, will halt. Because we've designed Devious to do the opposite of what Oracle says, and because Oracle is being run by Devious, we know that Oracle cannot possibly reach the correct result since Devious is designed to do the opposite of Oracle.

Is that right?

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 6:40 pm UTC

MathDoofus wrote:
Devious runs Oracle and--because we can make Oracle accept as much input of any kind as we like--asks Oracle what will happen if Devious runs Devious.

No, here's where you keep falling down. Devious takes a program as input, and then asks Oracle what will happen if that program is given itself as input.

In most cases this is just fine! If I call Devious(someOtherProgram), it'll ask Oracle "will someOtherProgram(someOtherProgram) halt or loop?" and then it'll loop or halt as a result. No contradiction, it's just doing what it's defined to do.

The special case that causes the contradiction is when you feed Devious itself as input - in other words, when you call Devious(Devious) - because that causes Devious to ask Oracle what'll happen if you call Devious(Devious). It then does the opposite of what Oracle said it would.

(I'm not writing anything that hasn't already been said in this thread. I tried the machine analogy because it makes it clearer when we're *running* a machine vs *looking at* a machine, and makes the "pass a function as input" thing clearer.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 6:45 pm UTC

Let me add to the above and see if I'm closer to grasping the proof-by-contradiction.

We design Devious to do the opposite of what Oracle declares.

And, because we can run programs (and whatever else) inside programs, here's what happens.

Devious runs Oracle and, as part of running Oracle, asks Oracle to evaluate a copy of Devious. Now it doesn't really matter what the result of Oracle's evaluation of the inside version of Devious is, because the master Devious (i.e., the one asking Oracle to look at Devious) is programmed to do the opposite of whatever Oracle says. Even though Oracle is working with only the inside copy of Devious, because the master Devious contradicts (by design and definition) whatever Oracle says, then it simply can't be the case that Oracle always correctly tells us whether a program will halt or not.

What I'm still having trouble with (and if someone can answer this using only English, and with no pseudo-code or "pretend it's all fish" examples) is the following: Why is it that the outside version of Devious is permitted to take the contrary position to Oracle such that doing so makes Oracle wrong in the way that we care about?

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 6:46 pm UTC

Xanthir wrote:
MathDoofus wrote:
Devious runs Oracle and--because we can make Oracle accept as much input of any kind as we like--asks Oracle what will happen if Devious runs Devious.

No, here's where you keep falling down. Devious takes a program as input, and then asks Oracle what will happen if that program is given itself as input.

In most cases this is just fine! If I call Devious(someOtherProgram), it'll ask Oracle "will someOtherProgram(someOtherProgram) halt or loop?" and then it'll loop or halt as a result. No contradiction, it's just doing what it's defined to do.

The special case that causes the contradiction is when you feed Devious itself as input - in other words, when you call Devious(Devious) - because that causes Devious to ask Oracle what'll happen if you call Devious(Devious). It then does the opposite of what Oracle said it would.

(I'm not writing anything that hasn't already been said in this thread. I tried the machine analogy because it makes it clearer when we're *running* a machine vs *looking at* a machine, and makes the "pass a function as input" thing clearer.)


This is what I don't understand--I can't grasp how Devious can ask Oracle what happens in the case of Devious calling Devious, or even worse, what the outcome of Devious calling Devious would. Can you set this up for me?

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 6:55 pm UTC

I can't grasp how Devious can ask Oracle what happens in the case of Devious calling Devious, or even worse, what the outcome of Devious calling Devious would.

Tell me where in this list your understanding fails you:

1. Do you understand how we can run Oracle(someProgram, someInput), which is asking "what will happen if I call someProgram(someInput)?"?

2. Do you understand how "someInput" can be another program, like Oracle(someProgram, anotherProgram)? ("What will happen if I call someProgram(anotherProgram)?")

3. Do you understand how "someInput" can be the same program, like Oracle(someProgram, someProgram)? ("What will happen if I call someProgram(someProgram)?")

4. Do you understand how I can pass Devious's source code to itself, like Devious(Devious)? (Or in the case of a machine, how I can pass an IKEA box full of Devious parts to a running Devious machine?)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 6:57 pm UTC

Xanthir wrote:
I can't grasp how Devious can ask Oracle what happens in the case of Devious calling Devious, or even worse, what the outcome of Devious calling Devious would.

Tell me where in this list your understanding fails you:

1. Do you understand how we can run Oracle(someProgram, someInput), which is asking "what will happen if I call someProgram(someInput)?"?

2. Do you understand how "someInput" can be another program, like Oracle(someProgram, anotherProgram)? ("What will happen if I call someProgram(anotherProgram)?")

3. Do you understand how "someInput" can be the same program, like Oracle(someProgram, someProgram)? ("What will happen if I call someProgram(someProgram)?")

4. Do you understand how I can pass Devious's source code to itself, like Devious(Devious)? (Or in the case of a machine, how I can pass an IKEA box full of Devious parts to a running Devious machine?)


As to 1, no. I don't understand the difference between having Oracle evaluate a program vs. evaluating that program's input.

As to 2, no. I don't understand the nesting of programs, or what's supposed to happen when they're nested like that.

As to 3, no. See 2, above, and add to that the resulting confusion to someone named "MathDoofus" when a program is not only nested, but nested within itself!

As to 4, no. I don't know what source code is, or how it differs from the two arguments you refer to in 1, which are a program and some input.

Every single item on your list is unclear to me in one or more ways. I'm sorry. It's clear that I'll never get this.

Finally, the use of pseudo-code is highly confusing to me. I don't know how to program.

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 6:59 pm UTC

Just to see how far this goes:

Do you understand what it means to feed an Oracle machine a box of machine parts and some materials, which is asking "If I were to build the machine in this box, and feed it these materials, will it work fine or explode?"?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 7:02 pm UTC

Xanthir wrote:Just to see how far this goes:

Do you understand what it means to feed an Oracle machine a box of machine parts and some materials, which is asking "If I were to build the machine in this box, and feed it these materials, will it work fine or explode?"?


No. The physical-objects example is more confusing than the pseudo-code, frankly.

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 7:08 pm UTC

Okay, well that's literally step one of the entire construction, so I recommend thinking about that until you get it. You can't get any further without understanding that first step, as everything else builds on that.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 7:11 pm UTC

Xanthir wrote:Okay, well that's literally step one of the entire construction, so I recommend thinking about that until you get it. You can't get any further without understanding that first step, as everything else builds on that.


I think that I understand the Oracle. It's a program. It is supposed to evaluate any program fed to it (including itself) and tell us whether the program being evaluated will halt or not.

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 7:15 pm UTC

MathDoofus wrote:
Xanthir wrote:Okay, well that's literally step one of the entire construction, so I recommend thinking about that until you get it. You can't get any further without understanding that first step, as everything else builds on that.


I think that I understand the Oracle. It's a program. It is supposed to evaluate any program fed to it (including itself) and tell us whether the program being evaluated will halt or not.


You said "As to 1, no. I don't understand the difference between having Oracle evaluate a program vs. evaluating that program's input.", so you don't understand the Oracle. You might understand some different sort of program that we're not describing, but you don't understand the one we're actually trying to talk about.

---

Let's go back to machines, this is bugging me.

You and me, we go to a real-world IKEA. I grab a box from the shelves, open it up. Inside is a large flat surface, four legs, a bag of screws, and an instruction sheet. Just looking at these contents, without actually building the thing, can you tell that it's going to be a table? Of course you can.

That's all the Oracle machine does. It looks at a box of machine parts and an example input, and figures out "If I were to build this, it would do [some particular thing] when I give it [the example input]".

Does this make sense? Where, between "I can tell this box of IKEA parts will form a table" and "the Oracle machine can tell this box of IKEA parts will form a table" do you get confused?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby gmalivuk » Tue May 02, 2017 7:17 pm UTC

I really don't know how to explain this in a way it hasn't already been explained.

Every program you can run on a computer can be represented as a sequence of 1s and 0s. That sequence in turn corresponds to a particular number. All the inputs we're talking about are numbers, but numbers can refer to programs. Oracle interprets one of its numbers as a program and tells us what that program does with the other number.

Honestly, it's not even important that the number we associate with a program is the binary representation of the program. We could just have a numbering scheme where Devious is assigned the number 3.

Let's say program 2 is the program that just takes an input and divides it in half. Then Oracle(2,2) outputs HALT, because program 2 with input 2 just divides that in half and halts.

Devious(2) checks what Oracle(2,2) says, and then it does the opposite. So Devious(2) loops forever because Oracle(2,2) is HALT.

Devious(3) checks what Oracle(3,3) says and does the opposite. The problem is that Oracle(3,3) is supposed to tell us what program 3 does with input 3, and program 3 is Devious.

So Devious(3) does the opposite of what Oracle says Devious(3) does, and therefore we have to conclude that at least in this case, Oracle doesn't give the correct answer.
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: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 7:20 pm UTC

Xanthir wrote:
MathDoofus wrote:
Xanthir wrote:Okay, well that's literally step one of the entire construction, so I recommend thinking about that until you get it. You can't get any further without understanding that first step, as everything else builds on that.


I think that I understand the Oracle. It's a program. It is supposed to evaluate any program fed to it (including itself) and tell us whether the program being evaluated will halt or not.


You said "As to 1, no. I don't understand the difference between having Oracle evaluate a program vs. evaluating that program's input.", so you don't understand the Oracle. You might understand some different sort of program that we're not describing, but you don't understand the one we're actually trying to talk about.

---

Let's go back to machines, this is bugging me.

You and me, we go to a real-world IKEA. I grab a box from the shelves, open it up. Inside is a large flat surface, four legs, a bag of screws, and an instruction sheet. Just looking at these contents, without actually building the thing, can you tell that it's going to be a table? Of course you can.

That's all the Oracle machine does. It looks at a box of machine parts and an example input, and figures out "If I were to build this, it would do [some particular thing] when I give it [the example input]".

Does this make sense? Where, between "I can tell this box of IKEA parts will form a table" and "the Oracle machine can tell this box of IKEA parts will form a table" do you get confused?


No. I'm confused at the steps where Oracle is run inside something, either once or multiple times. That's the nub of the most confusing part.

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 7:32 pm UTC

That's not the part where you're confused, based on your previous answers, but let's run with it.

Again with the machine examples - do you find it confusing that the Devious machine can contain an Oracle machine inside of it? Most machines are made from smaller machines, in some sense. Your smartphone is a machine that contains a bunch of other machines, like a screen, a CPU, etc.

I assume this concept doesn't confuse you - what makes it confusing when we're talking about programs?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 7:39 pm UTC

Xanthir wrote:That's not the part where you're confused, based on your previous answers, but let's run with it.

Again with the machine examples - do you find it confusing that the Devious machine can contain an Oracle machine inside of it? Most machines are made from smaller machines, in some sense. Your smartphone is a machine that contains a bunch of other machines, like a screen, a CPU, etc.

I assume this concept doesn't confuse you - what makes it confusing when we're talking about programs?


Sure, I realize that, as two examples, desktop computers (which are machines composed of smaller machines such as a hard drive, a microprocessor, a video card, etc.) and cars (which has an engine, several smaller motors, etc.) contain a bunch of embedded machines.

What's unclear--and will probably forever remain unclear to me--are the following items:

1. How is Devious permitted to look at Oracle's output and only then do the opposite. That feels like cheating.

2. What does it even mean for Devious run itself (once or multiple times)?

3. What exactly is Devious passing, returning, or doing? I don't even know the right verb to use to ask the question! :)

4. Are we relying on two separate instances of Oracle?

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 7:46 pm UTC

How is Devious permitted to look at Oracle's output and only then do the opposite. That feels like cheating.

It's just got an Oracle machine inside of itself. Running the Oracle machine is an independent operation. This is similar to asking how your phone is permitted to look at its CPU output and only then update the screen; they're separate components.

What does it even mean for Devious run itself (once or multiple times)?

It doesn't. Devious never runs itself. Again, check out the machine example, because it makes the distinction between "a running machine" and "a box of machine parts" very clear. There is *one* running Devious machine; there are several boxes of Devious parts. At no point do those boxes of Devious parts "start running". The Oracle machine just scans them, does some computations, and tells you what it thinks the machine *would* do, *if* it were constructed and turned on.

What exactly is Devious passing, returning, or doing? I don't even know the right verb to use to ask the question! :)

Again, look at my machine example. Every time I mention a machine, I explain exactly what is getting put into it, and what it outputs. Can you point to exactly where in that description you found a confusing mention of a machine's inputs?

Are we relying on two separate instances of Oracle?

Look at the machine example. There is exactly one running Oracle machine - the one that's built into the running Devious machine.

(The box of Devious parts, as a result, also contains some Oracle parts, but again, this is not a running machine. It's just a box of parts with assembly instructions.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 7:50 pm UTC

Xanthir wrote:How is Devious permitted to look at Oracle's output and only then do the opposite. That feels like cheating.

It's just got an Oracle machine inside of itself. Running the Oracle machine is an independent operation. This is similar to asking how your phone is permitted to look at its CPU output and only then update the screen; they're separate components.[/quote]

How can we say that Oracle is "wrong" when Devious is arriving at an outcome (or a state, or a result - not sure which word to use) only after Oracle reports back? That's what feels like cheating.

I really, really want to move away from the machine example because it's confusing. Is there any other way to describe Oracle and Devious? I realize that I'm too stupid to understand the difference between a program and its input, but part of that is because no one has taken the time to explain what happens when a program takes itself as input.

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 7:59 pm UTC

How can we say that Oracle is "wrong" when Devious is arriving at an outcome (or a state, or a result - not sure which word to use) only after Oracle reports back? That's what feels like cheating.

Because we *ask* Oracle "what happens if we call Devious(Devious)?", and it gives us some answer, but when we *actually* call Devious(Devious), it does the opposite thing. But that's the final step; it's not the part where you're getting confused, your confusion is rooted in not understanding the earlier steps properly.

I really, really want to move away from the machine example because it's confusing. Is there any other way to describe Oracle and Devious? I realize that I'm too stupid to understand the difference between a program and its input, but part of that is because no one has taken the time to explain what happens when a program takes itself as input.

No, I'm sticking with machines, because they're the only way to avoid the confusion of things existing at multiple levels.

So, continuing to use this:

Do you understand a machine taking a box of machine parts as input? Say we have an IKEA Assembly Machine - you put in a box of IKEA parts, and the assembled IKEA furniture pops out the other end. This make sense?

Now it turns out that the IKEA Assembly Machine is also made by IKEA, and I order a second one. Rather than assemble it myself (the first one was hard enough!), I just put the box into my already-constructed IKEA Assembly Machine. Out pops a fully-assembled, second IKEA Assembly Machine. Does this make sense? (In real life there would be problems with having enough space to fit a fully-assembled machine inside of itself, but this is the world of imagination, where that doesn't matter.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby gmalivuk » Tue May 02, 2017 8:00 pm UTC

1) How is it cheating to look at the output of a submachine? Your car's speedometer looks at the output of some sensors before deciding what to display. Devious is just some wrapping we put around Oracle.

2) Devious doesn't run itself, it runs Oracle. When we say "Devious(Devious)", we just mean Devious runs on the number that corresponds to it. In my scheme from above, it's the same as Devious(3).

3) Devious is passing its input to Oracle, twice. Devious(7) runs Oracle(7,7), and Oracle(7,7) just tells us what program number 7 does when given the integer 7 as input.

4) Oracle runs once. As I explained (did you see my post above?), Devious(2) runs Oracle(2,2). Oracle(2,2) outputs HALT (because I decided in my numbering scheme that program 2 simply divides its input in half and then stops) so Devious(2) loops forever. Devious(3) runs Oracle(3,3), which is supposed tottell us what program 3 (which is the number I'm giving to Devious) does with input 3. This is a totally legal move because Oracle is supposed to correctly tell us what every program does with every input. It can do so without actually running that program, just like you can tell the box contains parts for a table without putting it together.
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: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 8:04 pm UTC

Xanthir wrote:
How can we say that Oracle is "wrong" when Devious is arriving at an outcome (or a state, or a result - not sure which word to use) only after Oracle reports back? That's what feels like cheating.

Because we *ask* Oracle "what happens if we call Devious(Devious)?", and it gives us some answer, but when we *actually* call Devious(Devious), it does the opposite thing. But that's the final step; it's not the part where you're getting confused, your confusion is rooted in not understanding the earlier steps properly.


You are the first person to explain that asking Oracle to declare "halt" or "won't halt" is completely separate from "calling" Devious. What I still don't understand is how we're allowed to say that Oracle is wrong when Devious gets to have the last word.

No, I'm sticking with machines, because they're the only way to avoid the confusion of things existing at multiple levels.

So, continuing to use this:

Do you understand a machine taking a box of machine parts as input? Say we have an IKEA Assembly Machine - you put in a box of IKEA parts, and the assembled IKEA furniture pops out the other end. This make sense?

Now it turns out that the IKEA Assembly Machine is also made by IKEA, and I order a second one. Rather than assemble it myself (the first one was hard enough!), I just put the box into my already-constructed IKEA Assembly Machine. Out pops a fully-assembled, second IKEA Assembly Machine. Does this make sense? (In real life there would be problems with having enough space to fit a fully-assembled machine inside of itself, but this is the world of imagination, where that doesn't matter.)


I am having some trouble distinguishing between a box of parts and something that, when assembled, automatically assembles boxes of parts. In other words, it's hard for me to imagine something assembling itself.

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 8:11 pm UTC

gmalivuk wrote:1) How is it cheating to look at the output of a submachine? Your car's speedometer looks at the output of some sensors before deciding what to display. Devious is just some wrapping we put around Oracle.



Because we wouldn't say that the sensors are wrong if the speedometer were designed solely to report exactly the opposite of what the sensors are saying.

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: Halting Problem

Postby Robert'); DROP TABLE *; » Tue May 02, 2017 8:12 pm UTC

I don't know how useful this example is, because it doesn't map very well to the actual actions we have the machines/programs perform, but it might help illuminate the logic and structure of the argument a bit.

Imagine that we visit the mystic oracle (who is a person) who lives at Delphi. The oracle is known to have a very strange magic power - if you name any person, and ask any strictly yes/no question, the oracle will tell you how that person would answer that question. The oracle is thought to be perfect and infallible - he always answers immediately, no matter how hard the question, and the answers he gives are always correct, even when actually asking the question might lead the actual person to hum and haw for a very long time before they give any answer at all. Nobody has ever managed to ask a question, or ask about a person, that the oracle does not know the answer to.

We are skeptical of this claim - how can the oracle reliably answer questions about everyone, on every subject? We think to ourselves for a while, trying to think of a question that will stump the oracle. Devious people that we are, we eventually come up with one.

We make our way to Delphi. We meet the oracle. Then, we ask our question, and our question is: "If I were to ask you this question, would you answer 'no'?"
Last edited by Robert'); DROP TABLE *; on Tue May 02, 2017 8:17 pm UTC, edited 1 time in total.
...And that is how we know the Earth to be banana-shaped.

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 8:15 pm UTC

What I still don't understand is how we're allowed to say that Oracle is wrong when Devious gets to have the last word.

Oracle is wrong because we asked it a question about a hypothetical situation, it said the result would be X, then we actually *did* that situation in real life, and we got Y instead.

I am having some trouble distinguishing between a box of parts and something that, when assembled, automatically assembles boxes of parts.

I'm not sure how. A box of parts is very different from a running machine. You can tell the difference between a working computer, and a box of computer parts. That's the only distinction I'm making here.

If assemblers themselves are the problem, then you can tell the difference between a car-assembly robot, like you see in car factories, and a box of the parts that a car-assembly robot is made out of. They're two completely different things - one's a robot, one's a box of machine parts.

In other words, it's hard for me to imagine something assembling itself.

Nothing assembles itself at any point. It might assemble another copy of itself. Take the car-assembly robot. There's no reason I couldn't change its programming so that it assembles *another* assembly robot, right? Does this confuse you?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby gmalivuk » Tue May 02, 2017 8:17 pm UTC

MathDoofus wrote:
gmalivuk wrote:1) How is it cheating to look at the output of a submachine? Your car's speedometer looks at the output of some sensors before deciding what to display. Devious is just some wrapping we put around Oracle.



Because we wouldn't say that the sensors are wrong if the speedometer were designed solely to report exactly the opposite of what the sensors are saying.
So? The sensors aren't sensing whether the speedometer is reporting the speed correctly, they're sensing the speed.

If we had sensors to detect whether some part of the car was working correctly, and the output from those sensors reported exactly the opposite of what the sensors are saying, then we'd certainly say something was wrong.

MathDoofus wrote:I am having some trouble distinguishing between a box of parts and something that, when assembled, automatically assembles boxes of parts. In other words, it's hard for me to imagine something assembling itself.
People are machines that can construct other people.
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)

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

Re: Halting Problem

Postby Soupspoon » Tue May 02, 2017 8:22 pm UTC

((Since I started this response, countless messages (or, at least, I have not counted them) have bounced back and forth... May not be useful any more, but some of what was said does seem to answer some of what arose between then and now... So, without further delay, here you are anyway...))

Code: Select all

How many vowels are there in the following sentence? "How many vowels are there in the following sentence?"

The answer is (immaterial, but) 16 (if I counted them correctly myself) and does not depend upon asking the quoted question, merely looking at the words in the quotes in context of the 'calling question'.

Code: Select all

Ask this of itself: "How many vowels are there in the following sentence?"

...a mish-mash of the core behaviour of an (Undevious) aggregator. This would ask the question (how many vowels) of the text ("How many [...] following sentence?")


For an Oracle question, "Has the following question a valid answer?" is what we might ask, as in:

Code: Select all

Has the following question a valid answer? "How many roads must a man walk down, before we can call him a man?"

If we were to 'run' the "How many roads..?" question we may get an answer from it or discover that it just keeps on blowing in the wind. The HTFQAVA? question is supposedly capable of telling us whether there is an answer, but not the answer itself. Because some questions have no answers and (perhaps) before asking any question you would like to know if one might actually get an answer...

With the Devious, we're saying "Give no answer only if the following has a valid answer", by way of internalising the results of the HTFQAVA and acting accordingly. Like so...

Code: Select all

Give no answer only if the following has a valid answer: "How many vowels are there in the following sentence?"

...gives no answer, because HTFQAVA determines (somehow) that it has and thus our Give No Answer kicks in.

Code: Select all

Give no answer only if the following has a valid answer: "How many roads must a man walk down, before we can call him a man?"
...gives, if HTFQAVA senses it as unanswerable, some answer. Maybe "this question had no answer", the only answer that the Give No Answer can give, and only when that is the actual answer.

I've taken liberties with this "in words only" explanation, which will be self-evident to others (e.g. the absence of an answer must not be deemed sufficiently an answer in itself, and "How many roads..?" as a question does not need to be followed by a quote for the road question to query), but it is the disassociation of the words being referenced to by the questions (or other instructions) from the top-level question, and the presumed ability of the HTFQAVA "oracle" to bypass the barriers of actually having to find the buried answer to finding out whether any question has an answer to give, howsoever unanswerable it is, that reflects the way the pseudocoded technical description of the problem deals with the issue.

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 8:25 pm UTC

Xanthir wrote:Oracle is wrong because we asked it a question about a hypothetical situation, it said the result would be X, then we actually *did* that situation in real life, and we got Y instead.



Can you explain this part in detail? How do we get Oracle to opine on a hypothetical while, at the same time, using Devious to show (or cause?) the actual to be the opposite?

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 8:29 pm UTC

Can you explain this part in detail? How do we get Oracle to opine on a hypothetical while, at the same time, using Devious to show (or cause?) the actual to be the opposite?

Explaining that part in detail is what I and others have been trying to do this whole time. Quit trying to jump straight to the end; it's the middle parts that are causing you confusion. ^_^

So in your last response we said:

I am having some trouble distinguishing between a box of parts and something that, when assembled, automatically assembles boxes of parts.


I'm not sure how. A box of parts is very different from a running machine. You can tell the difference between a working computer, and a box of computer parts. That's the only distinction I'm making here.

If assemblers themselves are the problem, then you can tell the difference between a car-assembly robot, like you see in car factories, and a box of the parts that a car-assembly robot is made out of. They're two completely different things - one's a robot, one's a box of machine parts.


Does this explanation confuse you? If so, what part? This is important development toward the eventual answer - a box of machine parts, and an assembled running machine made from those parts, are different things, and we can tell them apart. Yes?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 8:31 pm UTC

Xanthir wrote:Does this explanation confuse you? If so, what part? This is important development toward the eventual answer - a box of machine parts, and an assembled running machine made from those parts, are different things, and we can tell them apart. Yes?


I think that I can tell the difference among (1) a box of loose machine parts and (2) a machine construed (however magically) from those loose parts.

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

Re: Halting Problem

Postby gmalivuk » Tue May 02, 2017 8:35 pm UTC

MathDoofus wrote:How do we get Oracle to opine on a hypothetical
All Oracle can ever do is opine on a hypothetical. Oracle(4,5) tells us what would happen if we ran program 4 with input 5. It can't actually try to run program 4, because program 4 might loop forever and then Oracle could never finish and give us an answer.

IkeaOracle looks in the Ikea box and tells us what that piece of furniture would be if we assembled it. It doesn't have to assemble it. The Ikea box includes instructions, and there's nothing illegal about one of those instructions being, "If IkeaOracle says this box contains a table, go to page 5. If Oracle says this box contains something else, go to page 10." And then page 5 starts instructions for making a dresser out of the parts, while page 10 starts instructions for making a table.

The possibility of creating such a box (with such instructions) would mean that IkeaOracle must sometimes make a mistake.
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)

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 8:36 pm UTC

I thought so, but you keep claiming you can't. ^_^

Okay, so back to the machine examples.

Do you understand how I could make an machine that takes a box of machine parts and some example material as input? Like, just the concept of a machine that takes a box of machine parts as input. (An assembler-bot is *one example* of this, but it's not actually what we're talking about here.

If you understand that, then that's the basis of the Oracle machine - it takes that box, scans it, does some computer simulations, and figures out whether the machine parts, if they're assembled into a working machine, will explode or not. Does this make sense?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 8:37 pm UTC

gmalivuk wrote:
MathDoofus wrote:How do we get Oracle to opine on a hypothetical
All Oracle can ever do is opine on a hypothetical. Oracle(4,5) tells us what would happen if we ran program 4 with input 5. It can't actually try to run program 4, because program 4 might loop forever and then Oracle could never finish and give us an answer.

IkeaOracle looks in the Ikea box and tells us what that piece of furniture would be if we assembled it. It doesn't have to assemble it. The Ikea box includes instructions, and there's nothing illegal about one of those instructions from being, "If IkeaOracle says this box contains a table, go to page 5. If Oracle says this box contains a dresser, go to page 10." And then page 5 starts instructions for making a dresser out of the parts, while page 10 starts instructions for making a table.

Creating such a box (with such instructions) would mean that IkeaOracle must sometimes make a mistake.


Then how can Devious call Oracle and then run Devious inside of Devious while still somehow using Oracle? That's what I'm struggling with.

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 8:38 pm UTC

Xanthir wrote:I thought so, but you keep claiming you can't. ^_^

Okay, so back to the machine examples.

Do you understand how I could make an machine that takes a box of machine parts and some example material as input? Like, just the concept of a machine that takes a box of machine parts as input. (An assembler-bot is *one example* of this, but it's not actually what we're talking about here.

If you understand that, then that's the basis of the Oracle machine - it takes that box, scans it, does some computer simulations, and figures out whether the machine parts, if they're assembled into a working machine, will explode or not. Does this make sense?


No, I don't understand the difference between machine parts and example material.

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 8:39 pm UTC

They're just two inputs. The Oracle device takes two inputs. One *must* be a box of machine parts, the other can be *anything*.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Halting Problem

Postby gmalivuk » Tue May 02, 2017 8:39 pm UTC

MathDoofus wrote:
gmalivuk wrote:
MathDoofus wrote:How do we get Oracle to opine on a hypothetical
All Oracle can ever do is opine on a hypothetical. Oracle(4,5) tells us what would happen if we ran program 4 with input 5. It can't actually try to run program 4, because program 4 might loop forever and then Oracle could never finish and give us an answer.

IkeaOracle looks in the Ikea box and tells us what that piece of furniture would be if we assembled it. It doesn't have to assemble it. The Ikea box includes instructions, and there's nothing illegal about one of those instructions from being, "If IkeaOracle says this box contains a table, go to page 5. If Oracle says this box contains a dresser, go to page 10." And then page 5 starts instructions for making a dresser out of the parts, while page 10 starts instructions for making a table.

Creating such a box (with such instructions) would mean that IkeaOracle must sometimes make a mistake.


Then how can Devious call Oracle and then run Devious inside of Devious while still somehow using Oracle? That's what I'm struggling with.
Devious never runs inside of anything.

Devious calls Oracle, and Oracle opines on a hypothetical of what would happen if we ran Devious on some input. But like I just said in that post you quoted, Oracle never runs the programs we ask it about.
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: 247
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 8:40 pm UTC

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?

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

Re: Halting Problem

Postby MathDoofus » Tue May 02, 2017 8:41 pm UTC

gmalivuk wrote:
Devious never runs inside of anything.

Devious calls Oracle, and Oracle opines on a hypothetical of what would happen if we ran Devious on some input. But like I just said in that post you quoted, Oracle never runs the programs we ask it about.


OK. Then how do we reach a result sufficient to show that Oracle must sometimes be wrong?

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

Re: Halting Problem

Postby gmalivuk » Tue May 02, 2017 8:43 pm UTC

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?

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.

MathDoofus wrote:
gmalivuk wrote:Devious never runs inside of anything.

Devious calls Oracle, and Oracle opines on a hypothetical of what would happen if we ran Devious on some input. But like I just said in that post you quoted, Oracle never runs the programs we ask it about.


OK. Then how do we reach a result sufficient to show that Oracle must sometimes be wrong?
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.
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)

User avatar
Xanthir
My HERO!!!
Posts: 5212
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Halting Problem

Postby Xanthir » Tue May 02, 2017 8:45 pm UTC

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


Return to “Mathematics”

Who is online

Users browsing this forum: Zamfir and 16 guests