From: Philip Goetz (philgoetz@gmail.com)
Date: Sun Feb 26 2006 - 09:14:01 MST
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
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:56 MDT