Laver Table

Laver表是Richard Laver在1992 年提出的一个增长速度很快的表

定义

考虑作用于$\{1,\cdots ,2^n\}$上的二元运算${\star }_n$，它满足如下条件:

\begin{eqnarray*}a \star_n 0 & = & 0 \\a \star_n 1 & = & (a+1) \mod 2^n \\a \star_n i & = & (a \star_n (i-1)) \star_n (a \star_n 1) \ (i \neq 0,1)\end{eqnarray*}

Laver表$A_n$定义为唯一的取值为$a\star nb$的$2^n\times 2^n$表。

注意这一定理仅适用于 2 的幂。假如我们考虑的二元运算作用于一般的$\{1,\cdots ,a\}$上，其中$a\ne 2^n$，则这样的二元运算${\star }_n$将不是存在且唯一的。

我们定义如下函数的周期为 p(n):

• $2^n\to 2^n$
• $a\mapsto 1{\star }_{n}a$

定义q(n)为函数p(n)的逆，即$q(n)=min\{N|p(N)\ge 2^n\}$