So one way to state
Turing's big thing is:
There's no way to write down an algorithm/recipe that someone could follow by rote and successfully determine what an arbitrary computer program will do. I.e., the output of some programs cannot be predicted based on their rules and initial conditions. I.e., the only way to determine what a random computer program will do is to actually run it and see what happens.*
An example: Suppose I email you a program and tell you run it, promising you that it will fix your botched lasik. You get pretty excited, but you're a little nervous: maybe I'm lying; maybe the program is actually a virus that will delete all the photos of you that I took. Furthermore (thought experiment time) suppose I'm dead and so you can't make me tell you what I was thinking when I wrote it.
But then you think to yourself "Hey, couldn't I just program a computer to search through every line of YOUR computer program, checking for anything that looked bad? Obviously I'd check for the "delete all photos" command, but I could also check for
all delete commands, reasoning that since none are required to make your program function as advertised, they must all be malicious. Maybe I could generalize this reasoning to pick out all potentially malicious parts of your program."
But
as we know from Turing, this is impossible. You can't write a computer program that will determine whether my program is malicious because you can't even write a computer program that figures out what my program does!
"Intuitively though, why is predicting what a computer program will do so hard?" Here's an example of a short program whose behavior is difficult to predict:
int natural_number = 1;
int count = 0;
while (natural_number > 1) {
if ( natural_number is even ) {
natural_number = natural_number / 2;
}
if ( natural_number is odd ) {
natural_number = natural_number * 3 + 1;
}
}
count = count + 1;
natural_number = natural_number + 1;
GOTO LINE 1 (i.e., start over, preserving the values of 'count' and 'natural_number')
The question being "How large does
count get (if in fact it ever stops growing)?".
What's going on? Well, the program applies a certain process to every natural number, starting with 1:
- If the number is even, divide it by two
- If the number is odd, triple it and add one
If this process eventually converges to 1, the program moves onto the next number. If the process
doesn't converge to 1 for the number X, the program will enter into an infinite loop and the highest
count will ever be is (X - 1).
Therefore, to find how big
count gets (if it stops growing at all), we have to figure out the smallest number that doesn't converge to 1 upon repeated application of the above process.
Oh, but oops; that every number converges to 1 (i.e., that
count never stops growing) is the
Collatz conjecture, which, as its name suggests, has not been proved:
The conjecture has been checked by computer for all starting values up to 10 × 258 ≈ 2.88×1018[1]. While impressive, such computer evidence should be interpreted cautiously. More than one important conjecture has been found false, but only with very large counterexamples. (See for example the Pólya conjecture, the Mertens conjecture and the Skewes' number.)
It is also known that {4,2,1} is the only cycle with fewer than 35400 terms (skeet -- ed).
Determining what a computer will do is hard because the behavior of a computer program can depend on whether a tricky mathematical proposition is true or false. Since there's no general recipe for determining whether a mathematical proposition is true**, there's no such recipe for predicting the behavior of computer programs.
* I'm eliding one subtle distinction here for simplicity (SSD).
** Next time I feel like having sex, I'll post something about this.
Everyone, quick, put up a post complaining about how the "holiday season" starts earlier and earlier every year, and you just can't fucking stand listening to Christmas music before Thanksgiving! Have we no shred of decency left? What about the Constitution!
