Notre Dame Journal of Formal Logic 53 (4):479-489 (2012)

There are many classical connections between the proof-theoretic strength of systems of arithmetic and the provable totality of recursive functions. In this paper we study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. We prove several results about this proof-theoretic degree structure using recursion-theoretic techniques such as diagonalization and the Recursion Theorem
Keywords recursive functions   totality   provability   degree structure
Categories (categorize this paper)
DOI 10.1215/00294527-1722710
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 50,165
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

No references found.

Add more references

Citations of this work BETA

Unprovability and Proving Unprovability.Mingzhong Cai - 2015 - Studia Logica 103 (3):559-578.

Add more citations

Similar books and articles

Accessible Recursive Functions.Stanley S. Wainer - 1999 - Bulletin of Symbolic Logic 5 (3):367-388.
Recursive Analysis.R. L. Goodstein - 1961 - Dover Publications.
Weak Presentations of Computable Fields.Carl G. Jockusch & Alexandra Shlapentokh - 1995 - Journal of Symbolic Logic 60 (1):199 - 208.
Degrees Joining to 0'. [REVIEW]David B. Posner & Robert W. Robinson - 1981 - Journal of Symbolic Logic 46 (4):714 - 722.
Generalized Weak Presentations.Alexandra Shlapentokh - 2002 - Journal of Symbolic Logic 67 (2):787-819.
Some Restrictions on Simple Fixed Points of the Integers.G. L. McColm - 1989 - Journal of Symbolic Logic 54 (4):1324-1345.
On First-Order Theories with Provability Operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.


Added to PP index

Total views
29 ( #333,433 of 2,324,711 )

Recent downloads (6 months)
1 ( #680,091 of 2,324,711 )

How can I increase my downloads?


My notes