Re: Computing Randomness

From: <hal.domain.name.hidden>
Date: Thu, 12 Apr 2001 23:56:32 -0700

Hal writes:
> You are writing programs and they have a complexity. Chaitin limits this
> complexity to no more than the complexity of the FAS plus a constant. Thus
> there can not be an infinite number of such constructions.

This is not quite right. Chatin limits how much complexity these programs
can be *proven* to have using the FAS. The FAS is unable to show that
an object has more complexity than what is in the FAS itself (plus a
constant). That doesn't mean that the objects are limited in complexity,
but rather that the FAS is limited in how much complexity it can prove.

Hal (the other Hal)
Received on Fri Apr 13 2001 - 00:10:33 PDT