We know that it is impossible to write a program H (P,X) that determines YES or NO whether program P halts on input X. We know that is impossible to write a program H (P) that determines YES or NO whether program P always halts. (YES if P always halts. NO if some input somewhere will cause P to infinite loop.) So, how about this one? Is it possible to write a program N (P) that prints YES if the program NEVER halts and NO if P halts at least on some inputs? REDUCE IT TO THE HALTING PROBLEM. Assume that the above program N(P) exists. Use it to write H (P,X). If you can write H(P,X)--an impossible task--you have to have been using an impossible tool. That's how you know that N(P) also does not exist. First, create program Q that ignores its own input and just runs P on input X no matter what input Q actually gets. Run N(Q). If N(Q) returns YES then Q never halts, which means P doesn't halt on input X (so print NO). If N(Q) returns NO then Q halts, at least sometimes. But since Q always runs the same thing regardless of its input, if Q halts sometimes, it must always halt. So, P must halt on X. So print YES. Ta-da. I've just written H(P,X). So N(P) must not exist. Prove that there is no such program E(P,Q) that accepts two programs P and Q and definitively returns YES if P and Q always behave the same way and NO if P and Q don't always behave the same way. REDUCE IT TO N(P). In other words, assume E(P,Q) exists. Use that to write N(P). Design a program I: while (1); if E(P,I) returns YES then P must never halt so write YES. if E(P,I) return NO then P must halt at least sometimes so write NO. Some professional compilers make the claim that they are able to flag all unreachable lines of code. In other words, they can indicate with colors or whatever which lines of your program will never fire under any circumstances. Prove that such a compiler could not possibly exist. void TrumpLove () { return; cout << "Trump is the greatest!" << endl; } Reduce it to N(P): How would I write N(P) so that it works if I had access to that superduper compiler? N(P): Create Program Q that looks like this: P; cout << "B" << endl; Run Q through the magic compiler and see if it flags the "cout << "B" << endl;" line as unreachable. If that line is unreachable then P must ALWAYS infinite loop. So N(P) returns "YES". If that line is reachable, then P must halt at least sometimes, so N(P) returns "NO". What would the world be like if the Halting Problem could be solved? Consider this programs: read positive integer n from the input. while (1) { if (prime (n) && prime (n+2)) break; n++; } Twin primes: numbers differing by 2 that are both prime. <3,5>, <5,7>, <11,13>, <17,19>, <29,31>, etc. Unsolved problem of mathematics: are there an infinite number of twin primes? If my program ALWAYS halts, then there must be an infinite number of twin primes. If my program doesn't halt, at least sometimes, there must be a point beyond which there are no more twin primes. Thus, if the Halting Problem could be solved, it could tell me whether my program ALWAYS halts or not. [ H(P).] Thus, a simple computer program could tell me if there are an infinite number of twin primes. Lots of famous unsolved math problems can be written as a computer program that may or may not halt. Too bad the Halting Problem cannot be solved! cout << "A" << endl; while (1); cout << "B" << endl; Is there an irrational number raised to an irrational power giving a rational answer? YES. Let x be sqrt(2) ^ sqrt(2). Is x rational? Beats me. If x is rational, then we've found one, hurray! If x is not rational, then consider y = x ^ sqrt(2). x is irrational, by assumption, and sqrt(2) is. (sqrt(2)^sqrt(2))^sqrt(2) = sqrt(2)^(sqrt(2)*sqrt(2)) = sqrt(2)^2 = 2. So there must be such a number. Conway's Game Of Life Imagine you have a two-dimensional grid of cells. Each cell is alive or dead at any time step. Any living cell that is adjacent (horizontally, vertically, or diagonally) to exactly two or three other living cells remains alive in the next time step. If a living cell is adjacent to fewer than two or more than three other living cells, it is dead in the next time step. A dead cell that is adjacent to exactly three living cells becomes alive in the next time step. Otherwise, the dead cell remains dead. ** ** When a pattern stabilizes, we can say that it "halts". But sometimes you get infinite loops. Look at *** * In the next time step, it becomes * * And the following time step, it becomes *** again, and so forth. Can a computer program work out whether a pattern will stabilize or loop? The answer is YES, if the Game of Life is played in a finite grid. The reason for this is that in a finite grid, say mxn, there are a finite number of possible boards. In fact, that number is 2^(m*n)...which is huge, but still finite. If you emulate the Game Of Life, keeping track of which boards you see, as you as come across a repeat, you're done! If you are repeating the very last grid, you've stabilized. If you've repeated a board from further back, you're looping. But, you can definitely answer whether a certain board configuration will stabilize. But, if you let the board become infinite...then the Halting Problem kicks in. You simply can't emulate this if you have an infinite possibilities...it is possible that a grid will never stabilize, but also never be the same thing twice. Game of Life reminded me of real numbers. The decimal expansion of rational numbers either repeats or terminates. But the decimal expansion of irrational numbers goes on forever, without terminating or repeating. Similarly, the Game of Life on a finite grid, will terminate or repeat. On an infinite grid, it's not guaranteed to do either. The Game of Life can represent computer programming in general, and this is literally true, because the Game of Life was proven to be a Turing-Complete language. If your computer program uses a limited amount of storage under all circumstances, if variables never go beyond a certain point, for example. A fixed amount of space is ever allocated. Then, you CAN definitively say whether the program halts. Because there is only a finite amount of states that the program can possibly be in, if you hit the same twice, it must not halt, and you're going to hit all possible states sooner or later. The issue is when the program doesn't have a fixed amount of resources, that number CAN get as large as they need to, that storage can be allocated as high as one wants, THEN that's when the Halting Problem kicks in, and we can't tell for sure whether it halts. For example, consider a program that reads in a numerator, reads in a denominator, and prints the decimal expansion of that fraction until there are no more digits to be printed. 5 / 4 = 1.25 49 / 10 = 4.9 2 / 3 = 0.6666666666666666666 For any given input, this program only uses a finite amount of memory. If I'm dividing by 19, I only need to remember 19 possible remainders, for example. So, for any given input, the resources used are bounded, so I can totally tell whether this program is going to halt. Now, it possible to use arbitarily large resources, I can divide by a 100-digit number or a 200-digit number or whatever...but any one specific input, I am only using a bounded amount of resources. So, I can solve the Halting Problem here. The Halting Problem really kicks in when I'm using an unbounded amount of resources on a specific input. Do I keep allocating space? Do I keep incrementing integers? Do I keep moving that tape arbitrarily far to the right? That's when the HALTING PROBLEM kicks in. "You are interviewing at a laboratory, and they tell you that they are working on the Halting Problem and are getting closer every day to solving it. Are they telling the truth?" My answer: "They might be telling the truth. Working on it and actually solving it are two different things."