Re: Revised Computing Randomness & the UD

From: Marchal <marchal.domain.name.hidden>
Date: Sat Apr 21 08:30:49 2001

Hal Ruhl wrote:

>1) The UD proof of the object "all theorems" is complex because each step
>is a unique slice of progress towards some sub component of the target
>object thus all steps are different and there are a great many of them.
>
>2) The UD knows its proof is complex and since it is the only way it has to
>the target object it knows it is elegant.


>The UD [a simple FAS] - uses an incredibly complex proof [known by the UD
>it to be elegant and incredibly complex] - to exhibit "all theorems" [an
>object of extremely low complexity].

You confuse computability and provability. The UD does not generates
formal
proof in a formal system, it executes all possible computations.

There is a sort of absolute sense (with Church's thesis) in saying that
the
UD generates all the proof of \Sigma_1 sentences, though. A sentence which
is provably equivalent to ExP(x) (It exist a x such that P(x) with P
recursive).

And there are surely a lot of other senses, but then you need to define
the one you are using.

How do you define "knowing"? In what sense does the UD know something?

It can be shown that the set of *all theorems* of a reasonable first
order
arithmetic theory is not so low; with reasonable logical complexity
definition.

Bruno
Received on Sat Apr 21 2001 - 08:30:49 PDT