Re: Is the universe computable

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Fri, 23 Jan 2004 15:42:46 +0100

Dear Stephen,

At 12:39 21/01/04 -0500, Stephen Paul King wrote:
>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.



Good question. But you know I do address this question in my thesis
(see url below). I cannot give you too much technical details, but here is a
the main line. As you know, I showed that if we postulate the comp hyp
then time, space, energy and, in fact, all physicalities---including the
communicable (like 3-person results of experiments) as the uncommunicable
one (like qualie or results of 1-person experiment) appears as modalities
which are
variant of the Godelian self-referential provability predicates. As you know
Godel did succeed in defining "formal provability" in the language of a
consistent machine and many years later Solovay succeeds in formalising
all theorems of provability logic in a couple of modal logics G and G*.
G formalizes the provable (by the machine) statements about its own
provability ability; and G* extends G with all true statements about the
machine's ability (including those the machine cannot prove).
Now, independently, temporal logicians have defined some modal
systems capable of formalizing temporal statements. Also, Brouwer
developed a logic of the conscious subject, which has given rise to a whole
constructive philosophy of mathematics, which has been formalize
by a logic known as "intuitionist logic", and later, like the temporal logic,
the intuitionist logic has been captured formally by an modal
extension of a classical modal logic. Actually it is Godel who has seen
the first that Intuitionist logic can be formalised by the modal logic S4, and
Grzegorczyk makes it more precise with the extended system S4Grz.
And it happens that S4Grz is by itself a very nice logic of subjective,
irreversible (anti-symmetric) time, and this gives a nice account too of the
relationship Brouwer described between time and consciousness.
Now, if you remember, I use the thaetetus trick of defining
(machine) "knowledge of p" by "provability of p and p". Independently
Boolos, Goldblatt, but also Kusnetsov and Muravitski in Russia, showed
that the formalization of that form of knowledge (i.e. "provability of p
and p")
gives exactly the system of S4Grz. That's the way subjective time arises
in the discourse of the self-referentially correct machine.
Physical discourses come from the modal variant of provability given
by "provable p and consistent p" (where consistent p = not provable p):
this is justified by the thought experiment and this gives the arithmetical
quantum logics which capture the "probability one" for the probability
measure on the computational histories as seen by the average consistent
machine. Physical time is then captured by "provable p and consistant p and p".
Obviously people could think that for a consistent machine
the three modal variants, i.e:

     provable p
     provable p and p
     provable p and consistent p and p

are equivalent. Well, they are half right, in the sense that for G*, they
are indeed
equivalent (they all prove the same p), but G, that is the self-referential
machine
cannot prove those equivalences, and that's explain why, from the point of
view of the
machine, they give rise to so different logics. To translate the comp hyp
into the
language of the machine, it is necessary to restrict p to the \Sigma_1
arithmetical
sentences (that is those who are accessible by the Universal Dovetailer,
and that step
is needed to make the physicalness described by a quantum logic).
The constraints are provably (with the comp hyp) enough to defined all
the probabilities on the computational histories, and that is why, if ever
a quantum
computer would not appear in those logics, then (assuming QM is true!) comp
would definitely be refuted; and that is all my point.




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



This is related to the Skolem theorems or to the so-called "Skolem Paradox",
Cantorian cardinals are relative notions (in set theory). There is no sense
to talk about an absolute implementation of those cardinals. I do believe
in the Cantorian theory but high cardinal are measure on our high ignorance;
I don't see how we could extend a "set realism" for them, unlike what we can do
with numbers (but also with all ordinals less than the first non constructive
ordinal of Church and Kleene, by using an extended version of Church
thesis, the
so-called hyper-arithmetical Church thesis; but that step would be a step
toward a weakening of comp and the \Sigma_1 sentences should be replaced
by something else ...).

Hoping having not been too technical. A good book is Rogers' one, see the ref
in my thesis or papers, and of course a must is the Boolos 1993 book.
Even in my french thesis I have not give all technical details. I have done
that
in my "brussel's thesis" which I will soon put on my web page, but then it
is 800 pages of technical details ... in french (I did not choose it).

Remember that I am not a defender of comp. My only goal is to show that comp
is enough precise so that it can be refuted; or put in another way, my goal is
to show comp is a scientific theory in the popper sense of the word; a
little like
John Bell succeeded in showing that the Einstein Podolski Rosen paper
leads to verifiable propositions, and was not philosophy (as Bohr implicitly
argued, and as so many physicist did believe (without thinking on the matter).

Best Regards, and have a nice week-end,

Bruno
Received on Fri Jan 23 2004 - 09:42:48 PST