Re: Is the universe computable

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Wed, 21 Jan 2004 15:21:24 +0100

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?
>
>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"):
>
>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.)




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




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



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?

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.

Bruno
Received on Wed Jan 21 2004 - 09:21:52 PST