Ian Wild <email@example.com> 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:
which points to such things as:
...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.
Information & Randomness: A Survey of Algorithmic Information Theory
...The random number Omega, the halting probability. Hilbert's 10th
Rob Warnock, 8L-846 firstname.lastname@example.org
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