Re: Computational irreducibility and the simulability of worlds

From: Bruno Marchal <>
Date: Sat, 10 Apr 2004 18:12:07 +0200

At 00:35 10/04/04 -0400, Stephen Paul King wrote:

> > BM: I agree with this. There is no embedding of QM in a Boolean
> > if by embedding we mean a injective function which preserves the value of
> > the observable. But ...
> Ok. Well please help me how does my argument not follow? I am trying to
>understand how my claim fails. You seem to understand this, I need to
>understand this, help me please.

BM: My feeling is that we just have different fundamental hypotheses. More
in the sequel.

> > >it follows
> > >that it is impossible to fully simulate a QM system on a classical
> > >unless we allow for some rather exotic special conditions.
> >
> > I disagree. Unless "fully" means "in real time" ? Not only a classical
> > computer can compute all "quantum computable functions", but if you
> > allow the classical computer to simulates the system consisting of
> > "you + a quantum computer", then the classical computer will, relatively
> > to you, be able to simulate all quantum processes (and not only the
> I have one situation in mind where your conclusion follows but it seems
>to be a Very Special case, the case where we have infinite resourses
>available for the classical systems to simulate the QM systems, all of the

Giving that I *assume* that arithmetical truth is independent
of me, you and the whole physical reality (if that exists), "I" do have
infinite resources in that Platonia. Remember that from the first person
point of view it does not matter where and how, in Platonia, my
computational states are represented. Brett Hall just states that
the proposition "we are living in a massive computer" is undecidable
(and he adds wrongly (I think) that it makes it uninteresting), but
actually with my hypotheses physics is a sum of all those
undecidable propositions ...(Look again my UDA proof if you are not
yet convinced, but keep in mind that I assume the whole
(un-axiomatizable by Godel) arithmetical truth, which I think you

> I agree with most of your premises and conclusions but I do not
>understand how it is that we can coherently get to the case where a
>classical computer can generate the simulation of a finite world that
>implies QM aspects (or an ensemble of such), for more than one observer
>including you and I, without at least accouting for the appearence of

A non genuine answer would be the following: because the solutions
of Schroedinger equations (or Dirac's one, ...) are Turing-emulable.
This does not help because a priori we must take into account all
computation (once we accept we are turing-emulable), not only
the quantum one (cf UDA). A priori
comp entails piece of non-computable "stuff" in the neighborhood,
but no more than what can be produced by an (abstract) computer
duplicating or differentiating all computational histories.
Remember that if we are machine then we should expect our
"physical reality" NOT to be a machine. Indeed at first sight we
should expect all "nearly-inconsistent" histories (white rabbits).
But the godelian constraints add enough informations for defining a
notion of normality, that is a beginning of an explanation of why coherent
and sharable realities evolves from the point of view of the observers
embedded in Platonia.
Most of Alan and David critics of comp works fine for Schmidhuber
form of comp (where physics comes from a special program) or
Tegmark where physical reality is a mathematical structure among
all mathematical structures. I provide arguments showing that if we belong
to a mathematical computation then our future/past (that is our physics)
depends on an infinity of (relative) computations (all those going
through our relative states).

> How is it that we necessarily experience an asymmetrical flow of time
>given the assumption that all 1st person experiences are assumed to be
>merely algorithms that exist a priori in Platonia?

Your phrasing is a little bit misleading here I'm afraid. The first person
experiences are knowledge states. If you agree with the usual axioms
for knowledge (that is : I know A implies A, I know A implies that I know
that I know A, I know (A -> B) entails that if I know A then I know B,
plus the traditional modal inference rules, then with comp that
knowledge states are completely captured by the S4Grz modal logic
which has nice semantics in term of antisymmetrical knowledge states
evolution. What is absolutely nice is that from the machine point of view
that knowledge cannot ever be defined. Only meta-reasoning based
on comp makes it possible to handle it.
You can read the appendice (in english!) in "Conscience et Mecanisme"
by the Russian logician Sergei Artemov which provides an argument
for identifying the notion of informal (and even un-formalizable) provability
by the conjonction of formal provability and truth. By Godel, that *is*
different from just formal provability:'Artemov.pdf
Note that this idea has been explicitly proposed by Plato in his
Thaetetus (just replace "formal proof" by "justification" or "definition"
(The historian of greek philosophy disagree on the meaning of the
word we should use, but here I interpret it as "rigorous third person
justification" or formalizable proof).

>How is the issue of the
>NP-Completeness problem of the computation of our experience a world where
>we interact successively with each other solved by the mere existence of a
>solution to that problem?
> How does the a priori possibility of a solution imply that the solution
>needs not be searched for and found?

Because the physical appearances comes from a sum on *all* solutions
existing in Platonia (a modal "inside" view of that sum, to be sure).
You didn't have to prove the existence of "Stephen Paul King" to be born,
isn't it?

Received on Sat Apr 10 2004 - 12:12:05 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:09 PST