Journal of Symbolic Logic 43 (4):667-672 (1978)

Abstract
We study the measure independent character of Godel speed-up theorems. In particular, we strengthen Arbib's necessary condition for the occurrence of a Godel speed-up [2, p. 13] to an equivalence result and generalize Di Paola's speed-up theorem [4]. We also characterize undecidable theories as precisely those theories which possess consistent measure independent Godel speed-ups and show that a theory τ 2 is a measure independent Godel speed-up of a theory τ 1 if and only if the set of undecidable sentences of τ 1 which are provable in τ 2 is not recursively enumerable
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2273506
Options
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: 58,276
Through your library

References found in this work BETA

Computability & Unsolvability.Clifford Spector - 1958 - Journal of Symbolic Logic 23 (4):432-433.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
29 ( #361,564 of 2,419,614 )

Recent downloads (6 months)
8 ( #87,603 of 2,419,614 )

How can I increase my downloads?

Downloads

My notes