On 31 Jan 2012, at 19:33, meekerdb wrote:

On 1/31/2012 10:25 AM, Bruno Marchal wrote:

That's the reason mind exist, it accelerate the processing much more quickly. In fact, just by software change, the slower machine can always beat the faster machines, on almost inputs, except a finite number of them.

I can accept that intuitively, but can you point to a technical proof?

I basically got in mind Gödel's length of proof theorem of 1936, and Blum's speed-up theorem of 1967.

Adding an undecidable sentence, undecidable by a theory/machine T, to the theory/machine T, not only makes an infinity of undecidable sentences decidable, but it shorten infinitely many proofs.

In T + con(T), for example, infinities of (arithmetical) propositions are decidable (and undecidable in T), and infinity of proofs can be arbitrarily sped up.

Blum obtained in 1967 a related result in term of computational speed.

GÖDEL K., 1936, On the Length of Proofs, translated in Davies 1965, pp. 82-83.

BLUM, M., 1967, "A Machine-Independent Theory of the Complexity of Recursive Functions", Journal of the ACM 14: 322–336.

A characterization of the self-speedable machines has been made by Blum and Marquez in term of "subcreative sets", which generalizes the creative sets (provably equivalent, in some sense, to the universal sets /sets/machine/numbers). So you have a notion of subuniversal numbers, with the universal one as special cases, which correspond to the self-speedable machine/ numbers. All universal numbers are speedable, but not all speedable numbers are universal.

BLUM M. and MARQUES I., 1973, On Complexity properties of Recursively Enumerable
Sets, Journal of Symbolic Logic, Vol 38, N° 4, pp. 579-593.

Another interesting paper is:

ROYER J.S., 1989, Two Recursion Theoretic Characterizations of Proof Speed-ups, The
Journal of Symbolic Logic, 54, N° 2

Quite interesting and relevant for the Löbian number's bio-psycho- theology is:

GOOD I.J, 1971, Freewill and Speed of Computation. Brit. J. Phil. Sci. 22, 48-49.

Some good books:

ARBIB M., 1964, Brains, Machines and Mathematics, McGraw-Hill, 2ème éd. : 1987,
Springer-Verlag, New-York.

CALUDE C. Theories of Computational complexity, North Holland, 1988.

SALOMAA A.,1985, Computation and Automata, Cambridge University Press,
Cambridge.

Ah, you can look here too:

http://en.wikipedia.org/wiki/Blum's_speedup_theorem

Bruno

http://iridia.ulb.ac.be/~marchal/



--
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Reply via email to