Re: an true information theory

From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 03/05/05 

Date: Sat, 05 Mar 2005 02:56:00 GMT

"Daryl McCullough" <stevendaryl3016@yahoo.com> wrote in message
news:d09rfl02ot1@drn.newsguy.com...
> Stephen Harris says...
>
>
>>I appreciate your comments, but I have to question them.
>>
>>> 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.
>
> Stephen,
>
> I was trying to sketch a more general notion of "computing an answer",
> but now that I think about it, I don't think it's a very interesting
> notion, so perhaps I should just drop it.
>
> The basic idea is that if the correct algorithm is A, then eventually
> the guessing program will guess A. However, there might be a time
>when a *different* algorithm A' appears to be a better choice than A.
>Then the guessing program may temporarily switch his answer to A'.
> But that's only temporary---eventually he will switch back to A. An
> >incorrect algorithm
> can appear to be better than the correct algorithm for a brief amount of
> time. That's because the correct algorithm might take longer to
>compute some output than the incorrect algorithm. For example, a
>program that correctly generates primes will take longer to run than the
> incorrect program that uses the algorithm: 2 is prime, and every odd
> number is prime, although the incorrect program generates the correct
>answer for 2, 3, 5, 7.
>
> --
> Daryl McCullough
> Ithaca, NY
>

I have been reading about "universal prediction" and "universal
sequential learning", which are closely connected to machine
learning and computational learning theory. So far your notion
is fairly reasonable incomparison to the literature. Perhaps my
idea of finiteness applies to only completely error free solutions.

http://www.ieeeits.org/review/meir/05meir.html
Reflections on ``Universal Prediction of Individual Sequences''

SH: I am still reading about this. But you mentioning primes jogged
my memory about twin Mersenne Primes. And I think the history
of trying to find a prime number formula for predicting primes
in the infinite counting numbers is a good way (IMO) to think
of Case's statement: "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!" So for instance I think the rule, if there is one,
for finding {*twin} Mersenne primes is an example, or could be,
of being unable to find the rule to such a sequence if it has one.

That is a big "if" and somewhat calls into question, 'what is a rule'.

http://www.utm.edu/research/primes/howmany.shtml
"The Prime Number Theorem: approximating pi(x)
Even though the distribution of primes seems random
(there are (probably) infinitely many twin primes and there are
(definitely) arbitrarily large gaps between primes), the function
pi(x) is surprisingly well behaved: In fact, it has been proved
(see the next section) that:

The Prime Number Theorem: The number of primes not exceeding x
is asymptotic to x/log x.
In terms of pi(x) we would write:
The Prime Number Theorem: pi(x) ~ x/log x.
This means (roughly) that x/log x is a good approximation for
pi(x)--but before we consider this and other consequences lets
be a little more specific:
"a(x) is asymptotic to b(x)" and "a(x) ~ b(x)" both mean that
the limit (as x approaches infinity) of the ratio a(x)/b(x) is 1.

If you have not had calculus then this means that you can make
a(x)/b(x) as close to 1 as you want by just requiring that x is
large enough. Warning: a(x) ~ b(x) does not mean that a(x)-b(x)
is small! For example, x2 is asymptotic to x2-x, but the
difference between them, x, gets arbitrarily large as x goes to
infinity."
but that shawdow fall pretty far from the oak decidability
SH: So this rule does not appear to uniquely predict the next
item in the sequence, but a likely area for the next occurrence.
Since Case provided a finite example and then drew his
conclusion, I assumed that the mathematical rules that could
not be discovered were true of finite instances as well of
course as infinite examples.

So this issue of the limits of sequence prediction is due to
Godel Inc. and the halting problem? It seems like both
might come under the umbrella of decidability, but this
particular question falls on the outskirts of the shadow of
the umbrella, if at all, IMO. Do you see a closer connection?

Schmidhuber and Hutter talk about strategies to "remember"
old working algorithms which are replaced with algorithmic
better matches to making predictions, when it happens that
the new improved algorithm turns out to be a fluke improvement
in the long run. It seems in some programs the old working
criteria were erased when something new/better was found
and then when that was discovered to be not so good, the
older approach was irretrievable. Schmidhuber talks about
keeping the backup until one is certain that prediction is
maximized, but I had my doubts about his description of this.
Anyway, AIXI and the Godel machine mentioned things
about algorithms that reminded me of your 'notion'.

{*twin}
http://www.utm.edu/research/primes/notes/faq/NextMersenne.html

"What about the next Mersenne?
So what can we gather from this? One thing is that given one
Mersenne prime exponent's p, the next one will fall, on the
average, near 1.47576p. But not too near the average much of
the time--sometimes the gaps will be small, sometimes large.
So the next (possibly the 41st) Mersenne exponent might be
about 31,000,000 yielding a Mersenne with about 9.3 million
digits. Or it may not."

http://www.utm.edu/research/primes/mersenne/heuristic.html
SH: I bring this up because it demonstrates a rule (perhaps)
but not the specific next Mersenne Prime. I think Case's article
is about specific prediction of the next member in the sequence,
but that this cannot happen in some cases because the sequence
itself if too big and complex even though the sequence is finite.

"One can not miss that this graph is amazingly linear. Erhardt
(and many others after him) looked at the limited data and guessed
that the geometric mean of the ratio of two successive Mersenne
exponents 3/2.
Some time later Wagstaff (and independently Pomerance and Lenstra)
each suggested this should be 2 raised to 1/egamma or about 1.47576
(not 3/2). (This is Euler's constant gamma.) This is now the
accepted value, but why? Below we will answer this question by using
a simple heuristic argument.

If you are in a rush, then let me simply follow Ribenboim
[Ribenboim95] and state the factor egamma comes by analogy from
Mertens' theorem. Otherwise, take a sip of coffee and join us for
a little mathematics."

http://www.utm.edu/research/primes/infinity.shtml#twin
SH: I mention this because it reminded me a bit of Case's example.

The Sum of the Reciprocal of the Primes
"When the sums of the reciprocals of a set of positive integers
converge (example: the square integers), we think of that set
as "small." When it diverges (example: the positive integers) we
think of that set as "larger." So what about the set of primes?
We will show below that the sum of the reciprocals of the primes
diverges, so the primes are a "large" subset of the integers.
This is a simple consequence of the prime number theorem, but
much more elementary proofs are available (e.g., [Ribenboim88
pp. 156-7]). On the other hand, it is conjectured that there
are infinitely many twin primes (this is the twin prime conjecture,
most everybody believes it is true--we just do not have a proof yet).
Nevertheless, it has been proven the sum of the reciprocals of the
twin primes is about is 1.90216054... (this is called Brun's constant).
So the twin primes are only a "small" subset of the integers (in this
sense)."

SH: I've read a bit from Penrose's new book "The Road To Reality".
I was interested to see if he justified from a quantum approach why
he thought QFT and consciousness might be linked. I've found
nothing yet. I did find out why Penrose thinks there is more than just
quantum theory needed to explain the physics of the universe. He
has a lot of views which he freely admits are not conventional wisdom.
I have trouble with the book, I think one needs a lot of Physics edu.

Regards,
Stephen

 

Relevant Pages

  • Re: Math errors in book Secret Life of Numbers
    ... his students have proven that primes can be found in polynomial time. ... For practical purposes the algorithm is, admittedly, still too ... that in practice, it always was solved in polynomial time using the ... the simplex method is not a polynomial-time algorithm. ...
    (sci.math.research)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)