From: Nick Hay (nickjhay@hotmail.com)
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 http://www.cs.auckland.ac.nz/~nickjhay/2006.dagstuhl.pdf), 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