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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
