From: Philip Goetz (philgoetz@gmail.com)
Date: Sat Feb 25 2006 - 07:42:35 MST
On 2/21/06, William Pearson <wil.pearson@gmail.com> wrote:
> Cribbing from Chaitin mercilessly....
>
> The number of friendliness preserving programs a program can safely
> self transform itself into is bounded by the length of the program.
>
> Let us posit a number Phi which is equivalent to Omega but for
> friendliness. That is 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. And omega is bit
> 1 is 1 iff program 1 halts (I don't know whether this is the classical
> definition)
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.
> Knowing a bit of Phi is 1 is equivalent to knowing a bit of Omega is
> 1, unless not halting is friendly :)
We are leaving halting out of it, I think. Actually, halting would be
friendly, or at least neutral - a program that had halted couldn't goo
you. Anyway, the point is, Phi is about friendliness, not halting;
don't confuse the two.
> The easiest way to know whether n programs halt (without empirically
> checking them) is to have them encoded in an n bit number.
???
You are saying that you arbitrarily assign one bit per program. This
will not tell you whether they halt, unless an oracle magically
provides the proper bit in each case. I think you mean something
other than "the easist way to know (learn)"; possibly, "the easiest
way to denote".
> Each bit
> representing one bit of omega, so similarly for Phi.
Can't parse this.
> Quite often this
> is expressed as knowing the first n bits of omega, but as we are not
> interested in the ordering of Phi we shall treat them as arbitrary
> bits of Phi and hence arbitrary length* programs.
I can't resolve your anaphors in general. "Them" here appears to mean
bits of Phi, but then you are saying we shall treat bits of Phi as
bits of Phi. I can't parse a lot of this post.
In any case, there is no 1-1 correspondence between bits of Phi, and
programs. The cardinality of the set of bits of Phi is aleph-null;
the cardinality of the number of programs is 2^(aleph-null). Well,
technically you could construct a 1-1- correspondence, if you take the
continuum hypothesis as false, but there's no obvious way to take a
bit of Phi and find the program for it, or vice-versa.
> So the maximum number of bits of Phi and hence number of known or
> provably friendly programs is bounded by the length of your starting
> program.
How does this bounding follow from anything you said before?
Especially since you've never referred to a "starting program".
I don't know what that phrase is supposed to refer to.
My best guess is that your "starting program"
is a program to generate Phi, and that you are wrongly
assuming that a program cannot generate a stream
of bits longer than itself.
> It would be less than that because you would have to take
> into consideration the bit requirement of the machinery to transform
> your bit of Phi into a program and other things you want your program
> to do. But tightening the bound is not of much interest I don't think.
>
> Anything wrong with this semi-formal proof?
Two key problems:
1. Each bit in Phi does not correspond to a program. If you want
each bit to correspond to a program, you have to construct Phi in a
different manner. If you want Phi to be a number (a sequence of
bits), then you must be aware that claiming that you can make each bit
in a sequence of bits correspond to one of the set of possible
programs, is claiming that the continuum hypothesis is false.
2. This last bit about the maximum number of bits being bounded by
your starting program. That doesn't seem to connect to anything else
in the proof.
- Phil
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:56 MDT