How would you describe Turing's Halting Problem to a 13-year-old? originally appeared on Quora - the place to gain and share knowledge, empowering people to learn from others and better understand the world.
A reasonably curious and patient 13-year-old should have no trouble understanding the Halting Problem precisely as it is, without any need for analogy or metaphors.
Making sure they understand the whole thing, including the proof of non-existence of an algorithm, may take patience and attention to their reactions and level of understanding, but it should not be beyond their abilities to follow.
Here's a slightly informal but intuitively clear statement of the Halting Problem: is there a computer program that can look at the code of any other program and decide if that other program will ever stop running?
And then, here's a quick and intuitive description of the solution: There is no such program. If there had been one, we could run it on a version of itself which halts if it determines that the other program never stops, and runs an infinite loop if it determines that the other program stops. Contradiction ensues.
That's all there is to it, but admittedly it's pretty vague. To make it more precise, read on.
Make sure the kid understands the idea of a computer program. In this day and age, this should not be difficult at all; the main thing to emphasize is that a computer program simply processes a piece of data and does something with it, sometimes eventually finishing and sometimes not.
This feels a bit different from programs they may be familiar with, like Pokémon Go or Photoshop, but it should not be difficult to explain that programs don't have to involve interactive user input. For the purposes of this discussion, a program simply processes some input, provided to it in the form of some file.
For example;
- A program may read up to 100 numbers, add them up and print out the result. This program will always stop, whatever the input is. (If the input happens not to be a list of numbers, the program should just stop with an error message).
- A program may read a number, and then start counting from 1 until it reaches that number, at which point it stops. This program will halt rather quickly if you give it the input 23, it will halt after many years if you give it the input 23^23, and if you give it the input 0 it will simply run forever.
This example may generate an interesting discussion about memory capacity and what happens if the counter becomes so large the computer can no longer store it. Most kids won't actually be bothered by this: the idea of counting 1,2,3,4,…, possibly forever, would seem totally natural to them. If they do wonder about that, clarify that for this discussion they may assume an ideal computer with unlimited memory.
One final example:
- A computer program that doesn't require any input. It scans the even numbers 4,6,8,10,… in order, and for each one it checks all the ways to write this number as x+y for positive integers x,y. When it finds such a pair x,y that are both prime, it moves on to the next even number. If it can't find any such pair, it prints the string “GOLDBACH WAS FREAKIN’ WRONG!!!”
This program is not at all hard to write. Checking whether an integer is prime is a simple matter. Doing it efficiently is a bit trickier, but for the present discussion we don't care at all about efficiency.
Does this program ever halt? Nobody knows, and this is a good example to clarify that checking if a program ever halts is no simple business. This is the most important example. If they understand it, they understand why it's almost insane to expect that we can correctly predict if a given program halts.
You can give similar examples with the 3n+1 problem, or finding an odd perfect number, or many other difficult or open problems. Whatever works for the kid in question.
With those examples out of the way, we point out that a computer program is itself just a piece of text. Many 13-year-olds already did a bit of programming, and if they didn't, we can just show them a piece of code or pseudo-code, for example the code that performs any of the examples we just went over.
This code isn't a particularly well-written program, but it doesn't matter. It's pretty clear what it does, and it's pretty clear what's going to happen if N is 23 and if N is 0.
Now we can describe a bit more precisely what the Halting Problem is.
Is there a computer program which reads the code and required input of some other program, and decides if that other program will ever terminate if run on that input?
That's it. This is the Halting Problem. And the answer to that question is No. There cannot be any computer program that successfully performs that task.
Why?
Well, imagine a magical program M which reads as input a code C and an input I, and determines correctly if C will halt on input I. Note that M requires two pieces of input: the code C of the program it's examining, and a piece of input I for C to run on, in case C needs some input to do its thing.
Also note that M always eventually halts: after it’s done analyzing the program C running on the input I, it says “Yes, C will stop given input I” or “No, C will never stop given input I.”
Now let's build a slightly more elaborate program P. This program receives input J, and what it does is this: it duplicates J into two copies, and then runs magical program M with the two copies of J as inputs (Remember that M takes two pieces of input, so we give it (J, J)). Program M says either “Yes” or “No”. If it says Yes, our big program P enters an infinite loop. If M says “No”, P stops.
P is a pretty simple program, built around the program M. You can even write in in actual code, at one point invoking a call to M.
Now let's run P with its own code as input, meaning that input J that P expects, we just let it be the code of P itself. Remember, as always: code is just a bunch of text.
What P does now is ask M: “what happens when P runs with input P?”, which, behold, is exactly what we are doing. And whatever M says will happen, P makes sure to do the exact opposite. So M could not have correctly predicted what happens in this peculiar situation. But M was supposed to always answer correctly.
Well, it can't, and that's a somewhat informal but pretty accurate summary of Alan Turing’s great discovery: there are things that cannot be computed, regardless of speed, space, resources or cleverness.
This question originally appeared on Quora - the place to gain and share knowledge, empowering people to learn from others and better understand the world. You can follow Quora on Twitter, Facebook, and Google+. More questions: