Degrees of relative provability (Q691125)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Degrees of relative provability |
scientific article |
Statements
Degrees of relative provability (English)
0 references
29 November 2012
0 references
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.
0 references
degree structure
0 references
provability strength
0 references
totality of recursive functions
0 references
relative provability order of recursive algorithms
0 references
