Ian Wild  <ian.wild@eurocontrol.be> wrote:
+---------------
| "Vilhelm Sj�berg" wrote:
| > The set of programs for a turing-machine is isomorphous with the set
| > of finite bit strings.  The set of finite bitstrings is countable.
| > Hence, there are real numbers which cannot be computed by a
| > turing-machine.
| 
| Yup.  They're called the non-computable reals.
| I believe, though I can't find a reference just at the moment,
| that one of them is "the probability that a randomly chosen
| turing machine will halt".
+---------------

For *much* more along these lines, see:

	<URL:http://www.cs.auckland.ac.nz/CDMTCS/chaitin/>

which points to such things as:

	<URL:http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable/ch5.html>
	...showing why you can't prove that a LISP expression is elegant
	if the LISP complexity of the axioms is substantially less than
	the size of the expression that you're trying to prove is elegant.
	More precisely, we show that a formal axiomatic system of LISP
	complexity N cannot enable you to prove that any S-expression
	more than N + 356 characters in size is elegant. 
or:
	<URL:http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable/ch6.html>
	Information & Randomness: A Survey of Algorithmic Information Theory
	...The random number Omega, the halting probability. Hilbert's 10th
	problem.


-Rob

-----
Rob Warnock, 8L-846		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		FAX: 650-933-0511
Mountain View, CA  94043	PP-ASEL-IA