Mathematical Logic Quarterly 39 (1):384-392 (1993)

We provide and interpret a new measure independent characterization of the Gödel speed-up phenomenon. In particular, we prove a theorem that demonstrates the indifference of the concept of a measure independent Gödel speed-up to an apparent weakening of its definition that is obtained by requiring only those measures appearing in some fixed Blum complexity measure to participate in the speed-up, and by deleting the “for all r” condition from the definition so as to relax the required amount of speed-up. We interpret our results as correlating the relative difficulty of mechanically recognizing theories with the relative power and the relative abstractness of the theories. We conclude by providing two open problems concerning possible similarities and relationships between the Blum speedability and Gödel speed-up phenomena. MSC: 03D15, 03F20
Keywords Blum complexity measure  Speed‐up theorems  Length of proof  Speedable set
Categories No categories specified
(categorize this paper)
DOI 10.1002/malq.19930390142
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,056
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Undecidable Theories.Alfred Tarski - 1968 - Amsterdam: North-Holland Pub. Co..
Undecidable Theories.Martin Davis - 1959 - Journal of Symbolic Logic 24 (2):167-169.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

View all 14 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Some Results on Measure Independent Gödel Speed-Ups.Martin K. Solomon - 1978 - Journal of Symbolic Logic 43 (4):667-672.
A Connection Between Blum Speedable Sets and Gödel's Speed-Up Theorem.Martin K. Solomon - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (5):417-421.
On Subcreative Sets and S-Reducibility.John T. Gill Iii & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669 - 677.
Strong Measure Zero Sets Without Cohen Reals.Martin Goldstern, Haim Judah & Saharon Shelah - 1993 - Journal of Symbolic Logic 58 (4):1323-1341.
Ramsey Sets, the Ramsey Ideal, and Other Classes Over R.Paul Corazza - 1992 - Journal of Symbolic Logic 57 (4):1441 - 1468.
Finite Powers of Strong Measure Zero Sets.Marion Scheepers - 1999 - Journal of Symbolic Logic 64 (3):1295-1306.


Added to PP index

Total views
10 ( #853,304 of 2,427,676 )

Recent downloads (6 months)
2 ( #329,204 of 2,427,676 )

How can I increase my downloads?


My notes