Re: poly: Infinite calculations in an open universe?

Hal Finney writes:
> In the case of the computation, suppose every time you solve one problem
> you generate 10 new ones. You still are able to get to every problem
> eventually. You generated problems 0-9 at time 0, problems 10-19 at time
> 1, problems 20-29 at time 2, and in general problems 10n - 10n+9 at time n.
> You are still able to retire problem x at time x, so every problem gets
> dealt with in its turn and there are no problems which never get solved.

You are making an implicit assumption, which is that the number of
problems is countably infinite. It is not. Cantorian set theory shows
that many sets are NOT mappable into the integers.

The computing cycles available in the universe, even if infinite, are
mappable into the integers. However, it is trivial to state classes of
problems that map into the reals, and a trivial diagonalization
argument shows you can't map the one into the other.

Perry
Received on Wed Dec 10 03:45:31 1997