线性数阵

重定向到：

线性数阵是大部分数阵型记号的基础。

定义

这里以BEAF的线性数阵为例。

一个合法的 BEAF 线性数阵表达式形如 ${b, p, a_{1}, a_{2}, \dots, a_{n}}$ 其中 $n$ 为非负整数， $b, p, a_{i}$ 均为正整数。

我们进行以下约定：

BEAF 线性数阵的展开规则如下：

若没有驾驶员，则数阵的值为 $b^{p}$ ；
若指数为1，则数阵的值为 $b$ ；
否则，将驾驶员-1，副驾驶改为"整个数阵指数-1后的值"，将副驾驶左边的数全部替换为底数。例如， ${4, 3, 1, 2} = {4, 4, {4, 2, 1, 2}, 1} = {4, 4, {4, 4, {4, 1, 1, 2}, 1}, 1} = {4, 4, {4, 4, 4, 1}, 1}$ 。

这里介绍一种改进的线性数阵。它将经典的线性数阵改成了容易分析增长率的一元函数，将每一项的默认值改成了0，且删除了对增长率提升没有帮助的操作。

一个合法的线性数阵表达式形如 $F (x, a_{1}, a_{2}, \dots, a_{n})$ ，其中， $x, n, a_{i}$ 均为非负整数。

我们用"#"表示任意序列，"Z"表示由若干个0组成的序列。

该线性数阵的展开规则如下：

(基础规则)只有一项时，有 $F (x) = x + 1$ ；
(后继规则)若第二项不为0，有 $F (x, a + 1, #) = f^{x} (x)$ ，其中 $f (x) = F (x, a, #)$ 。例如： $F (3, 1, 4) = F (F (F (3, 0, 4), 0, 4), 0, 4)$ ；
(删尾规则)若末项为0，有 $F (#, 0) = F (#)$ ，例如： $F (2, 1, 0) = F (2, 1)$ 。
(借位规则)否则，第二项为0且存在不为0的项。此时有 $F (x, Z, 0, a + 1, #) = F (x, Z, x, a, #)$ 。例如： $F (2, 0, 2, 5) = F (2, 2, 1, 5)$ 。

下面用快速增长层级对改进的线性数阵进行增长率分析：

$F (x) = F (x, 0) = x + 1 = f_{0} (x)$

$F (x, 1) = F^{x} (x) \sim f_{0}^{x} (x) = f_{1} (x)$

$F (x, 2) \sim f_{1}^{x} (x) = f_{2} (x)$

$F (x, n) \sim f_{n} (x)$

$F (x, 0, 1) = F (x, x) \sim f_{x} (x) = f_{ω} (x)$

$F (x, 1, 1) = F (F (\dots, 0, 1), 0, 1) \sim f_{ω + 1} (x)$

$F (x, n, 1) \sim f_{ω + n} (x)$

$F (x, 0, 2) = F (x, x, 1) \sim f_{ω + x} (x) = f_{ω \cdot 2} (x)$

$F (x, 0, n) \sim f_{ω \cdot n} (x)$

$F (x, 0, 0, 1) = F (x, 0, x) \sim f_{ω x} (x) = f_{ω^{2}} (x)$

$F (x, 1, 0, 1) \sim f_{ω^{2} + 1} (x)$

$F (x, 0, 1, 1) = F (x, x, 0, 1) \sim f_{ω^{2} + x} (x) = f_{ω^{2} + ω} (x)$

$F (x, 0, 0, 2) = F (x, 0, x, 1) \sim f_{ω^{2} + ω x} (x) = f_{ω^{2} 2} (x)$

$F (x, 0, 0, 0, 1) = F (x, 0, 0, x) \sim f_{ω^{2} x} (x) = f_{ω^{3}} (x)$

$F (x, 0, 0, 0, 0, 1) \sim f_{ω^{4}} (x)$

$F (x, \underset{n}{\underset{⏟}{0, \dots, 0}}, 1) \sim f_{ω^{n}} (x)$

一般来说，单独的线性数阵的极限增长率为 $ω^{ω}$ ，但其强度会随"后继规则"的变化而变化。

例如，若把第二条规则改为 $F (x, a + 1, #) = F (x + 1, a, #)$ ，则上述分析应该在哈代层级下进行，故极限函数的增长率相当于 $H_{ω^{ω}} (x) \sim f_{ω} (x)$ 。

对于上文增长率分析中的记号，通过如下方法可以快速得到增长率：

取出一个表达式 $F (x, a_{0}, a_{1}, \dots, a_{n})$ ；
取出 $a_{0}, a_{1}, \dots, a_{n}$ 的部分并反转，得到 $a_{n}, \dots, a_{1}, a_{0}$ ；
$F (x, a_{0}, a_{1}, \dots, a_{n})$ 的增长率即为 $ω^{n} \times a_{n} + \dots + ω^{1} \times a_{1} + ω^{0} \times a_{0}$ 。

举个例子： $F (x, 0, 1, 1)$ 的增长率即为 $ω^{2} \times 1 + ω^{1} \times 1 + ω^{0} \times 0$ 。

由于以上原因，(单行)线性数阵也被称为 $ω$ 进制数阵，因为 $ω^{n} \times a_{n} + \dots + ω^{1} \times a_{1} + ω^{0} \times a_{0}$ 类似于一个“ $ω$ 进制数”。

另外，表达式 $ω^{n} \times a_{n} + \dots + ω^{1} \times a_{1} + ω^{0} \times a_{0}$ 对于每个 $a_{i} (i = 0, 1, \dots, n)$ 都是“线性”的，这也是线性数阵中“线性”一词的来源。