Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-17T02:13:05.838Z Has data issue: false hasContentIssue false

α-Speedable and non α-Speedable Sets

Published online by Cambridge University Press:  20 November 2018

Barry E. Jacobs*
Affiliation:
University of Maryland, College Park, Maryland
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

α-Recursion theory was invented simultaneously by Kripke [15] and Platek [22] and served to generalize the theories of Takeuti [34], Machover [20], Kreisel and Sacks [14] and others. Kripke (in [16]) derived machinery to construct an analogue to Kleene's T-predicate enabling him to assert that all of unrelativized ordinary recursion theory (as found in Kleene [13]) lifted to α-recursion theory. As a result, we were able to set down in [8] α-analogues to Blum's [1] well-studied axioms, thus, introducing the study of α-computational complexity theory.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1979