**From:** Nick Hay (*nickjhay@hotmail.com*)

**Date:** Sun Feb 26 2006 - 14:18:32 MST

**Next message:**William Pearson: "Re: Self improvement in the human brain was Re: DNA as a measure of brain complexity"**Previous message:**BillK: "Re: Self improvement in the human brain was Re: DNA as a measure of brain complexity"**In reply to:**Philip Goetz: "Re: ESSAY: Program length, Omega and Friendliness"**Next in thread:**William Pearson: "Re: ESSAY: Program length, Omega and Friendliness"**Reply:**William Pearson: "Re: ESSAY: Program length, Omega and Friendliness"**Reply:**Philip Goetz: "Re: ESSAY: Program length, Omega and Friendliness"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Philip Goetz wrote:

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

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.

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

I mean the infinite set of all finite binary strings here ( {0,1}^* using the

Kleene star operator). There's a simple bijection between the positive integers

and all finite binary strings: take the binary enoding of the integer, and

remove the initial 1:

1 1 empty string

2 10 0

3 11 1

4 100 00

5 101 01

. ... ..

Hence, the set of all finite strings is countable (aleph-null). Similar tricks

can be used for any alphabet.

When would you ever use a program of infinite length? I've had reason to think

about them in my work (i.e. with monotone Turing machines, or the model used

here http://www.cs.auckland.ac.nz/~nickjhay/2006.dagstuhl.pdf), but that's

talking about processes of infinite duration.

-- Nick Hay

*>
*

*> - Phil
*

*>
*

*> .
*

*>
*

**Next message:**William Pearson: "Re: Self improvement in the human brain was Re: DNA as a measure of brain complexity"**Previous message:**BillK: "Re: Self improvement in the human brain was Re: DNA as a measure of brain complexity"**In reply to:**Philip Goetz: "Re: ESSAY: Program length, Omega and Friendliness"**Next in thread:**William Pearson: "Re: ESSAY: Program length, Omega and Friendliness"**Reply:**William Pearson: "Re: ESSAY: Program length, Omega and Friendliness"**Reply:**Philip Goetz: "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
*