From: Philip Goetz (philgoetz@gmail.com)
Date: Mon Feb 27 2006 - 06:25:33 MST
On 2/26/06, William Pearson <wil.pearson@gmail.com> wrote:
> > 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.
>
> By programs in the following I shall mean programs whose kolmogorov
> complexity is equal to there length. That a program can know that an
> infinite number of programs that all do the same thing have the same
> halting likelyhood or friendliness is not interesting.
If you limit yourself to programs whose K-complexity = their length,
then you have destroyed the point of the exercise. A program has 1
K-complexity, so I think you are saying that "The length of programs
of length n that programs of length n can be transformed into is
bounded by n".
> The thrust of the argument is this. Determining friendliness (or other
> desired property) of a program is as hard or harder as determining
> whether a program halts or an infinite looping program has finite
> output (whether it hangs or not). Friendlyness implies (in a logical
> sense) the program halts.
Determining friendiness may be as hard as determining whether a
program halts. I don't know. Why would friendliness imply that the
program halts? I don't see any connection.
> As all the bits of the Omega Series have no relation to each other,
> they are random so the shortest way of storing them is the direct
> information. And so because it is as hard or harder to prove
> friendliness Phi must be equally random.
>
> A proof system and axioms is a way of storing information about the
> world, we shall call a starting program with embedded proof system and
> axioms S.
>
> How many other programs can S prove the friendliness of?
>
> I have said the bound on the number of programs a proof system can
> have knowledge that they are friendly is the number of bits in it.
> Otherwise it has found some hidden relation between the bits of the
> Phi so that it can be compressed.
Well, you're assuming, in advance, that there is no such thing as a
proof system, but that instead, all the bits of Phi must be
enumerated. A proof system is generative, and a proof system of
finite size can prove, for example, that an infinite number of numbers
are either prime or not prime.
If you assume that there is no way to prove that a program is
friendly, even then, it doesn't follow that you have to list one bit
per program you know, because you may have heuristics that allow you
to produce a prior probability for each program under consideration.
- Phil
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:56 MDT