Re: ESSAY: Program length, Omega and Friendliness

From: Nick Hay (
Date: Sun Feb 26 2006 - 14:18:32 MST

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, but that's
talking about processes of infinite duration.

-- Nick Hay

> - Phil
> .

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