# Re: Computing Randomness

From: Russell Standish <R.Standish.domain.name.hidden>
Date: Tue, 17 Apr 2001 12:12:00 +1000 (EST)

Hal Ruhl wrote:
>
> Dear Russell:
>
> At 4/13/01, you wrote:
> >Private post per Jacques suggestion:
>
> I tried to initiate a side bar a few months ago and was convinced by the
> other party that it was not the best idea. However, if you want we can
> have such an exchange.
>
> I just posted to the list a response to Hal Finney which may clarify my view.
>
OK - reinitiating this as a public discussion

> >Hal Ruhl wrote:
> > >
> > > Dear Russell:
> > >
> > > You wrote:
> > >
> > > >Why bound the proof?
> > >
> > > It was not my idea. Chaitin equated complexity with a computing program's
> > > length and a proof chain is a computing program according to Turing.
> > >
> >
> >Sure - however the length of a proof corresponds to logical depth, not
> >K-complexity. You must careful not to conflate the two very different
> >concepts.
>
> I believe the issue revolves around the length of the "elegant" proof which
> as I understand it is the correct complexity to discuss.
>

I wonder why?

> > > [rearranging your post]
> > >
> > > >1+1=2, 2+1=3, 3+1=4 ...
> > > >
> > > >are all distinct theorems.
> > >
> > > My view:
> > >
> > > Again as in my response to Juergen these are not theorems but proof chains
> > > leading to theorems.
> > >
> >
> >Most people would call these theorems.
>
> As I understand it theorems are strings of alphabet elements say in binary:
>
> 10011100110001 or 101010101001
>
> There are no operators in the string. The operators are in the proof.
>

OK - so my theorems above are coded in ASCII to make them more human
readable. Choice of alphabet makes no difference.

>
> >At last count, there were \aleph_0 of them. Why do you say finite,
> >when its obvious to blind freddy there's an infinite number.
>
> Objects that have elegant programs too program length complex for a FAS to
> prove to be elegant are not fully describable by the FAS. Any finite FAS
> can only prove a finite number of programs to be elegant. Thus a finite
> FAS can fully describe only a finite number of objects.
>

I can see that, but I fail to see why one would want to do this. I
promise I'll get around to reading Chaitin's books in the next year or
two.

> >Perhaps you say that tautologies will equivalence these theorems to a
> >finite collection - but in that case you end up with a collection of
> >axioms, not theorems.
>
> At the moment I suspect that "collection of axioms" is close to the right
> idea. Take the logistics equation and iterate it on a chaotic
> trajectory. You start with an axiom - data injected as true without
> proof. Now let a finite computer determine the next point on the
> trajectory. The computer truncates the calculation to fit its precision -
> it hands you a new axiom surely not "proven" by the equation itself. Add
> to this growing set of axioms the equation itself [the rule] plus the
> finite environment and it is a little like how
> IMO universes evolve in finite FAS except that the FAS is pushed to higher
> complexity by the "evolving".
>
> Hal
>

This is obviously an analogy, which I'm not sure where that gets
you. You can also perform the logistic calculation using arbitrary
precision arithmetic, in which case no loss of precision occurs. The
difference, of course is that you end up with exponential slow-down of
the arbitrary precision calculation with respect to the finite
precision calculation. Perhaps you can make a link here to Juergen's
algorithmic TOE stuff, where the algorithmic performance of the
generating algorithm matters.

----------------------------------------------------------------------------
Dr. Russell Standish Director
High Performance Computing Support Unit, Phone 9385 6967
UNSW SYDNEY 2052 Fax 9385 6965
Australia R.Standish.domain.name.hidden
Room 2075, Red Centre http://parallel.hpc.unsw.edu.au/rks
----------------------------------------------------------------------------
Received on Mon Apr 16 2001 - 19:43:35 PDT

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