Peter Wegner (pw@cs.brown.edu)
Sun, 9 May 1999 23:34:38 -0400 (EDT)
> ** The classes CS and CE can be nonenumerable, having the cardinality of the reals. In particular if CE is the real world environment W, the number of possible worlds is nonenumerable. The fact that the real world has the cardinality of the real numbers is clearly something that was understood by mathematicians when the term "real numbers" was introduced.
That is a point of contention with philosophers since no pointer is
observed with a real valued resolution. Our observations have a finite
bound of accuracy, thus the idea that |W| = |R| is an inference, not an
empirical fact. But, the fact that we can think of such ideal objects
that are not directly observable is extraordinary. R. Penrose's thinking
(that we have discussed in the past) that we can somehow have access to
the Platonic Realm is analogous... ;)
** This is not a matter of philosophy but of mathematics. One of the principal results of the paper "Interaction, Computability, and Church's Thesis" shows that the extension from induction to coinduction extends definition and reasoning from enumerable to nonenumerable domains.
SIM environments have the cardinality of the reals: this follows from our reduction of SIM semantics to non-well-founded set theory (section 3 of the paper). The streams over a finite alphabet have the cardinality of the reals, as opposed to strings which have the cardinality of the integers.
Though we perform only finite computations our models of both TMs and interaction machines are infinite. The infinity of TMs is expressed by enumerable sets of strings while the infinity of IMs is expressed by nonenumerable sets of streams.
Since the real world W has at least the cardinality of SIM environments it has
the cardinality of the reals. This is a proof, not a philosophical conjecture. However, by all means try to pick holes in this reasoning.
** There is a new version of the paper "Interaction, Computability, and Church's Thesis" on my home page that goes more deeply into issues of expressiveness and
is generally an improvement on the previous draft. You may wish to download it and read the new version.
This archive was generated by hypermail 2.0b3 on Sun Oct 17 1999 - 22:10:31 JST