Ian Wild <ian.wild@eurocontrol.be> wrote:
+
 "Vilhelm Sj�berg" wrote:
 > The set of programs for a turingmachine 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
 > turingmachine.

 Yup. They're called the noncomputable 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 Sexpression
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, 8L846 rpw3@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 6509331673
1600 Amphitheatre Pkwy. FAX: 6509330511
Mountain View, CA 94043 PPASELIA