Fast-Growing Hierarchy Growth Bound Theorem - Revision history

LegionMammal978: redirect

2025-11-04T18:31:56Z

redirect

← Older revision		Revision as of 18:31, 4 November 2025
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~~]]

Polygon: Used Template:Stub

2025-08-10T22:34:43Z

Used Template:Stub

← Older revision		Revision as of 22:34, 10 August 2025
Line 1:		Line 1:
			{{Stub}}
	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 ''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]].

Line 10:		Line 11:
	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]		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]]		[[Category:Computability theory]]

Bt2901: 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..."

2024-09-14T22:11:56Z

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..."

New page

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:Stub]]
[[Category:Computability theory]]