Re: an true information theory

From: Daryl McCullough (stevendaryl3016_at_yahoo.com)
Date: 03/03/05 

Date: 3 Mar 2005 07:03:13 -0800

Eray says:

>"Can the rule finding itself be done by some computer program?
>Interestingly, it is mathematically proven that there can be no
>computer program which can eventually find (synonym: learn) these
>(algorithmic) rules for all sequences which have such rules! "
>
>Here, the exclamation mark at the end of the first paragraph suggests
>that the answer is a NO.

He doesn't just *suggest* that the answer is no, he is stating
it. However, he is just saying that there is no such thing as
a *perfect* pattern recognizer program. That isn't saying anything
about the impossibility of AI, because humans aren't perfect
pattern recognizers, either.

>That the rule finding itself cannot be done by
>any program. However, he cannot come out and say it,
>because that would not sound "scientific".

What's unscientific about it? It's a provable fact about
algorithms: There is no algorithm P which can reliably
take the outputs of a second program Q and figure out
the code for Q from its outputs.

More precisely, let's have three notions of "figuring out
an algorithm":

    1. P can only make one "guess". Given an infinite sequence
    of outputs from Q, program P can in a finite amount of time
    halt and return the code for Q.

That's obviously impossible, because if P stops after seeing n
outputs, and figures out that the algorithm must be A1, there
is always the possibility that the real algorithm is A2, where
A2 produces identical outputs to A1 for the first n steps, and
different outputs thereafter.

    2. P can make as many guesses as it likes, but may only
    change its guess if the guess is proven wrong. (That is,
    at stage n, P makes a guess A for the algorithm. If at
    a later stage, program Q makes an output that is inconsistent
    with algorithm A, then P may change its guess).

It's a little harder to see, but if P follows such a rule, it
can't be guaranteed to eventually figure out the correct algorithm.
The reason for this is the unsolvability of the halting problem.
Suppose that P's current guess is algorithm A, and P sees outputs
o_0, o_1, o_2, ... o_n. P knows that algorithm A produces outputs
o_0, o_1, ... o_{n-1}, but P hasn't run A long enough to know whether
A's next output is o_n or not. Then how long does P wait to decide
whether output o_n is consistent with the algorithm being A? P
has no way of knowing whether A might eventually output o_n, so
he has no way of knowing whether A is consistent with output o_n.

A third notion of "correctly guessing the algorithm" is yet more
complicated:

   3. P can make as many guesses as it likes, and may change its
   guess at any time (and can change back to a previous guess, if
   it wants). We will say that P is "infinitely often" correct if
   there is an infinite number of stages n such that P's guess at
   stage n is correct and no other wrong guess appears infinitely
   often. That is, P makes an infinite sequence of
   guesses for the algorithm: A_1, A_2, ... where A_n and A_m may
   be equal, even when n is not equal to m. From this infinite
   sequence of algorithms, strike off every algorithm that appears
   only a finite number of times. If the resulting list has only
   one algorithm in it, and that algorithm is correct, then P
   has guessed correctly.

I think with this very weak sense of "guessing the algorithm" it is
possible for P to correctly guess every algorithm. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: an true information theory
    ... > outputs, and figures out that the algorithm must be A1, there ... > there is an infinite number of stages n such that P's guess at ... > sequence of algorithms, strike off every algorithm that appears ... I've read that quantum computing may improve tractability but ...
    (sci.math)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)
  • Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)
    ... I enjoyed thinking more about the consequences of Turing, ... A sequence is said to be computable if it can be computed by a circle-free ... circular if it performs an infinite computation outputting only finitely ... because it can be generated by a shorter algorithm. ...
    (comp.theory)
  • Re: Poetential infinity
    ... > represented more formally as discrete infinite sequences. ... If you search Google with terms "potentially infinite" turing machine tap ... for an algorithm has a finiteness requirement. ... "computational method" which abandons the finiteness requirement: ...
    (sci.logic)
  • "Algorithmic Randomness, Quantum Physics, and Incompleteness"
    ... all finite sequences are to be found infinitely often and ... different members of the infinite set of random numbers. ... Just using random numbers with initial digits 1 thru 9, ... it generated by a shorter input algorithm than the length ...
    (sci.logic)