Halting Problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
ucim
Posts: 6567
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Halting Problem

Postby ucim » Sun May 07, 2017 11:37 pm UTC

Soupspoon wrote:(Altogether now...) Oh no it isn't!!
That's not contradiction, that's abuse! :)

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

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

Re: Halting Problem

Postby MathDoofus » Thu Dec 28, 2017 8:11 pm UTC

Returning to this after some months away to be sure that I understand the proof sufficiently. Any help would be appreciated.

Here's my high-level understanding of the proof:

We pretend that a program Oracle exists such that, for any program (P) with input (i), Oracle will tell us whether P halts when given i. Oracle accordingly can be represented like this: O(P, i)

Some background assumptions regarding Oracle that are necessary to the proof:

1. The proof works only if we assume that Oracle works for any program.

2. Oracle itself must halt every time or it's useless to us (because, if Oracle itself didn't halt, then it wouldn't be true that Oracle works for any program.

Next, we design a second program called Devious. Devious, unlike Oracle, takes only argument. And Devious has only one purpose: if Oracle says "yes" in response to the question of whether a program P will halt given input i, then Devious goes into an infinite loop and thus never halts. If Oracle says "no," then Devious halts. Devious is designed to do the exact opposite of what Oracle returns (or "predicts").

The steps below are where I'm having trouble and kindly request help:

We make Devious take itself as an argument: D(D)

But, somehow, the Devious-as-argument-to-Devious gets Oracle to run (I don't know how this happens). And then Oracle evaluates (Devious, Devious) (i.e., Devious as input to Devious). Oracle--because it's designed to answer the question of whether any given program P halts when given input i--returns a "yes" or "no" answer. But the outer layer of Devious always does the opposite, which shows that Oracle can't possibly exist.

User avatar
ucim
Posts: 6567
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Halting Problem

Postby ucim » Thu Dec 28, 2017 9:06 pm UTC

MathDoofus wrote:1. The proof works only if we assume that Oracle works for any program.
Close. Maybe actually correct; I have to think about it.
Spoiler:
I figure that so long as for every program, there is an Oracle..., it should work. It doesn't have to be the same oracle, but if it is, the proof is easier to follow because you don't have to worry if you are using the "right" oracle. But I could be wrong about this - I wonder if the self reference actually makes this first condition necessary.
MathDoofus wrote:But, somehow, the Devious-as-argument-to-Devious gets Oracle to run (I don't know how this happens).
Devious contains (a copy of) the code for Oracle within it. Devious is essentially Oracle with its outputs reversed.

We feed a copy of Devious to itself as input. Devious "asks" its built-in Oracle if this combination would halt. The built-in Oracle gives an answer, and then Devious does the opposite. Haha gotcha nyah nyah nyah!

Given Oracle, Devious could be constructed. But Devious implies that Oracle can fail. Therefore, it must be that Oracle can't exist.

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

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

Re: Halting Problem

Postby MathDoofus » Thu Dec 28, 2017 9:19 pm UTC

ucim wrote:
MathDoofus wrote:1. The proof works only if we assume that Oracle works for any program.
Close. Maybe actually correct; I have to think about it.
Spoiler:
I figure that so long as for every program, there is an Oracle..., it should work. It doesn't have to be the same oracle, but if it is, the proof is easier to follow because you don't have to worry if you are using the "right" oracle. But I could be wrong about this - I wonder if the self reference actually makes this first condition necessary.
MathDoofus wrote:But, somehow, the Devious-as-argument-to-Devious gets Oracle to run (I don't know how this happens).
Devious contains (a copy of) the code for Oracle within it. Devious is essentially Oracle with its outputs reversed.

We feed a copy of Devious to itself as input. Devious "asks" its built-in Oracle if this combination would halt. The built-in Oracle gives an answer, and then Devious does the opposite. Haha gotcha nyah nyah nyah!

Given Oracle, Devious could be constructed. But Devious implies that Oracle can fail. Therefore, it must be that Oracle can't exist.

Jose


Awesome! Thank you for the help. I'm still having trouble with Devious. I can get comfortable with Oracle and its two arguments (some program P given some input i) but I'm not entirely sure about Devious, in particular: (1) how Devious takes Devious as its argument and (2) then runs Oracle on Devious. Can you help with that? In other words, how is that Devious-as-argument itself get to take Oracle as an argument, which in turn takes two arguments (Devious and Devious)?

User avatar
ucim
Posts: 6567
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Halting Problem

Postby ucim » Thu Dec 28, 2017 10:35 pm UTC

MathDoofus wrote:how Devious takes Devious as its argument
Any program can be written to take arguments (initial input). Any program is also just made up of data: to wit, the statements that make it up. So, you can feed (A COPY OF) any program into Oracle, or to Devious. It's just data.
Spoiler:
If you feed it into the CPU's instruction register, the CPU will execute the instructions, "running" the program. That's what distinguishes an "executable" program from other kinds of data, like a cat picture. If you feed a cat picture into the CPU's instruction register, it will do seemingly random stuff and cough up a hairball. Devious (the running program) is being fed into the instruction register; that's what makes it run. But a copy of Devious is being fed into Devious itself. That copy doesn't make it to the instruction register, instead it is analyzed by the running Devious.
MathDoofus wrote:then runs Oracle on Devious.
That's a shorthand way of saying "Devious contains a copy of Oracle's routines, and it feeds the input into those routines to see what Oracle would have said". In this case the input is the copy of Devious. So, its copy of Oracle's routines analyse Devious and says that Devious would do foo. But it tells Devious because those routines are part of Devious. Now that Devious knows what the prediction of its action is, it goes ahead and does the opposite, proving that Oracle isn't a very good oracle.

MathDoofus wrote:how is that Devious-as-argument itself get to take Oracle as an argument
It doesn't take Oracle "as an argument". It contains Oracle, like people contain hearts and livers.

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

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

Re: Halting Problem

Postby MathDoofus » Thu Dec 28, 2017 10:41 pm UTC

ucim wrote:
MathDoofus wrote:how Devious takes Devious as its argument
Any program can be written to take arguments (initial input). Any program is also just made up of data: to wit, the statements that make it up. So, you can feed (A COPY OF) any program into Oracle, or to Devious. It's just data.
Spoiler:
If you feed it into the CPU's instruction register, the CPU will execute the instructions, "running" the program. That's what distinguishes an "executable" program from other kinds of data, like a cat picture. If you feed a cat picture into the CPU's instruction register, it will do seemingly random stuff and cough up a hairball. Devious (the running program) is being fed into the instruction register; that's what makes it run. But a copy of Devious is being fed into Devious itself. That copy doesn't make it to the instruction register, instead it is analyzed by the running Devious.
MathDoofus wrote:then runs Oracle on Devious.
That's a shorthand way of saying "Devious contains a copy of Oracle's routines, and it feeds the input into those routines to see what Oracle would have said". In this case the input is the copy of Devious. So, its copy of Oracle's routines analyse Devious and says that Devious would do foo. But it tells Devious because those routines are part of Devious. Now that Devious knows what the prediction of its action is, it goes ahead and does the opposite, proving that Oracle isn't a very good oracle.

MathDoofus wrote:how is that Devious-as-argument itself get to take Oracle as an argument
It doesn't take Oracle "as an argument". It contains Oracle, like people contain hearts and livers.

Jose


So Devious, in order for my explanation to work, must (in addition to taking itself as an argument, which I'll call Devious-as-argument) contain a copy of Oracle's code so that it can--when it takes itself as an argument--feed Oracle to Devious-as-argument? Do I have that right?

User avatar
ucim
Posts: 6567
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: Halting Problem

Postby ucim » Thu Dec 28, 2017 11:31 pm UTC

MathDoofus wrote:So Devious, in order for my explanation to work, must (in addition to taking itself as an argument, which I'll call Devious-as-argument) contain a copy of Oracle's code so that it can--when it takes itself as an argument--feed Oracle to Devious-as-argument? Do I have that right?
Almost. Devious contains Oracle's code, so that it can feed its input (in this case a copy of Devious(which contains Oracle) to Oracle's code. It feeds Devious-as-argument to Oracle('s guts contained in Devious-as-program), gets the response Oracle would have given, and then (nyah nyah) does the opposite.

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

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

Re: Halting Problem

Postby MathDoofus » Fri Dec 29, 2017 2:15 am UTC

ucim wrote:
MathDoofus wrote:So Devious, in order for my explanation to work, must (in addition to taking itself as an argument, which I'll call Devious-as-argument) contain a copy of Oracle's code so that it can--when it takes itself as an argument--feed Oracle to Devious-as-argument? Do I have that right?
Almost. Devious contains Oracle's code, so that it can feed its input (in this case a copy of Devious(which contains Oracle) to Oracle's code. It feeds Devious-as-argument to Oracle('s guts contained in Devious-as-program), gets the response Oracle would have given, and then (nyah nyah) does the opposite.

Jose


Thank you! I’m going to read this again in the morning and think about it a bit longer before asking additional questions.

User avatar
MartianInvader
Posts: 796
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Halting Problem

Postby MartianInvader » Tue Jan 09, 2018 12:42 am UTC

I just stumbled on this thread, but it might be a good thought-excercise to construct Devious yourself. In other words, solve the following problem:

Suppose you have an Oracle O(p, i) that correctly tells you whether any program will halt given any input (you can imagine this as just a bunch of code you can copy-paste at will, if it helps). Using this Oracle, write a program D(p) that takes a program p as input, and runs forever if p halts when passed itself as input, and halts if p runs forever when passed itself as input.

People in this thread have already given example code of such a program, but doing it yourself would really help understand what the program is.

Next, answer the question: What happens when you run D(D)? Will it halt or run forever?
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests