Countable vs Continuous

From: <>
Date: Thu, 21 Jun 2001 11:24:25 +0200

There has been some confusion regarding the various kinds of infinity.

There is the rather harmless kind: the countable one. And some say there
is another kind, a strange one, the one associated with the uncountable
continuum, the one whose very existence many deny.

Do not lump them together.

The former is accessible by nonhalting computer programs. The latter is not.

A program that runs forever cannot consume more than countable time steps
and storage cells, adding a new cell whenever it needs one. For example,
countably many steps and cells are sufficient to print all digits of
the real number Pi. Therefore Pi is "computable in the limit."

But countable time and space resources are NOT sufficient to print all
digits of all random reals in the continuum. In fact, countable resources
are not even sufficient to print all (countably many) digits of a single
real without finite individual description. Unlike Pi, such truly random
reals (and almost all reals are truly random) are NOT computable in the
limit, although all their finite beginnings are.

Pi has a finite description. Are all infinite objects with finite
descriptions computable in the limit? No. Counter example: Infinite Omega
(the halting probability of a universal Turing machine with random input)
has a finite description, but countable resources are NOT sufficient
to print it, although each finite beginning of Omega is computable in
the limit.

Algorithmic TOEs are limited to the comparatively few, countably many,
possibly infinite universe histories with finite descriptions. ATOEs deny
the existence of other histories, of histories we cannot even describe
in principle, of histories we cannot reasonably talk about.

Likewise, ATOEs are restricted to probabilities computable in the limit.
We cannot formally describe other probabilities, and therefore cannot
write reasonable papers about them. This apparently harmless restriction
is the very reason that any complex future (among all the possible
futures compatible with the anthropic principle) necessarily is unlikely.

Juergen Schmidhuber
Received on Thu Jun 21 2001 - 02:26:39 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST