Re: Universal prior - Go FORTH and Run Backward

From: Marchal <marchal.domain.name.hidden>
Date: Sat Nov 13 10:46:27 1999

Chris Maloney wrote:

>Marchal wrote:
>>
>> This is linked to something said by Russell Standish in his paper
>> and in some posts. Russell Standish pretends that (I quote him):
>>
>> Each self-consistent mathematical structure is completely described
>> by a finite set of symbols, axioms and rule.
>>
>> This is totaly incorrect, I'm afraid. It is known that you cannot
>> find a recursively enumerable (RE) set of axioms to specify the
>> (N,+,x) structure (N) of the natural numbers with addition and
>> multiplication. Each RE description of N admit plenty of non
>> isomorphic models which belongs to any reasonable set of
>> mathematical structures.
>
>I don't understand this. Do you have a reference? I thought that
>such a system as N with operations of addition and multiplication
>are easily definable as a formal system. I must be missing what
>you mean by "structure".

It is a consequence of either Lowenheim Skolem theorem or Godel'theor.
You can build easily a formal system sound for the standart structure
of the natural numbers, but you cannot build a *complete* theory
univoquely describing that structure. A good reference is Boolos and
Jeffrey. (Or Davis 65 for the original paper).

>If this hadn't been a reference to Goedel, I'd have been tempted
>to dismiss it. As it is, I'm merely quite skeptical. It seems
>to me that computability is just a mathematical formalism like
>any other, where you define symbols, axioms, and rules. Whenever
>I hear anyone say that mathematical truths are "relative", my
>guard goes up. It's one of the things I didn't like about David
>Deutsch's book.

For theories and formal system with a notion of truth you have a
great numbers of non equivalent logics and theories. Even if you
confine yourself to classical first order logical theories, you
enter in a real big zoo ...
ALL attempts to define the notion of computability has
lead to the same class of functions. Even formalism as different as
the game of life, Fortran, prolog, the unitary quantum transformation
describe alaways the same set of function !
And recursion theory gives deep results which does not depend of the
formalism choosed. In fact definability and provability is completely
dependent of the formalism, but with computability, either your
formalism is to poor and you miss the universal class, or your formalism
give you the universal class and you can augment it as you want, you
get always the same class. With provability you can extend any formalism
to give you more powerfull systems.
I don't agree with David Deutsch when he relativize computability,
but beyond that I agree on a lot of points.

>IMO, mathematical truths are fundamentally tautologies. They are
>equivalent to "If A then A". I am not one to question formal
>propositional calculus (the rules for making sylogisms) and
>therefore I adhere to the belief that mathematical truths are
>absolute, because they are tautologies. I.e. any correct proof
>of a theorem T based on axioms A, B, and C could be stated
>simply, "If A, B, and C, then T".
>
>So I certainly don't see that computability theory could be in
>any way more fundamental.

Because of the miracle of Church's thesis being apparently true.
More on that point later. A good book on Church's thesis
is Judson Webb (ref in my thesis).

>> That is why Tegmark or GSlevy approach, although very interesting,
>> is still ill-defined. Tegmark will need some powerfull constructive
>> axiom to give a sufficiently precise sense to the "whole set
>> of mathematical structures" so that he can make the white
>> rabbit disappearing, by isolating the right prior.
>
>His axiom was explicit: there is one of each structure, up to
>isomorphism. Making anything useful out of that might be difficult.

The problem here is that if you succeed in making precise a set
of structures + the notion of morphisme, you will work in a
mathematical structure itself isolated from a vast collection
of other mathematical structures.

>I was thinking that Hal and
>others weren't giving enough consideration to the explanatory power
>of the principle of computational indeterminacy.
>
>But I've since changed my mind. I am now completely stumped to the
>core.

In what way ? With the UD the problem is not yet solved, but at least
it is clearly formulable, and you don't have the "whole-of-math"
definition problem. I guess this come from your lack of appreciation
of Church'thesis and of the universality of the computability concept.

>For one thing, I reject Juergen's principle because it is ad hoc.
>I insist that any measure must result from zero information -- that
>is the whole appeal of the AUH, after all.

When you say "I insist that any measure must result from zero
information" I would be glad if you make this more precise. Note that
I agree with you here, although I would replace zero by ... eh...
a little more (no time for details, but I explain elsewhere that
with the null theory you will stumb again upon the problematical
 "whole-math".

>I also reject James Higgo's contention that the WAP can explain it
>all. After all, I can think of plenty of scenarios where I survive
>but the universe nevertheless acts chaotically.

I share Higgo's attraction for the WAP, if computational indeterminacy
(and also non-locality!) is taken into consideration. In that
case it can explain it all or it can refute comp. But you point on
the real problem which is that chaotic flying white rabbit are consistent.

>Tegmark says "one of each structure up to isomorphism". But now I
>keep thinking that that won't do at all, either. As the newcomer
>Fritz just recently said:
>
> Considering that every possible state does exist in some world,
> it seems safe for me to conclude that there is only one world
> corresponding to every state, and the chance of finding
> ourselves in any possible universe is just as likely as any
> other. The result would be total chaos.
>
>If there's one of each, and each has an equal measure, then how come
>I don't find myself embroiled in a chaotic universe?


With the UD every possible state does appear in an infinity
of computational stories. The problem is to isolated the good
"relative measure". The method is listening to the self-applied
UTM. With comp, hunting the noise or the rabbit is equivalent
to deriving the laws of physics from the laws of computation.
I prefer to say the "laws of dream" to keep in mind that it is
really the "laws of computation" as seen by computational being.
This induces modal nuances.

>Same problem, as far as I can see, with any computational theory.
>Tegmark recently wrote that (paraphrasing) any Turing machine could
>be described as a function on the natural numbers, f(n). It's
>state at any time would be n. Then, it's state at the next time
>interval would be f(n), then f(f(n)), and so on. This is just a
>HLUT (Huge Look-Up Table). Now, if all Turing machines exist in
>equal measure, then it seems to me, once again, that we should
>expect chaos.

The measure must be defined on the computations, not on the
machines.

>> I have still a question for Russell, what is the meaning of
>> giving a "physical existence" to a mathematical structure ? This is
>> not at all a clear statement for me.
>
>I don't have a problem with this at all. Tegmark, again, was pretty
>clear: ME == PE (Mathematical Existence == Physical Existence).

With comp there is a sense to say physical and psychological
existence implies mathematical existence. But mathematics is too
much general for that. What would it means for the number
1 to exists physically ? Honestly that looks a little like
non sense. I can understand that the number 1 is incarnate or
implemented in a lot of (apparently) physical manners, but "1"
is a creation of (perhaps an atemporal and universal) mind.

Bruno
Received on Sat Nov 13 1999 - 10:46:27 PST