Re: Revised Computing Randomness & the UD

From: Marchal <marchal.domain.name.hidden>
Date: Sat Apr 21 10:32:58 2001

Hi Hal,

>These are some of the things I want to explore as a result of formulating
>my question re the UD.
>
>To start:
>
>1) Are you saying that the UD contains all other computations as data?

No. The UD is a program without data. It generates and executes all
computations. It "dovetails", i.e. it executes all programs by little
pieces, so it does not stuck itself in a non stopping computation.


>... But for sake of covering all bases I thought
> "compute" = "prove" was established by Turing.

The work of Post, Church, and Turing (and others) shows the contrary. It
shows the abyssal difference between provability and computability.
Godel realises that his own incompleteness protect Church thesis and
gives to the notion of computability a miraculous absolute nature.
At the same time it shows that provability is always relative to a
choosen formal system. That is what makes the Universal Dovetailer
really universal. It computes everything computable, but is does not
makes proof. If you look at it as a theorem prover, most formal
description of the UD will give a not really powerful theory.

>3) If in order to work the UD contains all other computations
>as data then the UD is a highly complex program. ...

I wrote one in LISP. It makes more or less 100 lines. You can write
very little one in PROLOG. It is not a highly complex program.
But, please, the computations are not the data, they are the output.

>Random strings are complex and I thought "all Theorems" was a very low
>complexity object. Or is it random?

It depends how you code it. "All theorems" is an ambiguous expression.
Never use the word "theorem" without mentionning the theory.
"All computations" is not ambiguous (it does not depend on the formal
system in use). In some sense Chaintin OMEGA number codes all
computations in a terrible compressed way. It is "random". But then
there exists nice natural way to encode all computation in a non
random, but deep (in Bennett sense) manner.

>4) Why not run a highly parallel computer rather than a UD? [That is rather
>like a part of my model.]

First, the meaning of quasi-geometrical word like "parallel" are
among the things I want explain. I cannot take such meaning for granted.
Actually, with some terrestrial sense for parallel, it will not
change a thing in the limit (see the UDA argument which explain why).

Also, The UD has a property I never mentionned, it generates by itself
an infinity of variant of itself which on almost all inputs (almost all
= all with a finite number of exceptions) is "quasi-infinitely" more
quick. The UD is self-speedable. But that is not interesting, for the UD
does not need to go quickly. Conscience and matter are inside view
of UD*, the complete (infinite) work of the UD; belonging to Plato's
heavens.

>5) My meaning for "knowing" is at first order like proving. Chaitin is
>actually talking about the complexity of the FAS's theorem checker as the
>complexity of the FAS. The theorem checker "knows" all theorems of the
>FAS. If a proof is an elegant proof by default then the theorem checker
>also knows this proof or it would not know how to check the output for
>theorem hood. It can prove this proof is elegant because there is no other
>choice.

OK. But be careful. In my work knowing is quite different of proving.
The modalities are not the same. This will be discussed in my explanation
to George Levy. In fact I will define at some point "knowing p" by
proving p and p is true. knowing and proving will appear equivalent only
for the guardian angel, but the consistent machine cannot know that,
nor prove it!

Bruno
Received on Sat Apr 21 2001 - 10:32:58 PDT