|
It's not often that I learn about things that I'm genuinely intrigued by in high school, but this is an exception. The halting problem, which is, I'm assuming, a staple of computability theory, asks the question, “is it possible to make an algorithm that can, for all cases, tell you whether a given computer program with its input will terminate?” The answer is an emphatic no because of an ingenious counterexample.
Let us suppose that I am on my deathbed, having wasted away my entire life coding a (supposed) solution to the halting problem. I shall from here replace all forms of “halt” with “terminate” since I'm not a silly Brit. This is America.
terminates(prog,input)
#codified product of sweat, blood, junk food and tears goes here
#True if program terminates
#or False if program does not terminate.
Since any program can itself be represented in its most elementary form as binary data, we can check to see if a program terminates with itself as input with this function:
self-terminates(prog)
#if terminates(prog,prog) is True, self-terminates runs forever
#if terminates(prog,prog) is False, self-terminates exits.
Thus if a program terminates when given itself as input, self-terminates goes into an infinite loop. If it does not terminate, self-terminates simply terminates. To say it another way, self-terminates terminates only if the provided program would not terminate on itself.
Now, what if we tried to run the code self-terminates(self-terminates)? If terminates(self-terminates, self-terminates) terminates, then an infinite loop would occur in self-terminates(self-terminates). (Note that the result of this should be what terminates(self-terminates, self-terminates) gives.) To say it another way, if self-terminates terminates on itself, then it must loop indefinitely. The problem is obvious. The only other possible case is that terminates(self-terminates, self-terminates) is false, but it's not: this would mean that self-terminates(self-terminates) would indeed terminate. The halting problem is unsolvable for a general case because of this counterexample.
I tried to make my explanation as simple as possible, but it took me at least an hour to fully wrap my head around this. Even now I'm not even sure if my explanation is correct. If you think you can make sense of more formal discourse on this (because shit, I can't), there's an entire wikipedia article dedicated to this in addition to numerous sites on the web. I've really been enjoying my Artificial Intelligence class.
|
That's awesome that you think this stuff is interesting. Theoretical CS is pretty sweet.
Out of interest, what high school do you attend? My high school has a really strong CS program but I wish I had more exposure to theoretical results like the halting problem.
Also, the halting problem is actually *decidable* for some programming languages. Your counterexample assumes your language allows you to write such programs. Coincidentally, this very morning I went over a proof of termination for programs in Godel's T for the type theory class I am TAing.
|
http://en.wikipedia.org/wiki/Tjhsst I go there. The old AI teacher stepped out this year to work on his doctorate, so a veteran math/CS teacher stepped in for him and has basically made up the course as he's gone along. After he introduced us to Python we began working on genetic algorithms and now we're just starting our study of Turing. I'm having a really good time.
I love abstract stuff like this, but my ability to comprehend this kind of thing is about average when compared to my classmates'. Same thing for BC calc. If I ever go into a CS field it'll be programming 
edit: yes, that proof below me is a lot less convoluted. thanks!
|
Here's a simple proof of the halting problem that I think is a bit clearer:
The Halting Problem is:
INPUT: A string P and a string I. We will think of P as a program.
OUTPUT: 1, if P halts on I, and 0 if P goes into an infinite loop on I.
Theorem (Turing circa 1940): There is no program to solve the Halting Problem.
Proof: Assume to reach a contradiction that there exists a program Halt(P, I) that solves the halting problem, Halt(P, I) returns True if and only P halts on I. The given this program for the Halting Problem, we could construct the following string/code Z:
Program (String x)
If Halt(x, x) then
Loop Forever
Else Halt.
End.
Consider what happens when the program Z is run with input Z
Case 1: Program Z halts on input Z. Hence, by the correctness of the Halt program, Halt returns true on input Z, Z. Hence, program Z loops forever on input Z. Contradiction.
Case 1: Program Z loops forever on input Z. Hence, by the correctness of the Halt program, Halt returns false on input Z, Z. Hence, program Z halts on input Z. Contradiction.
End Proof.
http://www.comp.nus.edu.sg/~cs5234/FAQ/halt.html
It's cool that you're into this stuff.
|
I went to tj  Class of 2008. I'm a CS junior at CMU right now and am (probably) going to graduate a semester early. I'd be happy to talk to you about college stuff - I wish I had done so when I was in high school. If you wish, we can take this conversation offline so as to not derail your blog.
Who is this veteran teacher who speak of? If I had to guess, I'd say Mr. Steuben.
|
I'm a CS major, but this is probably my least favourite area in cs we studied so far.. I usually don't like it when people say "this has no real-life applications," but I think its true for once in this case.
|
Oh my goood. I'm going to blow up your PM box at some point—for now I have to finish my Vergil lines. CMU is a school I was really considering, so that's awesome.
Yes, it's Stueben, lol. The guy's strange and amazing. It's terrible that Latimer and Torbert both had to leave the year after I finished APCS since I've heard such great things about them, but Stueben and the new guy, Gabor, are both pretty cool too I guess.
|
The best, intuitive way I've heard to get a quick grasp the halting problem and related questions is this: imagine you have a program that does indeed tell you the answer to the halting problem. This would be the singular most powerful program in the world, because for any quantitative problem ever, you can simply make a program along the lines of "Search for Answers to Problem X" and then run that program and input into your Halting Program. For instance you could write a program looking for answers to Fermat's Last Theorem. Run the Halting program on that and, hey, you've proven it affirmatively or negatively. Or maybe write a "Search for Cancer Cure with Peptide A" etc. To boil it down to a simple rule: to ascertain every aspect of a program/machine/language, you have to run it. There are no clever shortcuts.
On a related, more mind-blowing note, you'll eventually get to things called Turing Machines, which end up being models for any sort of digital device you can imagine. Using those, you'll prove that it is actually impossible to determine any meaningful characteristic of programs at all!
|
On March 17 2011 15:11 petergibbons wrote:
Oh my goood. I'm going to blow up your PM box at some point—for now I have to finish my Vergil lines. CMU is a school I was really considering, so that's awesome.
Yes, it's Stueben, lol. The guy's strange and amazing. It's terrible that Latimer and Torbert both had to leave the year after I finished APCS since I've heard such great things about them, but Stueben and the new guy, Gabor, are both pretty cool too I guess.
Wow, what a coincidence. I had Steuben for Accelerated Intro CS. And I took Latin all 4 years.
|
Wait a minute. is your last name Hong?
|
On March 17 2011 15:11 Assault_1 wrote:
I'm a CS major, but this is probably my least favourite area in cs we studied so far.. I usually don't like it when people say "this has no real-life applications," but I think its true for once in this case.
Uh, the people who say that are the opposite of right (read: they are wrong). THIS is the theorem which says that it's actually impossible to test (certain) programs in (certain) languages (see my above post for details) AT ALL. Surely you think it's nice to know that you cannot naively expect every program to terminate?
|
On March 17 2011 15:17 petergibbons wrote:
Wait a minute. is your last name Hong?
PM me.
|
On March 17 2011 15:18 haxorz wrote:Show nested quote +On March 17 2011 15:11 Assault_1 wrote:
I'm a CS major, but this is probably my least favourite area in cs we studied so far.. I usually don't like it when people say "this has no real-life applications," but I think its true for once in this case. Uh, the people who say that are the opposite of right (read: they are wrong). THIS is the theorem which says that it's actually impossible to test (certain) programs in (certain) languages (see my above post for details) AT ALL. Surely you think it's nice to know that you cannot naively expect every program to terminate?
To put it more simply, no program can (perfectly) detect infinite loops. When I was 13 or so, I thought that interpreters/compilers should have a button to detect infinite loops, saving me the trouble of debugging them. So I've always thought of the halting problem as having real-world applications.
|
On March 17 2011 15:11 pullarius1 wrote:
The best, intuitive way I've heard to get a quick grasp the halting problem and related questions is this: imagine you have a program that does indeed tell you the answer to the halting problem. This would be the singular most powerful program in the world, because for any quantitative problem ever, you can simply make a program along the lines of "Search for Answers to Problem X" and then run that program and input into your Halting Program. For instance you could write a program looking for answers to Fermat's Last Theorem. Run the Halting program on that and, hey, you've proven it affirmatively or negatively. Or maybe write a "Search for Cancer Cure with Peptide A" etc. Very oversimplified, in my opinion, because all a "Halting Program" is guaranteed to do is return an answer in some finite time--it could be a billion years. If time weren't a practical consideration, then brute force search would more or less be "the most powerful program in the world".
To boil it down to a simple rule: to ascertain every aspect of a program/machine/language, you have to run it. There are no clever shortcuts. This is oversimplified to the point of being wrong (imo). The point of the halting theorem is that you can't "ascertain every aspect of [every] program/machine/language" at all--including by running it. It's not that there are no shortcuts to discovering that a given program halts on a given input--it's that there is no way at all.
|
|
|
|
|
|
EPT
