Some results on measure independent gödel speed-ups

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

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2009-01-28

Downloads
31 (#445,444)

6 months
1 (#1,042,085)

Historical graph of downloads
How can I increase my downloads?

References found in this work

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