Fast-Growing Hierarchy - Revision history

Sligocki: /* Examples */ Fix f_omega(0) = 1 issue

2026-04-22T19:28:56Z

Examples: Fix f_omega(0) = 1 issue

← Older revision		Revision as of 19:28, 22 April 2026
Line 23:		Line 23:

	== Examples ==		== Examples ==
	* <math>f_\alpha(0) = ~~0</math> for <math>\alpha >~~ 0</math>		* <math>f_{\alpha+1}(0) = 0</math>
	* <math>f_\alpha(1) = 2</math>		* <math>f_\alpha(1) = 2</math>

C7X: Spacing /* Examples */

2026-04-22T19:26:39Z

Spacing Examples

← Older revision		Revision as of 19:26, 22 April 2026
Line 23:		Line 23:

	== Examples ==		== Examples ==
	* <math>f_\alpha(0) = 0</math>for <math>\alpha > 0</math>		* <math>f_\alpha(0) = 0</math> for <math>\alpha > 0</math>
	* <math>f_\alpha(1) = 2</math>		* <math>f_\alpha(1) = 2</math>

C7X: f_ω(0) = f_0(0) = 1 /* Table of Small Values */

2026-04-22T19:26:13Z

f_ω(0) = f_0(0) = 1 Table of Small Values

← Older revision		Revision as of 19:26, 22 April 2026
Line 114:		Line 114:
	\|-		\|-
	\|<math>f_\omega(n)</math>		\|<math>f_\omega(n)</math>
	\|0		\|1
	\|2		\|2
	\|8		\|8

Sligocki: /* Examples */ Update to base 10

2026-04-22T17:45:05Z

Examples: Update to base 10

← Older revision		Revision as of 17:45, 22 April 2026
Line 23:		Line 23:

	== Examples ==		== Examples ==
	~~Small indexes:~~		* <math>f_\alpha(0) = 0</math>for <math>\alpha > 0</math>
			* <math>f_\alpha(1) = 2</math>

	* <math>f_0(n) = n+1</math>		* <math>f_0(n) = n+1</math>
Line 29:		Line 30:
	* <math>f_2(n) = n \cdot 2^n</math>		* <math>f_2(n) = n \cdot 2^n</math>
	* <math>f_3(n) = f_2^n(n) > (2 \uparrow)^n(n + \log_2 n) > (2 \uparrow)^n n \ge 2 \uparrow\uparrow (n+1)</math> for <math>n \ge 2</math>		* <math>f_3(n) = f_2^n(n) > (2 \uparrow)^n(n + \log_2 n) > (2 \uparrow)^n n \ge 2 \uparrow\uparrow (n+1)</math> for <math>n \ge 2</math>
	* <math>~~f_k(n) = f_{k-1}^n~~(n) > (2 \uparrow~~^{k-2})^~~n(n ~~+ 1~~) > 2 \uparrow^{k-1} (n~~+1)</math>~~ for ~~<math>~~n \ge 2</math>		* <math>f_3(n) > 10 \uparrow\uparrow n</math> for <math>n \ge 4</math>
	* <math>f_\omega(n) = f_n(n) > 2 \uparrow^{n-1} (n~~+1)</math>~~ for ~~<math>~~n \ge 2</math>		* <math>f_k(n) > 10 \uparrow^{k-1} n \; \text{ for } k \ge 4 \text{ and } n \ge 2 </math>
			* <math>f_\omega(n) = f_n(n) > 10 \uparrow^{n-1} n \; \text{ for } n \ge 4</math>
	* <math>f_{\omega+1}(64) = f_\omega^{64}(64) > \text{Graham's number}</math>		* <math>f_{\omega+1}(64) = f_\omega^{64}(64) > \text{Graham's number}</math>

	~~Small arguments:~~		*

	* ~~<math>f_\alpha(0) = 0</math>for <math>\alpha > 0</math>~~
	* <math>f_\alpha(1) = 2</math>

	=== Table of Small Values ===		=== Table of Small Values ===

Sligocki: Add Examples section including Tables of Small Values

2026-04-22T17:38:39Z

Add Examples section including Tables of Small Values

← Older revision		Revision as of 17:38, 22 April 2026
Line 21:		Line 21:

	The FGH given by these fundamental sequences is sometimes called the Wainer hierarchy. Above <math>\varepsilon_0</math>, a relatively elegant choice is the expansion associated to the [https://apeirology.com/wiki/Bashicu_matrix_system Bashicu matrix system], which has the [https://en.wikipedia.org/wiki/Fundamental_sequence_(set_theory)#Additional_conditions Bachmann property].		The FGH given by these fundamental sequences is sometimes called the Wainer hierarchy. Above <math>\varepsilon_0</math>, a relatively elegant choice is the expansion associated to the [https://apeirology.com/wiki/Bashicu_matrix_system Bashicu matrix system], which has the [https://en.wikipedia.org/wiki/Fundamental_sequence_(set_theory)#Additional_conditions Bachmann property].

			== Examples ==
			Small indexes:

			* <math>f_0(n) = n+1</math>
			* <math>f_1(n) = 2n</math>
			* <math>f_2(n) = n \cdot 2^n</math>
			* <math>f_3(n) = f_2^n(n) > (2 \uparrow)^n(n + \log_2 n) > (2 \uparrow)^n n \ge 2 \uparrow\uparrow (n+1)</math> for <math>n \ge 2</math>
			* <math>f_k(n) = f_{k-1}^n(n) > (2 \uparrow^{k-2})^n(n + 1) > 2 \uparrow^{k-1} (n+1)</math> for <math>n \ge 2</math>
			* <math>f_\omega(n) = f_n(n) > 2 \uparrow^{n-1} (n+1)</math> for <math>n \ge 2</math>
			* <math>f_{\omega+1}(64) = f_\omega^{64}(64) > \text{Graham's number}</math>

			Small arguments:

			* <math>f_\alpha(0) = 0</math>for <math>\alpha > 0</math>
			* <math>f_\alpha(1) = 2</math>

			=== Table of Small Values ===
			{\| class="wikitable"
			\|+
			!
			! colspan="8" \|n
			\|-
			!
			!0
			!1
			!2
			!3
			!4
			!5
			!...
			!n
			\|-
			\|<math>f_0(n)</math>
			\|1
			\|2
			\|3
			\|4
			\|5
			\|6
			\|
			\|n+1
			\|-
			\|<math>f_1(n)</math>
			\|0
			\|2
			\|4
			\|6
			\|8
			\|10
			\|
			\|2n
			\|-
			\|<math>f_2(n)</math>
			\|0
			\|2
			\|8
			\|24
			\|64
			\|160
			\|
			\|<math>n \, 2^n</math>
			\|-
			\|<math>f_3(n)</math>
			\|0
			\|2
			\|2048
			\|<math>>10^{10^8}</math>
			\|<math>> 10^{10^{10^{20}}}</math>
			\|<math>> (10 \uparrow)^4 49 > 10 \uparrow\uparrow 5</math>
			\|
			\|<math>> 10 \uparrow\uparrow n</math>
			\|-
			\|<math>f_4(n)</math>
			\|0
			\|2
			\|<math>> 10 \uparrow\uparrow 2048</math>
			\|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 10^{10^8} > 10 \uparrow\uparrow\uparrow 3</math>
			\|<math>> 10 \uparrow\uparrow\uparrow 4</math>
			\|<math>> 10 \uparrow\uparrow\uparrow 5</math>
			\|
			\|<math>> 10 \uparrow\uparrow\uparrow n</math>
			\|-
			\|...
			\|
			\|
			\|
			\|
			\|
			\|
			\|
			\|
			\|-
			\|<math>f_\omega(n)</math>
			\|0
			\|2
			\|8
			\|<math>>10^{10^8}</math>
			\|<math>> 10 \uparrow\uparrow\uparrow 4</math>
			\|<math>> 10 \uparrow^4 5</math>
			\|
			\|<math>> 10 \uparrow^{n-1} n</math>
			\|-
			\|<math>f_{\omega+1}(n)</math>
			\|0
			\|2
			\|<math>> 10 \uparrow^7 8</math>
			\|
			\|
			\|
			\|
			\|
			\|}

	== Growth Bound Theorem ==		== Growth Bound Theorem ==

RobinCodes: Added FGH Growth Bound Theorem from https://wiki.bbchallenge.org/wiki/Fast-Growing_Hierarchy_Growth_Bound_Theorem

2025-11-04T18:30:18Z

Added FGH Growth Bound Theorem from https://wiki.bbchallenge.org/wiki/Fast-Growing_Hierarchy_Growth_Bound_Theorem

← Older revision		Revision as of 18:30, 4 November 2025
Line 21:		Line 21:

	The FGH given by these fundamental sequences is sometimes called the Wainer hierarchy. Above <math>\varepsilon_0</math>, a relatively elegant choice is the expansion associated to the [https://apeirology.com/wiki/Bashicu_matrix_system Bashicu matrix system], which has the [https://en.wikipedia.org/wiki/Fundamental_sequence_(set_theory)#Additional_conditions Bachmann property].		The FGH given by these fundamental sequences is sometimes called the Wainer hierarchy. Above <math>\varepsilon_0</math>, a relatively elegant choice is the expansion associated to the [https://apeirology.com/wiki/Bashicu_matrix_system Bashicu matrix system], which has the [https://en.wikipedia.org/wiki/Fundamental_sequence_(set_theory)#Additional_conditions Bachmann property].

			== 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]

Int-y1: bold name

2025-08-25T08:31:41Z

bold name

← Older revision		Revision as of 08:31, 25 August 2025
Line 1:		Line 1:
	A Fast-Growing Hierarchy (FGH) is an ordinal-indexed hierarchy of functions satisfying certain restrictions. FGHs are used for assigning growth rates to fast computable functions, and are useful for approximating scores and halting times of [[Turing machine\|Turing machines]].		A '''Fast-Growing Hierarchy''' (FGH) is an ordinal-indexed hierarchy of functions satisfying certain restrictions. FGHs are used for assigning growth rates to fast computable functions, and are useful for approximating scores and halting times of [[Turing machine\|Turing machines]].
	[[Category:Functions]]		[[Category:Functions]]
	== Definition ==		== Definition ==

Qwerpiw at 16:45, 13 August 2025

2025-08-13T16:45:56Z

← Older revision		Revision as of 16:45, 13 August 2025
Line 1:		Line 1:
	A Fast-Growing Hierarchy (FGH) is an ordinal-indexed hierarchy of functions satisfying certain restrictions. FGHs are used for assigning growth rates to fast computable functions, and are useful for approximating scores and halting times of [[Turing machine\|Turing machines]].		A Fast-Growing Hierarchy (FGH) is an ordinal-indexed hierarchy of functions satisfying certain restrictions. FGHs are used for assigning growth rates to fast computable functions, and are useful for approximating scores and halting times of [[Turing machine\|Turing machines]].
			[[Category:Functions]]
	== Definition ==		== Definition ==

Polygon: Added link to "Turing machine", no longer a dead end

2025-08-11T09:43:07Z

Added link to "Turing machine", no longer a dead end

← Older revision		Revision as of 09:43, 11 August 2025
Line 1:		Line 1:
	A Fast-Growing Hierarchy (FGH) is an ordinal-indexed hierarchy of functions satisfying certain restrictions. FGHs are used for assigning growth rates to fast computable functions, and are useful for approximating scores and halting times of Turing machines.		A Fast-Growing Hierarchy (FGH) is an ordinal-indexed hierarchy of functions satisfying certain restrictions. FGHs are used for assigning growth rates to fast computable functions, and are useful for approximating scores and halting times of [[Turing machine\|Turing machines]].

	== Definition ==		== Definition ==

Racheline: explained FS systems

2024-08-15T16:36:06Z

explained FS systems

← Older revision		Revision as of 16:36, 15 August 2024
Line 2:		Line 2:

	== Definition ==		== Definition ==

			A fundamental sequence for an ordinal <math>\alpha</math> is an increasing sequence of ordinals <math><\alpha</math> which is unbounded in <math>\alpha</math>. The <math>\beta</math>-th element of <math>\alpha</math>'s fundamental sequence is denoted by <math>\alpha[\beta]</math>. In the context of FGHs, there is usually a restriction that the sequence's length must be as small as possible (that is, the length is the [https://en.wikipedia.org/wiki/Cofinality cofinality] of <math>\alpha</math>). A system of fundamental sequences for a set of ordinals is a function which assigns a fundamental sequence to each ordinal in the set.

	Given a system of fundamental sequences for limit ordinals below <math>\lambda</math>, its corresponding FGH is defined by		Given a system of fundamental sequences for limit ordinals below <math>\lambda</math>, its corresponding FGH is defined by