Halting Problem
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Halting Problem
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?
 Soupspoon
 You have done something you shouldn't. Or are about to.
 Posts: 1837
 Joined: Thu Jan 28, 2016 7:00 pm UTC
 Location: 531
Re: Halting Problem
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 nontrivial and ultimately nonhalting program is going to make you not halt your search for the halt that will not come.
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 nontrivial and ultimately nonhalting program is going to make you not halt your search for the halt that will not come.

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
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 nontrivial and ultimately nonhalting 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.

 Posts: 340
 Joined: Wed Sep 21, 2011 3:44 am UTC
Re: Halting Problem
This video is a pretty good animation of the paradox you get if you assume you can solve the halting problem.
 Soupspoon
 You have done something you shouldn't. Or are about to.
 Posts: 1837
 Joined: Thu Jan 28, 2016 7:00 pm UTC
 Location: 531
Re: Halting Problem
(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...))
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...))

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
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!
Re: Halting Problem
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.

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
>) 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?
Re: Halting Problem
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?
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?

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
>) 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 programwithinaprogram paradox that's apparently the standard method for explaining the halting problem to people like me who are math morons.
Re: Halting Problem
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 ad. If ad <= 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 73=4, that's 1 subtraction. 43=1, that's 2 subtractions. 13=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).
For example, let's say you're dividing 7 by 3. So 73=4, that's 1 subtraction. 43=1, that's 2 subtractions. 13=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
SecondTalon: "Still better looking than Jesus."
Not how I say my name

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
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 ad. If ad <= 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 73=4, that's 1 subtraction. 43=1, that's 2 subtractions. 13=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.
 doogly
 Dr. The Juggernaut of Touching Himself
 Posts: 5142
 Joined: Mon Oct 23, 2006 2:31 am UTC
 Location: Somerville, MA
 Contact:
Re: Halting Problem
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?
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?
Re: Halting Problem
MathDoofus wrote:What I'd like to make sense of now is the programwithinaprogram 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.

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
Can anyone explain the proofbycontradiction explanation of the Halting Problem? I'm having trouble following the various inputs to all of the hypothetical programs.
Re: Halting Problem
what i gave is a proofbycontradiction 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...)

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
>) wrote:what i gave is a proofbycontradiction 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.
Re: Halting Problem
What >) means is you can have a function that has multiple inputs. For example, f(x,y)=xy. So f(5,4)=54=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
SecondTalon: "Still better looking than Jesus."
Not how I say my name
Re: Halting Problem
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)

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
Zohar wrote:What >) means is you can have a function that has multiple inputs. For example, f(x,y)=xy. So f(5,4)=54=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 programwithinaprogram doesn't take multiple arguments? I'm getting bogged down in distinguishing between stuff that's meaningful and stuff that's not.
Re: Halting Problem
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.
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.

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
>) 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?
Re: Halting Problem
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.
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
SecondTalon: "Still better looking than Jesus."
Not how I say my name

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
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.
Re: Halting Problem
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.
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.

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
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 stringuse of D and the programuse of D?
Re: Halting Problem
yes, we write D to represent the program (programuse), and <D> to refer to the "stringuse" (aka encoded) version of D

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
>) wrote:yes, we write D to represent the program (programuse), and <D> to refer to the "stringuse" (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 distinctionand its significanceare limiting my understanding.
Re: Halting Problem
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
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.

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
>) 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.
 gmalivuk
 GNU Terry Pratchett
 Posts: 25399
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Halting Problem
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
"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
 gmalivuk
 GNU Terry Pratchett
 Posts: 25399
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Halting Problem
If your program is just
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
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
This corresponds to the integer 46257980346036404000959153228074491682832423871491376727551260213.
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.

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
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 selfreferential 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 abovelisted 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?
Re: Halting Problem
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 draggedin program will run forever with the draggedin 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.
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 draggedin program will run forever with the draggedin 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

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
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 selfcontradictory (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?
Re: Halting Problem
MathDoofus wrote:But how does a program containing selfcontradictory (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 selfcontradictory. 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 wellformed 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

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
>) 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)?
Re: Halting Problem
(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>

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
>) 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!

 Posts: 247
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Halting Problem
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?