[time 296] Re: [time 295] Re: [time 291] Re: Expressiveness of interactive computing

Stephen P. King (stephenk1@home.com)
Mon, 10 May 1999 00:31:28 -0400

Hi Peter,

        We are up late. ;) I am trying to get the baby to sleep... :)

Peter Wegner wrote:

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

        I believe that |W|=|R|, but I am merely saying that we can only infer
this fact.

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

        There is a thread on David Deutsch's FOR list that seems to echo
something analogous to this. Unfortunately David is fixated on UTMs. :(
See the attached post...

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

        What I am particularly fascinated by is how the knowledge base of an IM
increases by allowing it to interact. There is one think that is giving
me a little trouble wrapping my brain around ("groking"), it is how it
is that IMs, like any other machine or LS, is a black box to another. A
given LS can only observe a surface cross-section and not a volume of
another. I think this is a theorem waiting exploration! The discussion
by Chris Hillman noting that Shannon Information is volume and Fisher
info. is area (I think :) ) I think is involved!

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

        I agree with it, so I have a hard time picking holes in it. :) But, we
must aways seek falsification. I remember telling my friend Al, that any
observation is a sequence of negations, e.g. when we ask what something
is, we are segregating out what it is not. I need to follow this up.
> ** 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.

        I will! I have always enjoyed your papers. :)



Subject: Cantgotu environments
Date: Sat, 8 May 1999 11:58:59 EDT
From: Rachel Dugdale <REDugdale@AOL.COM>
Reply-To: "The Fabric of Reality List: The Work of David Deutsch" <FOR@LISTSERV.TCS.AC>

I think that Charlie Uniman's two questions basically address the same issue;
that of infinity. Starting with #2 (sorry!):

>Question #2: Again, what is it about physical reality's discreteness that
>requires that "physical objects can interact [only in a way] which would allow for [a
>finite] numbers of steps [preceding] a measurable conclusion"?

If something required an infinite number of steps preceeding the conclusion,
then the result would not be measurable since an infinite number of steps
naturally takes an infinite time.

>Question #1: What is it about the discreteness of physical reality and the
>physicality of objects that requires that each program contain "only a
>finite number of symbols" and that "one could not manufacture an infinite number of them"?

The answer here would appear to be similar, although I wouldn't blame it on
the "discreteness of physical reality" -- it would take infinite time to
write a program containing infinitely many symbols.

Only the Omega point subjectively infinite time theory could ever supply
sufficient time -- and even then the conclusion would never be reached,
because the time would be *infinite* and therefore the lifeforms experiencing
this would never be aware of reaching the end.

Rachel Dugdale.
Mail to: Rachel_Dugdale@hotmail.com or REDugdale@aol.com
Physics and related issues discussion list: to subscribe email:
with the message SUBSCRIBE

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