In this section, I describe the halting problem. As mentioned above, this is another non-computable problem. What's the relevance to AI? See next week. But briefly, if the brain can solve non-Turing-computable problems, then complete AI will be impossible to engineer on Turing-equivalent computers, and any cognitive model running on a Turing-equivalent computer will give an incomplete account of the mind.
Now to the halting problem. Suppose yourself to be a programmer. A client asks you to write a program, ``H'' (in any language, and running on any computer, of your choice) whose specification is as follows. The client is allowed to give it the text of any program as input. Your program, H, must work out (by any means you want) whether the program it was given as input will eventually stop, or go on for ever. If the former, it must print ``Halts''. Otherwise, it must print ``Doesn't halt''.
So, if H is given these programs, it will print ``Halts'':
Program 1:
i := sin(3.1415);
Program 2:
i := 1;
next: if i mod 2 = 0 then goto exit;
i := i + 1;
goto next;
exit:
write("Found an even number");
But with the programs below, it will print ``Doesn't halt''.
Program 1:
next: write("Looping");
goto next;
Program 2:
i := 0;
next: if i>0 and i<0 then goto exit;
i := i + 1;
goto next;
exit: write("Found a negative positive number");
Turing proved that program H is impossible to write. It's a logical impossibility, not a restriction imposed by technology or skill, in the same way that no number can be both odd and even, or no person can be both taller than 6 feet and shorter than 5. To prove it, Turing showed that if such a program existed, it would, when given itself as input, both halt and run forever. Since this is impossible, program H must be impossible too.
Obviously, you can analyse that some programs will or won't halt
- e.g. by looking for patterns like l: goto l. But that's
impossible in all cases. To see why, consider a program constructed to
generate the digits of 
, and stop only if it finds a string of 9
9's. It would not be easy to write a pattern recogniser that tells
whether this would ever halt!
But it's easy to state what H must do: I just have. Therefore, there is at least one task you can define, but not make a computer do.