Re: ESSAY: Program length, Omega and Friendliness

From: William Pearson (
Date: Sun Feb 26 2006 - 18:06:48 MST

On 26/02/06, Nick Hay <> wrote:
> Philip Goetz wrote:
> >>bit 1 is 1 iff the shortest program expressible
> >>in a programming languages (breaking ties in a defined fashion)
> >>is friendly and has friendliness maintaining transformations.
> >>And so on with the second bit and the second shortest program.
> >
> > The "and so on with the second bit and the second shortest program"
> > indicates there is only 1 program of each length. I think he must
> > mean "smallest" (when the bitstring is interpreted as a number) rather
> > than "shortest". Although that introduces the possibility of having
> > to compare program "000101" to "101", so we must order first by
> > length, then numerically.
> It's not well-defined as it stands. Once you put an ordering on all possible
> programs (as you have, or the one I mention below), and swap "shortest" with
> "smallest", it is.

Yeah this is a slip on my part. Maths is still a second language to me
and I am very much an amateur in AIT, likely to be fast and loose with
my proofs.


This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:56 MDT