From: William Pearson (wil.pearson@gmail.com)
Date: Mon Feb 27 2006 - 07:48:21 MST
On 27/02/06, Philip Goetz <philgoetz@gmail.com> wrote:
> 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".
No I am not trying to say anything like that
You miss out things like provably maintaining a certain programmatic
property such as friendliness. I also haven't bounded the length of
the programs to be transformed into, although a bound is possible.
> > 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.
No? If a program doesn't halt it doesn't output (in the classical
formulation of halting). If it doesn't output it doesn't do anything.
Most definitions of friendliness definitely imply that programs are
supposed to do something. This may be non-obvious, because as Richard
Loosemore we tend to think of AI programs as being infinite
outputting, so it might be clearer if I talked about whether a program
hangs or not rather than halts. However this discussion with you is
consuming the time that I can devote to that endeavour.
I treat the halting problem as described in the final paragraph here.
http://www.cgl.uwaterloo.ca/~csk/halt/
Quote
[...] the halting problem is undecidable.
In some sense, this problem (or some related formulation) is the
canonical undecidable problem. There are countless other undecidable
problems, which can often be expressed in terms of some simple
question about a computer program. For example:
* Will the program ever print out a 5?
* Will the program ever execute line 26?
It turns out that these sorts of problems are all equivalent to the
halting problem, in the sense that given a solution to one of them,
you could write a solution to any of the other ones. The reasons why
that is possible are interesting, but beyond the scope of the last
sentence of this document.
Endquote
I just substitute friendliness. Or strongly self-improving or other
property we want the program to maintain as it replaces itself with
new programs. I believe Rice's Theorem deals with the last sentence.
http://en.wikipedia.org/wiki/Rice%27s_theorem
> > 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.
This has no bearing on determining properties of strings that are
interpreted as programs. Primeness of a finite string can be
determined in finite time by a finite algorithm. Halting, and I argue
friendliness, cannot be. I would advise you to read some Chaitin if
you haven't.
> 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.
This was distinctly beyond the scope of what I was arguing. It is fine
method if you accept that this has an arbitrary chance of having your
program hang or never halt as it replaces itself with new ones. To
give you a brief argument, if it can be shown that your heuristic
correctly assigns over 50% chance of halting to those programs that
halt and under 50% for those that don't halt for more programs than
its length, then it would lead to violation of the limits of knowing
Omega. If we can't or don't show this link then the correspondence of
the heuristic with reality is arbitrary.
Will Pearson
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:56 MDT