Indeed, the proof of the halting problem is much easier to sketch than the proof of Godel's incompleteness theorem (which the OP doesn't even attempt). So here he goes: a proof sketch of the halting problem for 12 year old programmers.
Suppose that somebody wrote us a program that can check whether another program will loop indefinitely or eventually halt when run on a particular input:
bool halts(string program, string input){
// halting checking code that checks
// whether program's main function
// halts when given input
// returns true or false
}
For example:
string program =
"void main(string foo){" +
" if(foo[0] == 'a'){ return; }" +
" else{ while(true){} }" +
"}";
halts(program, "abc") // returns true
halts(program, "bar") // returns false
Now we can write the following program:
bool halts(string program, string input){
// same halting checking code as above
}
void main(string program){
if(halts(program, program)){
while(true){ }
}
}
Note that this is a perfectly valid program. halts() is supposed to work on
any program, including a program that happens to contain the source code of halts(). We can just reuse the code that the person gave us and copy-paste it here.
Now the question is: what will our halts() function say about this program, when given its own code as input? In other words: what will the following code print?
bool halts(string program, string input){
// same halting checking code as above
}
void main(){
string program =
"bool halts(string program, string input){" +
" // same halting checking code as above" +
"}" +
"void main(string program){" +
" if(halts(program, program)){" +
" while(true){ }" +
" }" +
"}";
print(halts(program,program));
}
There are just 2 possibilities: either this program prints true, or this program prints false (if this program never terminates then halts() has a bug).
Case 1: suppose halts(program,program) returns true.
If the halts function is working correctly, that means that when we actually run the code in `program` with `program` as its input, it will halt. But now lets see what actually happens. When we run the main() function in `program` with `program` as its input, it first checks `if(halts(program,program))`. Well, we already assumed that halts returns true, so control flow will go inside the if block to the infinite loop. But that means that halts lied to us!
Case 2: suppose that halts(program,program) returns false.
Now a similar argument holds. run the code in `program` with `program` as its input, the condition of the if statement will be false, and the main function will terminate. So even though halts(program,program) returns false, the program actually terminates. It lied again!
As you can see, no matter what halts returns, it cannot tell the truth about the program we constructed. Hence it is impossible to fill in the missing code in halts() so that it will work correctly.