|
|
| Line 1: |
Line 1: |
| {{Stub}}
| | #REDIRECT [[Fast-Growing Hierarchy#Growth Bound Theorem]] |
| The ''Fast-Growing Hierarchy Growth Bound Theorem'' is an important result in mathematical logic that has significant implications for unprovability results. The theorem highlights a relationship between computable functions that are provably total in first-order Peano Arithmetic (PA) and the fast-growing functions in the [[Fast-Growing Hierarchy|Wainer hierarchy]].
| |
| | |
| The theorem is based on work by several mathematicians. Georg Kreisel laid the groundwork in 1952 by investigating connections between recursions over well ordered sets and proofs in PA. These results were subsequently extended by many others; the following form is based on the presentation by Buchholz and Wainer.
| |
| | |
| == Statement ==
| |
| | |
| Let <math>T</math> be a Turing machine that computes a function <math>g:\N\to\N</math>, terminating on every input. Suppose that PA can prove the statement «<math>T</math> terminates on every input.» Then <math>g</math> cannot grow too fast: There exist <math>\alpha < \varepsilon_0</math> and <math>n_0\in\N</math> such that <math>g(n) < F_\alpha(n)</math> for every <math>n\ge n_0</math>.
| |
| | |
| == References ==
| |
| Wilfried Buchholz and Stan S. Wainer. Provably computable functions and the fast growing hierarchy. In S. G. Simpson, editor, Logic and Combinatorics, volume 65 of Contemporary Mathematics, pages 179–198. AMS, 1987. [https://epub.ub.uni-muenchen.de/3843/1/3843.pdf]
| |
| | |
| [[Category:Computability theory]]
| |