# 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?
```

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

```

```