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,
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
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
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
Journal of Symbolic Logic, 54, N° 2
Quite interesting and relevant for the Löbian number's bio-psycho-
GOOD I.J, 1971, Freewill and Speed of Computation. Brit. J. Phil. Sci.
Some good books:
ARBIB M., 1964, Brains, Machines and Mathematics, McGraw-Hill, 2ème
éd. : 1987,
CALUDE C. Theories of Computational complexity, North Holland, 1988.
SALOMAA A.,1985, Computation and Automata, Cambridge University Press,
Ah, you can look here too:
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to firstname.lastname@example.org.
To unsubscribe from this group, send email to
For more options, visit this group at