Re: ESSAY: Program length, Omega and Friendliness

From: Philip Goetz (
Date: Sat Feb 25 2006 - 08:58:07 MST

On 2/25/06, Philip Goetz <> wrote:
> How does this bounding follow from anything you said before?
> Especially since you've never referred to a "starting program".
> I don't know what that phrase is supposed to refer to.
> My best guess is that your "starting program"
> is a program to generate Phi, and that you are wrongly
> assuming that a program cannot generate a stream
> of bits longer than itself.


I had accidentally clipped off the first sentence of your post,
which explained that.

Now that I understand that, I'll try to re-interpret what you said.


>So the maximum number of bits of Phi and hence number of known
>or provably friendly programs is bounded by the length of your
>starting program. It would be less than that because you would
>have to take into consideration the bit requirement of the
>machinery to transform your bit of Phi into a program
>and other things you want your program
>to do. But tightening the bound is not of much interest
>I don't think.

You seem to be constructing a Phi that is specific to a specific
starting program. However, I know for a fact that for any program,
halting or not, there are an infinite number of programs equivalent to
it. Just think about it. So this can't be right. Also, I still
don't see how it logically follows. I totally fail to see the
intended point of connection. There doesn't seem to be anything
relating the length of phi to the length of the starting program.

- Phil

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