Turing used the halting problem to demonstrate that there are some
functions (or numbers) that one can describe but not compute. To see
this, consider that, given any programming language, one can assign a
unique integer to each program. E.g. by sorting the programs in order of
length, and numbering them from 1 upwards. Now, imagine the real number
whose th digit it 1 if the th program halts and otherwise.
Since the halting problem can't be solved, it's impossible to compute
this number. Nevertheless, it is true in fact that every program *does* either halt or fail to halt. Hence every digit of must be
either 0 or 1. But we can never know which.

Wed Feb 14 23:47:23 GMT 1996