Re: ESSAY: Program length, Omega and Friendliness

From: William Pearson (
Date: Sun Feb 26 2006 - 09:52:14 MST

 I shall address these (and other peoples comments) more fully once I
have had a chance to get to the library to read Omega. This is a stop
gap solution.

> 1. Each bit in Phi does not correspond to a program. If you want
> each bit to correspond to a program, you have to construct Phi in a
> different manner. If you want Phi to be a number (a sequence of
> bits), then you must be aware that claiming that you can make each bit
> in a sequence of bits correspond to one of the set of possible
> programs, is claiming that the continuum hypothesis is false.

I think the confusion comes in (and it is my fault) is because when
people talk about knowing a bit of Omega, they mean knowing one of the
outcomes of the infinite sum. I got a little confused. Thanks for
catching me on this. However it doesn't change the argument much. When
I talk about knowing a bit I shall mean knowing a bit of the omega
series rather than knowing a bit of the omega number

> 2. This last bit about the maximum number of bits being bounded by
> your starting program. That doesn't seem to connect to anything else
> in the proof.

By programs in the following I shall mean programs whose kolmogorov
complexity is equal to there length. That a program can know that an
infinite number of programs that all do the same thing have the same
halting likelyhood or friendliness is not interesting.

The thrust of the argument is this. Determining friendliness (or other
desired property) of a program is as hard or harder as determining
whether a program halts or an infinite looping program has finite
output (whether it hangs or not). Friendlyness implies (in a logical
sense) the program halts.

As all the bits of the Omega Series have no relation to each other,
they are random so the shortest way of storing them is the direct
information. And so because it is as hard or harder to prove
friendliness Phi must be equally random.

A proof system and axioms is a way of storing information about the
world, we shall call a starting program with embedded proof system and
axioms S.

How many other programs can S prove the friendliness of?

I have said the bound on the number of programs a proof system can
have knowledge that they are friendly is the number of bits in it.
Otherwise it has found some hidden relation between the bits of the
Phi so that it can be compressed.

I would like to make this more concrete and also try and talk about
proof systems that take in bits from the environment so you will have
to be patient.

  Will Pearson

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