Definition:Ackermann-Péter Function

From ProofWiki
Jump to navigation Jump to search

Definition

The Ackermann-Péter function $A: \Z_{\ge 0} \times \Z_{\ge 0} \to \Z_{> 0}$ is an integer-valued function defined on the set of ordered pairs of positive integers as:

$\map A {x, y} = \begin{cases} y + 1 & : x = 0 \\ \map A {x - 1, 1} & : x > 0, y = 0 \\ \map A {x - 1, \map A {x, y - 1} } & : \text{otherwise} \end{cases}$


Also defined as



Some sources define the Ackermann function as $A: \Z_{> 0} \times \Z_{> 0} \to \Z_{> 0}$ where:

$\map A {x, y} = \begin{cases} 2 y & : x = 1 \\ x & : x > 1, y = 1 \\ \map A {x - 1, \map A {x, y - 1} } & : \text{otherwise} \end{cases}$


Examples

$\begin {array} {c|c|c|c} \map A {m, n} & m = 0 & m = 1 & m = 2 & m = 3 \\ \hline n = 0 & 1 & \map A {0, 1} & \map A {1, 1} & \map A {2, 1} \\ n = 1 & 2 & \map A {0, \map A {1, 0} } & \map A {1, \map A {2, 0} } & \map A {2, \map A {3, 0} } \\ n = 2 & 3 & \map A {0, \map A {1, 1} } & \map A {1, \map A {2, 1} } & \map A {2, \map A {3, 1} } \\ n = 3 & 4 & \map A {0, \map A {1, 2} } & \map A {1, \map A {2, 2} } & \map A {2, \map A {3, 2} } \\ n = 4 & 5 & \map A {0, \map A {1, 3} } & \map A {1, \map A {2, 3} } & \map A {2, \map A {3, 3} } \\ \end{array}$

which leads to:

$\begin{array}{c|c|c|c} \map A {m, n} & m = 0 & m = 1 & m = 2 & m = 3 \\ \hline n = 0 & 1 & 2 & 3 & 5 \\ n = 1 & 2 & 3 & 5 & 13 \\ n = 2 & 3 & 4 & 7 & \map A {2, 13} \\ n = 3 & 4 & 5 & 9 & \map A {2, \map A {3, 2} } \\ n = 4 & 5 & 6 & 11 & \map A {2, \map A {3, 3} } \\ \end{array}$




Examples

No, you're right, I really don't know what I'm doing, at all.


$\begin{array}{c|c|c|c} \map A {m, n} & m = 1 & m = 2 & m = 3 & m = 4 & \cdots & m = k \\ \hline n = 1 & 2 & 2 & 3 & 4 & & k \\ n = 2 & 4 & \map A {1, \map A {2, 1} } & \map A {2, \map A {3, 1} } & \map A {3, \map A {4, 1} } & & \map A {k - 1, \map A {k, 1} } \\ n = 3 & 6 & \map A {1, \map A {2, 2} } & \map A {2, \map A {3, 2} } & \map A {3, \map A {4, 2} } & & \map A {k - 1, \map A {k, 2} } \\ n = 4 & 8 & \map A {1, \map A {2, 3} } & \map A {2, \map A {3, 3} } & \map A {3, \map A {4, 3} } & & \map A {k - 1, \map A {k, 3} } \\ n = 5 & 10 & \map A {1, \map A {2, 4} } & \map A {2, \map A {3, 4} }\ & \map A {3, \map A {4, 4} } & & \map A {k - 1, \map A {k, 4} } \\ \vdots & & & & & & \\ n = j & 2 j & \map A {1, \map A {2, j - 1} } & \map A {2, \map A {3, j - 1} } & \map A {3, \map A {4, j - 1} } & & \map A {k - 1, \map A {k, j - 1} } \\ \end{array}$


which leads to:

$\begin{array}{c|c|c|c} \map A {m, n} & m = 1 & m = 2 & m = 3 & m = 4 & \cdots & m = k \\ \hline n = 1 & 2 & 2 & 3 & 4 & & k \\ n = 2 & 4 & 4 & 8 & \map A {3, 4} & & \map A {k - 1, k} \\ n = 3 & 6 & 8 & 2^8 & \map A {3, \map A {4, 2} } & & \map A {k - 1, \map A {k, 2} } \\ n = 4 & 8 & 16 & 2^{2^8} & \map A {3, \map A {4, 3} } & & \map A {k - 1, \map A {k, 3} } \\ n = 5 & 10 & 32 & \map A {2, \map A {3, 4} } & \map A {3, \map A {4, 4} } & & \map A {k - 1, \map A {k, 4} } \\ \vdots & & & & \\ n = j & 2 j & 2^j & \map A {2, \map A {3, j - 1} } & \map A {3, \map A {4, j - 1} } & & \map A {k - 1, \map A {k, j - 1} } \\ \end{array}$






Also known as

The Ackermann-Péter function is also known as the Ackermann function.

However, there are a number of different similar functions which go by this name, so the full appellation can be argued as being more useful.

Also see

  • Results about the Ackermann-Péter function can be found here.


Source of Name

This entry was named for Wilhelm Friedrich Ackermann and Rózsa Péter.


Sources