Halting Problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Halting Problem

Postby MathDoofus » Mon May 01, 2017 2:01 pm UTC

I am reading about Turing Machines, and I've come across something called the Halting Problem. The common explanations of the Halting Problem, however, leave me confused. In particular, it's difficult for me to parse the various programs being referenced (one is a program that tells us whether a particular program halts; another is a program that doesn't halt; and there's also a third program that I don't understand). Can anyone simplify all of this for a newbie?

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

Re: Halting Problem

Postby Soupspoon » Mon May 01, 2017 3:02 pm UTC

Without seeing those three example (or abstractly described) programs, I'm going to try to go from scratch. It might not be helpful, and it's not complete (or necessarily bulletproof) as an explanation, but further replies from you and others may rectify such issues.

A program may or may not halt. If it has an explicitly functional infinite loop, it will not halt. If it has no looping at all, it will (assuming it has a finite size) eventually halt. But only a subset of programs can be shown to have an unconditionally repetitious loop with no other exits or are linear (or branching, or just plain spaghetti) such that they never backtrack onto prior steps.

Analysing the remainder, you are left with the possibility that you only know if a program will halt if you run the program (or analyse it with another program) and it halts (or the analysing program determines that it halts, thus itself halting upon outputting the result). If you are running the program and it is not yet halting, then only in the simpler cases can you determine that it will not halt. Otherwise you (or your analysing program) only knows that it has not yet halted. It may halt next instruction (or divert onto a path, in the next instruction, that leads to a halting branch), but to know this you need to keep on going. And potentially keep on going and going and going, because the very next instruction could be the point at which the program halts. You only know when you find it, and you're not going to halt yourself (or the second program) until you do. So a non-trivial and ultimately non-halting program is going to make you not halt your search for the halt that will not come.

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 3:06 pm UTC

Soupspoon wrote:Without seeing those three example (or abstractly described) programs, I'm going to try to go from scratch. It might not be helpful, and it's not complete (or necessarily bulletproof) as an explanation, but further replies from you and others may rectify such issues.

A program may or may not halt. If it has an explicitly functional infinite loop, it will not halt. If it has no looping at all, it will (assuming it has a finite size) eventually halt. But only a subset of programs can be shown to have an unconditionally repetitious loop with no other exits or are linear (or branching, or just plain spaghetti) such that they never backtrack onto prior steps.

Analysing the remainder, you are left with the possibility that you only know if a program will halt if you run the program (or analyse it with another program) and it halts (or the analysing program determines that it halts, thus itself halting upon outputting the result). If you are running the program and it is not yet halting, then only in the simpler cases can you determine that it will not halt. Otherwise you (or your analysing program) only knows that it has not yet halted. It may halt next instruction (or divert onto a path, in the next instruction, that leads to a halting branch), but to know this you need to keep on going. And potentially keep on going and going and going, because the very next instruction could be the point at which the program halts. You only know when you find it, and you're not going to halt yourself (or the second program) until you do. So a non-trivial and ultimately non-halting program is going to make you not halt your search for the halt that will not come.


That is a great explanation, thank you. What I'm stuck on is the standard explanation in which one assumes that there's a program that can tell you whether any particular program fed into it will halt (or not halt). That's where I get hung up.

arbiteroftruth
Posts: 344
Joined: Wed Sep 21, 2011 3:44 am UTC

Re: Halting Problem

Postby arbiteroftruth » Mon May 01, 2017 3:11 pm UTC

This video is a pretty good animation of the paradox you get if you assume you can solve the halting problem.

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

Re: Halting Problem

Postby Soupspoon » Mon May 01, 2017 3:17 pm UTC

(Today's XKCD is somewhat related to that... ;) )

It's a hypothetical program, which you assume to exist and then think about the necessary conditions of such a program existing.

i.e. given a Turing Computer tape with a Turing Computer program upon it, the contents of that tape could be data upon a Turing Computer tape with an "analyse this other program" program. I'll let that sink in, because your teaching materials may or may not deal with the problem in such terms, but you may be able to relate this with what they do say.

((Also may have been ninjaed, but haven't looked at the video link just given myself...))

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 3:40 pm UTC

Soupspoon wrote:(Today's XKCD is somewhat related to that... ;) )

It's a hypothetical program, which you assume to exist and then think about the necessary conditions of such a program existing.

i.e. given a Turing Computer tape with a Turing Computer program upon it, the contents of that tape could be data upon a Turing Computer tape with an "analyse this other program" program. I'll let that sink in, because your teaching materials may or may not deal with the problem in such terms, but you may be able to relate this with what they do say.

((Also may have been ninjaed, but haven't looked at the video link just given myself...))


The example from my materials tries to make some point about what I'll call the "Master Program" being fed some program that, depending on the input to that program, gets contradictory instructions. I still don't understand it, although the YouTube video was entertaining!

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 4:27 pm UTC

MathDoofus wrote:That is a great explanation, thank you. What I'm stuck on is the standard explanation in which one assumes that there's a program that can tell you whether any particular program fed into it will halt (or not halt). That's where I get hung up.


the proof usually follows this logic: suppose it is possible to solve the halting problem, so we are supposing there is some machine which will tell you whether some program will halt on a certain input. then, we will prove a contradiction (something impossible). therefore, the supposition must have been incorrect, which means the halting problem cannot be solved. this sort of style -- assuming something, then showing it's impossible, which means the opposite of the assumption was true, is a popular style of proof

also something to be really careful about is that the halting problem is not about whether a program will halt. it is about whether a specific program, given a specific input, will halt.

another thing to pay attention to is that the inputs to all machines are strings, and it is possible to encode a computer program as a string as well. therefore you can feed the encoding of one machine into another machine
Last edited by >-) on Mon May 01, 2017 4:29 pm UTC, edited 1 time in total.

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 4:29 pm UTC

>-) wrote:
also something to be really careful about is that the halting problem is not about whether a program will halt. it is about whether a specific program, given a specific input, will halt.


What do you mean by this statement?

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 4:32 pm UTC

well suppose you wrote a program to multiply two numbers. it doesn't make much sense to talk about whether the program halts, because it won't really do anything unless you give it some input (the numbers to be multiplied). even the empty string is a valid input, of course

formally, the halting problem asks for some turing machine M and some input x, does the M(x) (the computation of M given input x) halt?

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 4:35 pm UTC

>-) wrote:well suppose you wrote a program to multiply two numbers. it doesn't make much sense to talk about whether the program halts, because it won't really do anything unless you give it some input (the numbers to be multiplied). even the empty string is a valid input, of course

formally, the halting problem asks for some turing machine M and some input x, does the M(x) (the computation of M given input x) halt?


That makes sense. What I'd like to make sense of now is the program-within-a-program paradox that's apparently the standard method for explaining the halting problem to people like me who are math morons.

User avatar
Zohar
COMMANDER PORN
Posts: 7328
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: NY

Re: Halting Problem

Postby Zohar » Mon May 01, 2017 4:36 pm UTC

Let's take a simple example of a basic algorithm of division. You get a number a and a divisor d. In order to see what a/d is, you calculate a-d. If a-d <= 0 then you're done and you know "a/d = 0 plus something small". Else you get a new positive number. Then you subtract d from it again and continue on and on.

For example, let's say you're dividing 7 by 3. So 7-3=4, that's 1 subtraction. 4-3=1, that's 2 subtractions. 1-3=-2, -2 < 0. So we stop, and we know 7/3=2 and a remainder. And our program halts, awesome!

What happens if you put use the same algorithm try to calculate 7 divided by 0? Or 7 divided by -3? In these cases, our program won't stop. It depends on the input, it's not always going to behave the same.

Of course in this case you case put limitation on the input (make sure they're both positive numbers, for instance, and it will always halt).
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."

Not how I say my name

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 4:40 pm UTC

Zohar wrote:Let's take a simple example of a basic algorithm of division. You get a number a and a divisor d. In order to see what a/d is, you calculate a-d. If a-d <= 0 then you're done and you know "a/d = 0 plus something small". Else you get a new positive number. Then you subtract d from it again and continue on and on.

For example, let's say you're dividing 7 by 3. So 7-3=4, that's 1 subtraction. 4-3=1, that's 2 subtractions. 1-3=-2, -2 < 0. So we stop, and we know 7/3=2 and a remainder. And our program halts, awesome!

What happens if you put use the same algorithm try to calculate 7 divided by 0? Or 7 divided by -3? In these cases, our program won't stop. It depends on the input, it's not always going to behave the same.

Of course in this case you case put limitation on the input (make sure they're both positive numbers, for instance, and it will always halt).


So we're saying that in order to divide we must first subtract the numbers that we want to divide? I'm sorry; I don't follow this at all.

User avatar
doogly
Dr. The Juggernaut of Touching Himself
Posts: 5152
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Somerville, MA
Contact:

Re: Halting Problem

Postby doogly » Mon May 01, 2017 4:44 pm UTC

That's how you do division. Multiplication is iterated addition. Division is iterated subtraction, counting how many times you had to iterate. If I have to subtract 4 from 12 three times to get to 0, I know 12/4 = 3. If you divide 15 by 6, you do it 3 times and get to -3, which is less than 0, so you know 15/6 is 2 with a remainder of 3, So it is 2+3/6. Then maybe you reduce.
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 4:46 pm UTC

MathDoofus wrote:What I'd like to make sense of now is the program-within-a-program paradox


Here's a pretty standard proof I think. I'll use <> angle brackets to denode encoding.

First we suppose that we have some program M, such that M(x) tells us if the program and input pair encoded by x will halt. In other words, M tries to parse x into some pair (D,y) and tells us if the computation D(y) wil halt

Now we're going to find some program D and input y which will cause M to mess up.
D(y) does the following: Interpret y as the encoding of some computer program, then we will encode the pair (y,y) and run M(<y,y>). Now suppose the answer D gets back is no, it will not halt. Then D exits. Suppose the answer D gets back is yes, then D loops forever.

Now think about what happens when we run D(<D>). This causes D to interpret <D> as some computer program, which is is. Then, D will run M(<<D>,D>). If M tells D no this means M has claimed D(<D>) will not halt. but by how we defined D, we know it will halt. If M tells D yes, this means M has claimed D(<D>) will halt, but by how we defined D, we know it will go into an infinite loop. Therefore whatever M does, it is wrong.

We have just shown that M must be wrong, so there is no machine which can solve the halting problem.

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 4:47 pm UTC

Can anyone explain the proof-by-contradiction explanation of the Halting Problem? I'm having trouble following the various inputs to all of the hypothetical programs.

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 4:49 pm UTC

what i gave is a proof-by-contradiction type proof. just try to follow all the inputs and explain where you get stuck -- there are only two machines, each of which takes one input (well M takes one pair...)

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 4:51 pm UTC

>-) wrote:what i gave is a proof-by-contradiction type proof. just try to follow all the inputs and explain where you get stuck -- there are only two machines, each of which takes one input (well M takes a one pair...)


I'm sorry; I don't understand the relationship between the input and the pairs.

User avatar
Zohar
COMMANDER PORN
Posts: 7328
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: NY

Re: Halting Problem

Postby Zohar » Mon May 01, 2017 4:53 pm UTC

What >-) means is you can have a function that has multiple inputs. For example, f(x,y)=x-y. So f(5,4)=5-4=1. I hope that helps. Try to write down what >-) wrote, step by step, on a piece of paper. See if you can understand how each sentence follows from the previous one.
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."

Not how I say my name

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 4:54 pm UTC

it's not super important, but under the turing model of computation, turing machines (aka computer programs) take exactly one string as an input. of course, if you want to feed a machine two inputs, you can just combine the two inputs and put a delimiter between them. for example, you might feed two inputs 123 and 321 in a program by feeding in one input 123#321, and the # allows the program to figure out how to split the input. It's probably completely fine to think of M as taking two inputs <D> and y instead. so we have M(<D>,y) instead of M(x)

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 4:56 pm UTC

Zohar wrote:What >-) means is you can have a function that has multiple inputs. For example, f(x,y)=x-y. So f(5,4)=5-4=1. I hope that helps. Try to write down what >-) wrote, step by step, on a piece of paper. See if you can understand how each sentence follows from the previous one.


Is there a way of simplifying such that each program-within-a-program doesn't take multiple arguments? I'm getting bogged down in distinguishing between stuff that's meaningful and stuff that's not.

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 4:59 pm UTC

no, i don't think so.
but there are not that many programs and arguments. we have M, the halting problem solving program, which takes the bare minimum it needs! it only takes the program and the input you want to test. then we have D, the program which we are designing to mess up M. D only takes a single argument -- it's not possible to take any less.

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 5:01 pm UTC

>-) wrote:no, i don't think so.
but there are not that many programs and arguments. we have M, the halting problem solving program, which takes the bare minimum it needs! it only takes the program and the input you want to test. then we have D, the program which we are designing to mess up M. D only takes a single argument -- it's not possible to take any less.


What I'm having trouble with is distinguishing between the syntax (which is hard for me to parse) and what the substance of the example is. It makes it hard for me to figure out how the layers interact when the program is sometimes taking a string as input and at other times is taking a program as input. Does that make sense?

User avatar
Zohar
COMMANDER PORN
Posts: 7328
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: NY

Re: Halting Problem

Postby Zohar » Mon May 01, 2017 5:03 pm UTC

Thanks for the clarification, >-).

MathDoofus - if you want to learn about computing you'll have to get used to these kinds of notations and situations. Like I said - write it down, try to figute out how each statement is connected to the next and why it's written in that way.
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."

Not how I say my name

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 5:06 pm UTC

Zohar wrote:Thanks for the clarification, >-).

MathDoofus - if you want to learn about computing you'll have to get used to these kinds of notations and situations. Like I said - write it down, try to figute out how each statement is connected to the next and why it's written in that way.


I have written down each step but am totally flummoxed by the concept of a program feeding itself (or part of itself) as input.

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 5:06 pm UTC

yes, that makes sense. it will help to understand the idea of encoding something
often, we want programs to take other mathematical objects as input, such as pairs of numbers, lists of pairs of numbres, or even other computer programs

however, formally, computer programs can only take strings as input, so we can't input anything we want. there are rules!
luckily, we can encode all these mathematical objects into a string. for example, the pair (1,2) may be encoded as 1#2, or a computer program P might be encoded by a binary string 010101110001110.

if you've ever written a program which takes command line arguments, this should make a lot of sense -- all you get is some ascii string from the shell, and it's completely up to you to parse the string into numbers or boolean flags or whatever you want.

something to notice is that any computer program you've written already has a nice encoded representation -- the source code is the encoded version of the program. be careful to distinguish the encoding (the source code) from the actual computer program, which is an abstract mathematical object. the fact that "computer program" is often used to refer both to the mathematical object and the source code is a bit confusing

so to answer your question, a program always takes an input as a string, however, it can interpret that input as a computer program. when i say we run D(<D>), it means we take the program D, encode it into some string, and feed D that string.

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 5:15 pm UTC


so to answer your question, a program always takes an input as a string, however, it can interpret that input as a computer program. when i say we run D(<D>), it means we take the program D, encode it into some string, and feed D that string.


Is there some way to distinguish between the string-use of D and the program-use of D?

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 5:16 pm UTC

yes, we write D to represent the program (program-use), and <D> to refer to the "string-use" (aka encoded) version of D

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 5:17 pm UTC

>-) wrote:yes, we write D to represent the program (program-use), and <D> to refer to the "string-use" (aka encoded) version of D


Working through everything with pen and paper, I don't know that I understand how a program gets fed to itself. The string/program distinction--and its significance--are limiting my understanding.

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 5:21 pm UTC

try to think of them as physical machines instead of programs. a machine takes in a string as an input, and spits out yes, no, or loops forever
now if you try to put one machine D inside another machine M, that's not possible, because machines can only take string as input.

so what we do instead is to write down a string which describes the machine D. call this description <D>. Then we are able to feed the string <D> into M.

as for the significance, the idea of encoding is needed to make the proof rigorous, becuase machines are only allowed to take string as inputs. it also helps solve confusion which arises from "how can you have one computer program in another compter program" type questions. however, i don't think too much is lost if you drop the idea of encoding and just take everything at face value
Last edited by >-) on Mon May 01, 2017 5:24 pm UTC, edited 1 time in total.

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 5:24 pm UTC

>-) wrote:
MathDoofus wrote:
First we suppose that we have some program M, such that M(x) tells us if the program and input pair encoded by x will halt. In other words, M tries to parse x into some pair (D,y) and tells us if the computation D(y) wil halt



I've written everything down, and my first question is what the term "computation D(y)" means. I understand that M(x) means that a program M takes x, and that x represents both a program and some pair of inputs.

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

Re: Halting Problem

Postby gmalivuk » Mon May 01, 2017 5:26 pm UTC

D(y) means program D takes y as input

"computation D(y)" is the whole process (all the steps) of program D running with input y

The key here is that y can also be any string, including strings that represent a program
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

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

Re: Halting Problem

Postby gmalivuk » Mon May 01, 2017 5:30 pm UTC

If your program is just

Code: Select all

print y

Then in binary (if it's understood as ASCII), that's 01110000 01110010 01101001 01101110 01110100 00100000 01111001

As a decimal number, this is 31,650,994,541,830,265. We could set y=31650994541830265 and then run the program on that number, which is a representation of the program itself (without any particular inputs). This is a simple example of what it means for a program to get "fed to itself". If the program that just prints the input is D, then we could say 31650994541830265 is <D>.

We could also use

Code: Select all

print y///37

to refer to the program "print y" with input "37". This whole string is 01110000 01110010 01101001 01101110 01110100 00100000 01111001 00101111 00101111 00101111 00110011 00110111, which corresponds to the integer 34,800,636,529,417,086,195,106,526,007.

The proposed halting tester M gets fed this kind of input (a program together with the input given to that program), which can still be seen as a single input string.

Interesting things start to happen when we look at things like D(<D>), which can be referred to as

Code: Select all

print y///31650994541830265

This corresponds to the integer 46257980346036404000959153228074491682832423871491376727551260213.
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 » Mon May 01, 2017 5:35 pm UTC

gmalivuk wrote:D(y) means program D takes y as input

"computation D(y)" is the whole process (all the steps) of program D running with input y

The key here is that y can also be any string, including strings that represent a program


Abstracting away all of the notation/syntax (everyone has done a fine job of trying to explain the proof by contradiction, but my math learning disability means that the complicated and self-referential notation keeps me from understanding the substance), here's how I've tried to conceptualize the Halting Problem and its proof by contradiction.

I have a Master Algorithm that purports to answer (correctly) the ultimate question in every single case, which is "will it halt?" The Master Algorithm can take any string (or program, because I have no idea what the difference is between the two at this point) and answer the above-listed question.

I have a Master Program that uses the Master Algorithm. In particular, when the Master Algorithm says "yes" to the question "will it halt?" then the Master Program says to loop infinitely. And when the Master Algorithm says "no" to the question, the Master Program says to halt immediately.

What's the next step, and what am I missing?

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3032
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Halting Problem

Postby Qaanol » Mon May 01, 2017 5:44 pm UTC

All right, how about this:

For some reason, your boss sends you a whole bunch of programs and a whole bunch of data files, and wants you to determine which programs will run forever when given which data files as input. At first you just start dragging files onto programs and waiting to see how long they run, but some of the programs run for a really long time with some of the files. You think they might run forever, and you can’t wait that long.

So you post online asking for help, and pretty soon somebody emails you back with an attachment, claiming that the attachment is a program that does what you want. Just drag a program and a data file onto it, and it’ll tell you whether the dragged-in program will run forever with the dragged-in data file. Since all programs that get sent as email attachments from strangers are always totally safe, you start using it. And it seems to work.

But you start to wonder, does the attachment *really* do what was claimed? Or is it possible to create a program and a data file for which the attachment will give the *wrong* answer? Hmm…

Let’s try to write a program and a data file that will trick the attachment. How can we do it?

Okay, we’re going to want our new program to run the attachment as a subroutine. The attachment always halts (allegedly) so that is fine. We’ll run the attachment with some input program and data file yet to be determined. If the attachment says it will halt, then we make our program loop forever. And if the attachment says it will run forever, we make our program halt.

Now the tricky part is to make it so that when our program is run with some data, that we call the attachment to ask if it thinks our program will run forever using that data. In other words, we want to ask the attachment, “Hey, is this exact thing I am doing right now going to halt?” and if it says yes then we do not halt, and if it says no then we do halt, so the attachment will be wrong.

The input data that our program needs is just the program that it will ask the attachment to analyze. And that program is…itself. So we will run our program with *itself* as input. Our program, given itself as input, will run the attachment to ask whether it (our program) will run forever when given itself (our program) as input. Does that make sense?

No matter what the attachment answers, it will be wrong. Because we designed our program to take the answer and do the opposite. The attachment cannot possibly give the right answer for whether our program will run forever with itself as input. Because if it says our program will run forever, then our program will halt, and vice versa. That is what we created our program to do.

That is the main idea.

The rest of it is just bookkeeping to squish the two inputs (program and data) into a single file so that each program only takes one formal input. But that is just a matter of concatenating two files, with some way to indicate how long each part of the file is so the program can separate the sections and treat them as two inputs.
wee free kings

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 5:59 pm UTC

Qaanol wrote:
Okay, we’re going to want our new program to run the attachment as a subroutine. The attachment always halts (allegedly) so that is fine. We’ll run the attachment with some input program and data file yet to be determined. If the attachment says it will halt, then we make our program loop forever. And if the attachment says it will run forever, we make our program halt.

Now the tricky part is to make it so that when our program is run with some data, that we call the attachment to ask if it thinks our program will run forever using that data. In other words, we want to ask the attachment, “Hey, is this exact thing I am doing right now going to halt?” and if it says yes then we do not halt, and if it says no then we do halt, so the attachment will be wrong.



But how does a program containing self-contradictory (or paradoxical) instructions prove that the attachment won't work? In other words, does it matter whether the attachment itself halts or whether it gets the answer right as to whether whatever it's fed will halt?

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3032
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Halting Problem

Postby Qaanol » Mon May 01, 2017 6:36 pm UTC

MathDoofus wrote:But how does a program containing self-contradictory (or paradoxical) instructions prove that the attachment won't work? In other words, does it matter whether the attachment itself halts or whether it gets the answer right as to whether whatever it's fed will halt?


No instructions are paradoxical nor self-contradictory. We have written a program that looks like this:

Code: Select all

main(input: file) {
  if willHalt(program: file, data: file) {
    while true {}   // infinite loop
  }


That is a perfectly well-formed program. It takes a program file as input, calls another program (named “willHalt”) passing the input file as both arguments, and then either exits or loops forever depending on what that program returns.

The person who sent us the “willHalt” program claims that, when given a program and a data file, it will determine whether the input program would run forever given the data file as input. There are two parts to that claim:

1. The “willHalt” program halts for any input.
2. The return value of “willHalt” answers the question “Will the input program halt when run on the input data?”

Now, let us run “willHalt” by dragging onto it a program and a data file. The program is our new program, and the data file is *also* our new program.

If the “willHalt” program does what is claimed, then it will halt (by claim 1) and its return value (by claim 2) will answer the question “Will our program halt when run with itself as input data?”

So let us consider every possible outcome:

If “willHalt” runs forever with these inputs, then claim 1 was false.

If “willHalt” returns “true”, then we know, by looking at how our program is written, that our program will loop forever, so claim 2 is false.

If “willHalt” returns “false”, then we know, by looking at how our program is written, that our program will exit quickly, so claim 2 is false.

If “willHalt” returns something other than “true” or “false”, then claim 2 is false.

In every possible scenario, at least one of the claims about “willHalt” is false. Therefore the program “willHalt” cannot possibly do what is claimed. We have found an input program and data file for which “willHalt” does *not* correctly determine whether the input program will halt when run on the input data.

Notice that we do not know anything about how “willHalt” works. It could be *any* program. No matter what “willHalt” actually does, we can write the program we wrote, and guarantee that the 2 claims are not both true. Therefore, *any* program that claims to do what “willHalt” was claimed to do, does not actually do that. There is no program that can possibly satisfy those claims, because we can always write the program we just described to call it and do the opposite.
Last edited by Qaanol on Mon May 01, 2017 6:54 pm UTC, edited 2 times in total.
wee free kings

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 6:38 pm UTC

>-) wrote:Now we're going to find some program D and input y which will cause M to mess up.
D(y) does the following: Interpret y as the encoding of some computer program, then we will encode the pair (y,y) and run M(<y,y>).


I've gone over everything again with pen and paper, and this is the first sentence from the example that I don't understand at all. Program D has input y, but what is the significance of (y, y) and how in the world can the Program M run (y, y) (when the first part of the example said the Program M takes x as input)?

>-)
Posts: 496
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: Halting Problem

Postby >-) » Mon May 01, 2017 6:41 pm UTC

(y, y) is a pair, which is encoded as string x, so x = <(y,y)> which i've written with a bit of notation abuse as x = <y,y>

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 6:44 pm UTC

>-) wrote:(y, y) is a pair, which is encoded as string x, so x = <(y,y)> which i've written with a bit of notation abuse as x = <y,y>


Gotcha. I'm going to have to drop my question because I'm just not capable of getting it. There are too many layers of programs, strings, and input for me to keep straight. I still can't make sense of a program calling itself. My apologies. Thank you for your efforts and for your patience!

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

Re: Halting Problem

Postby MathDoofus » Mon May 01, 2017 6:46 pm UTC

Qaanol wrote:
The person who sent us the “willHalt” program claims that, when given a program and a data file, it will determine whether the input program would run forever given the data file as input. There are two parts to that claim:

1. The “willHalt” program halts for any input.
2. The return value of “willHalt” answers the question “Will the input program halt when run on the input data?”

Now, let us run “willHalt” by dragging onto it a program and a data file. The program is our new program, and the data file is *also* our new program.



What is the significance of willHalt halting for any input in 1. above? Isn't that implied by 2., which says that willHalt returns a value no matter what's fed to it?


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests