**Peter Wegner** (*pw@cs.brown.edu*)

*Sun, 9 May 1999 23:34:38 -0400 (EDT)*

**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Stephen P. King: "[time 296] Re: [time 295] Re: [time 291] Re: Expressiveness of interactive computing"**Previous message:**Stephen P. King: "[time 294] Re: [time 293] Re: [time 291] Re: Expressiveness of interactive computing"**In reply to:**Peter Wegner: "[time 293] Re: [time 291] Re: Expressiveness of interactive computing"**Next in thread:**Stephen P. King: "[time 296] Re: [time 295] Re: [time 291] Re: Expressiveness of interactive computing"

*> ** 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.

**Next message:**Stephen P. King: "[time 296] Re: [time 295] Re: [time 291] Re: Expressiveness of interactive computing"**Previous message:**Stephen P. King: "[time 294] Re: [time 293] Re: [time 291] Re: Expressiveness of interactive computing"**In reply to:**Peter Wegner: "[time 293] Re: [time 291] Re: Expressiveness of interactive computing"**Next in thread:**Stephen P. King: "[time 296] Re: [time 295] Re: [time 291] Re: Expressiveness of interactive computing"

*
This archive was generated by hypermail 2.0b3
on Sun Oct 17 1999 - 22:10:31 JST
*