**From:** Philip Goetz (*philgoetz@gmail.com*)

**Date:** Sun Feb 26 2006 - 09:14:01 MST

**Next message:**Philip Goetz: "Re: How do you know when to stop? (was Re: Why playing it safe is dangerous)"**Previous message:**Ben Goertzel: "Re: How do you know when to stop? (was Re: Why playing it safe is dangerous)"**In reply to:**Nick Hay: "Re: ESSAY: Program length, Omega and Friendliness"**Next in thread:**Nick Hay: "Re: ESSAY: Program length, Omega and Friendliness"**Reply:**Nick Hay: "Re: ESSAY: Program length, Omega and Friendliness"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

On 2/25/06, Nick Hay <nickjhay@hotmail.com> wrote:

*> Philip Goetz wrote:
*

*> > Omega is the sum, over all programs that halt, of 1/(length of program
*

*> > in bits), when programs are expressed in a way so that no program is a
*

*> > prefix of another program (necessary so that the sum of the lengths of
*

*> > all programs would be 1). What you've defined works only if, for
*

*> > every n, there is exactly 1 program of length n. Fortunately there
*

*> > are more than that.
*

*>
*

*> I think you mean the sum over 1/2^{length of the program in bits} for all
*

*> halting programs, here.
*

Right.

*> The modified definition of omega, with each bit describing whether a program
*

*> halts, is actually also used (well, I've done exercises about it anyway!).
*

*> Although one can compute each bit sequence from the other, modified omega
*

*> requires a lot less computation time to deal with than omega itself.
*

Hmm - I wonder if the requirement that programs be specified in a way

so that no program is the prefix of another program, means that there

are less than 2^(aleph-null) of them. That would be necessary for

such an omega even to exist, if you don't take a stance on the

continuum hypothesis, which states that 2^(aleph-null) > aleph-null

(the number of bits in omega).

Yes, I think that is the case. If, for instance, you define your

language so that a 1 bit means "keep on adding more bits" and a 0 bit

means "end of program", the cardinality of programs is aleph-null. My

intuition says you could show that any change in the rules that

preserved the condition that no program was the prefix of another

program did not change the number of possible programs.

*> It's true that there's no 1-1 correspondence between bits of Omega and whether
*

*> individual programs halt in the standard omega. However, you can compute one
*

*> from the other (basic idea: from omega you can compute the number of n-bit
*

*> programs that must halt, say k, from this number you can compute the actual set
*

*> of halting programs by running all n-bit programs until k of them halt). There
*

*> is a correspondence between bits of Phi and programs by its definition.
*

I don't think its construction was really defined. To quote:

*> 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.

*> The cardinality of the set of programs (prefix-free or not) *is* aleph-null i.e.
*

*> the set of programs are countable. This is becase there are countably many
*

*> finite bitstrings. There are uncountably many infinite bitstrings, but we don't
*

*> use these as programs.
*

I was assuming the infinite case - out of habit, probably. I suppose

the finite case makes more sense, even though we don't know how large

our largest bitstring will be.

- Phil

**Next message:**Philip Goetz: "Re: How do you know when to stop? (was Re: Why playing it safe is dangerous)"**Previous message:**Ben Goertzel: "Re: How do you know when to stop? (was Re: Why playing it safe is dangerous)"**In reply to:**Nick Hay: "Re: ESSAY: Program length, Omega and Friendliness"**Next in thread:**Nick Hay: "Re: ESSAY: Program length, Omega and Friendliness"**Reply:**Nick Hay: "Re: ESSAY: Program length, Omega and Friendliness"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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