Fast-Growing Hierarchy Growth Bound Theorem: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
Bt2901 (talk | contribs)
28 edits
Created page with "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 Wainer hierarchy. The theorem is based on work by several mathematicians. Georg Kreisel laid the groundwork in 1952 by inve..."
 
redirect
Tag: New redirect
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
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]].
#REDIRECT [[Fast-Growing Hierarchy#Growth Bound Theorem]]
 
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:Stub]]
[[Category:Computability theory]]

Latest revision as of 18:31, 4 November 2025

Redirect to:

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Fast-Growing_Hierarchy_Growth_Bound_Theorem&oldid=4987"