Degrees of relative provability (Q691125): Difference between revisions

The aim of the paper is to study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. Several results about the proof-theoretic degree structure are presented. Recursion-theoretic techniques -- e.g., diagonalization and recursion theorem -- are used. Some ideas from a new viewpoint are provided.