Re: Is the universe computable

From: Stephen Paul King <stephenk1.domain.name.hidden>
Date: Wed, 21 Jan 2004 12:39:29 -0500

Dear Bruno and Kory,

    Interleaving.

----- Original Message -----
From: "Bruno Marchal" <marchal.domain.name.hidden>
To: <everything-list.domain.name.hidden>
Sent: Wednesday, January 21, 2004 9:21 AM
Subject: Re: Is the universe computable


> At 02:50 21/01/04 -0500, Kory Heath wrote:
> >At 1/19/04, Stephen Paul King wrote:
> >> Were and when is the consideration of the "physical resources"
required
> >>for the computation going to obtain? Is my question equivalent to the
old
> >>"first cause" question?
> >[KH]
> >The view that Mathematical Existence == Physical Existence implies that
> >"physical resources" is a secondary concept, and that the ultimate ground
> >of any physical universe is Mathspace, which doesn't require resources of
> >any kind. Clearly, you don't think the idea that ME == PE makes sense.
> >That's understandable, but here's a brief sketch of why I think it makes
> >more sense than the alternative view (which I'll call
"Instantiationism"):
> >

[SPK]

    Again, the mere postulation of existence is insufficient: it does not
thing to inform us of how it is that it is even possible for us, as mere
finite humans, to have experiences that "change". We have to address why it
is that Time, even if it is ultimately an "illusion", and the distingtion
between past and future is so intimately intetwined in our world of
experience. How is it that we can think that it is reasonable to expect the
physically impossible to become possible by just postulating that it be so?

    "There ain't no such thing as a free lunch!" - Robert Heinleim


> >Here's my definition of "Computational Realism", which is sort of a
> >restricted version of Mathematical Realism. (I'm not sure if my
definition
> >is equivalent to what others call "Arithmetic Realism", so I'm using a
> >different term.)
>
> [BM]
> OK. Just to cut the hair a little bit: with Church thesis "computational
> realism" is equivalent to
> a restricted form of arithmetical realism. Comp. realism is equivalent to

> Arith. realism restricted
> to the Sigma_1 sentences, i.e. those sentence which are provably
equivalent
> (in Peano arithmetic, say) to sentences of the form "it exists x such that
> p(x)" with p(x) a decidable (recursive) predicate.
> This is equivalent to say that either a machine (on any argument) will
stop
> or will not stop, and this
> independently of any actual running. Indeed, sometimes I say that
> (Sigma_1) arithmetical realism
> is equivalent to the belief in the excluded middle principe (that is "A or
> not A) applied to
> (Sigma_1) arithmetical sentences. (Sigma_1 sentences plays a prominant
role
> in the derivation
> of the logic of the physical propositions from the logic of the
> self-referential propositions). Actually
> the Universal Dovetailing is arithmetically equivalent with an enumeration
> of all true Sigma_1 sentences. The key feature of those sentences is that
> their truth entails their provability (unlike
> arbitrary sentences which can be true and not provable (by Peano
> arithmetic, for exemple).
>
[SPK]

    Bruno, I do not understand why you use so weak a support for your very
clever theory! If we are to take the collection of a "true Sigma_1
sentenses" to have "independent of implementation" existence, why not all of
the endless hierarchy of Cantor's Cardinals? I have never understood this
Kroneckerian attitute.

> > [KH]
> >Let's say that you're about to physically implement some computation, and
> >lets say that there are only three possible things that this computation
> >can do: return 0, return 1, or never halt. Computational Realism is
simply
> >the belief that *there is a fact of the matter* about what this
> >computation will do when you implement it, and that this fact is true
> >*right now*, before you even begin the implementation. Furthermore, CR is
> >the belief that there is fact of the matter about what the result of the
> >computation *would be*, even if it's never actually implemented. CR
> >implies that there is such a fact of the matter about every conceivable
> >computation.

[SPK]

    That seems to me to be equivalent to postulating the existence of a List
of all possible algorithms and claiming that the postulation is sufficient
to prove that the output of an arbitrary computation *exists*. This reminds
me of the joke about Money growing on trees: We would still have to pay
people to do the "picking".

    My point is that while it ok to assume that "what the result of the
computation *would be*, even if it's never actually implemented" this is not
the same as eliminating the mere possibility of the implementation. This is
just the usual "contrafactual" - what "could of happended but did not" - and
illustrates some problems that can occur when such are considerred.

> > [KH]
> >It's from this perspective that I can begin to explain why I feel that
> >implementation is not a fundamental concept. In my view, implementing a
> >computation is a way of "viewing" a structure that already exists in
> >Mathspace (or Platonia, or whatever you want to call it). Implementation
> >is clearly something that occurs within computational structures - for
> >instance, we can imagine creatures in a cellular automata implementing
> >computations on their computers, and they will have all the same concerns
> >about "physical resources" that we do - computational complexity,
> >NP-complete problems, etc. However, the entire infinite structure of
their
> >CA world exists *right now*, in Mathspace. If we consider the rules to
> >their CA, and consider an initial state (even an infinite one - say, the
> >digits of pi), then there is *a fact of the matter* about what the state
> >of the infinite lattice would be in ten ticks of the clock - or ten
> >thousand, or ten million. And the key point is that the existence of
these
> >facts doesn't require "resources" - there's really no concept of
resources
> >at all at that level. Every single fact about every single possible
> >computation is simply a fact, right now. Every conceivable NP-complete
> >problem has an answer, and it doesn't require any "computational
> >resources" for these answers to exist. But of course, computational
> >creatures like us require computational resources to "view" these
answers.
> >Since our resources are severely limited, we don't have access to most of
> >the truths in Mathspace.

[SPK]

    Nope, that dog don't hunt! You are confussing the postential existence
of a computation with its "meaningfulness". But in the last time you are
getting close to my thesis. We should not take the a priori existence of,
for example, answers to NP-Complete problems to have more "ontological
weight" than those that enter into what it takes for "creatures like us" to
"view" the answers. This is more the realm of theology than mathematics. ;-)

> > [KH]
> >I don't think that this form of realism automatically leads to the
> >conclusion that ME == PE, but it certainly points in that direction. ME
==
> >PE becomes especially appealing when we consider the infinite regress
> >problem that the alternative position generates. You ask if your question
> >is equivalent to the old "first cause" question. I propose that it is
> >exactly equivalent, and brings with it all of the attendant paradoxes and
> >problems. If you believe that implementation is a fundamental concept -
if
> >you believe that, somehow, our universe must be "instantiated", or must
> >have some other special quality that gives it its true reality - then
> >you've got an infinite regress problem. Certainly, I can imagine that our
> >universe is instantiated in some larger computation, but then that
> >computation will have to be instantiated in something else to make *it*
> >real... and where does it all end? Or is it turtles all the way down? Or
> >does our universe simply have the elusive quality of "physical
existence",
> >while other mathematical structures lack it? In my opinion, the idea that
> >ME == PE points to a solution to these problems.

[SPK]

    No, I am not trying to argue that implementation is fundamental to the
exclusion of the existence of the mathematical structures. I am arguing that
the two have equal ontological status; one is just as *fundamental* as the
other. BTW, with the *discovery* of Non-Well founded set theory we have no
reason to fear Infinite regress when considering abstract structures. ;-)

[BM]
> I agree, although I would say that "physical existence" is only a
> particular case of mathematical
> existence, even a modal sort of existence. But that is another point, and
> actually I find your answer to Stephen quite clear and sufficient. Isn't
it
> Stephen?

[SPK]

    Clear, yes. Sufficient, no.

> About the question of applying "probability" to integers: there are more
> than one way to work
> that problem, and technically this could lead us far away, and I have not
> the time to really say more.
> Well I can give you a classical exercise in Number Theory: what is the
> probability that
> two integers are coprime (= their biggest common divisor is 1). Answer:
> 6/pi^2. Astonishing and
> counter-intuitive. The meaning is that if you build an urn with N balls on
> which you put the N first integers, then, as N is bigger and bigger, the
> "usual" probability of taking two coprime "balls" will converge toward
6/pi^2.
> What is the probability that k integers are coprime? Answer 1/zeta(k);
> where zeta is the famous Riemann Zeta function. The notion of Probability
> applied on infinite discrete sets or combinatorial structures often
> invokes Zeta or related functions. Generalisation of zeta function
(notably
> the multi-zeta functions) appears
> also in the renormalisation problem in quantum field theory, and I guess
> they will find application in the last definitive steps of our white
> rabbits elimination ..., i.e. in our search for the measure on
> computational histories.
>

[SPK]

    The appearence of zeta in the renormalization problem should not come as
a surprise! It is implicit in the mathematical tools that renormalization
uses. This is like the "White Rabbit" that the illusionist pulls out of his
tophat, to the pleasure and wonder of his audience, but such wonder rests on
the cleverness of the illusionist in hiding the Rabbit before the show.

Kindest regards,

Stephen
Received on Wed Jan 21 2004 - 12:55:27 PST