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

## Advertising

On 1/31/2012 10:25 AM, Bruno Marchal wrote:That's the reason mind exist, it accelerate the processing muchmore quickly. In fact, just by software change, the slower machinecan always beat the faster machines, on almost inputs, except afinite 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.