TON记号

合法表达式

常量包含$0,{\mathrm{\Omega }}_n$。

• 常量是合法表达式；
• 如果$a$和$b$是合法表达式，那么$C(a,b)$是合法表达式。

后缀形式

对于一个合法表达式，我们删去它其中的所有$,$与$()$，并反转整个字符串，即为该表达式的后缀形式。

比较

对于两个合法表达式，它们的大小关系等同于它们的后缀形式在字典序上的大小关系（我们认为$C<0<{\mathrm{\Omega }}_n$）。

标准表达式

• 常量是合法表达式；
• $C(a,b)$是标准表达式当且仅当：
  • $a,b$是标准表达式；
  • 如果$b$能表示成$C(c,d)$的形式，则$a\le c$；
  • 对于不同的版本，还有一些额外的条件，我们一般称其为 built-from-below 条件。

为了检查 built-from-below 条件，我们需要遍历某些表达式的语法树，为此，我们需要一些辅助定义：

• 位于不同位置的同类型的项被认为是不同的；
• 对于一个表达式$C(a,b)$，我们称$a$和$b$是$C(a,b)$的子项，记作$a,b⊑C(a,b)$；
• 我们称a是b的真子项（记作$a⊏b$），当且仅当$a⊑b\wedge a\ne b$。

与序数的关系

TON 中的标准表达式和序数一一对应。具体的，对于一个标准表达式$a$，如果有一系列小于它的表达式$b_1,b_2\cdots$，则$a$对应的序数为$b_1,b_2\cdots$对应的序数的上确界。

性质

• $C(a,b)>b$；
• $C(a,b)$对$a,b$都单调递增，且对$a$连续；
• $C(a,b)=b+{\omega }^a$当且仅当$C(a,b)\ge a$。

分析

见TON记号分析

原文

全文见https://zhuanlan.zhihu.com/p/658978883