指数运算（^）后面的数学运算是什么？

Question

让我们给表达式一些名称：

x+3 = x+1+1+1 // lvl 1
x*3 = x+x+x   // lvl 2
x^3 = x*x*x   // lvl 3

在数学中，第3级后的lvl的数学术语/真实名称/主题是什么？

比如：

x (lvl 4 operation) 3 = x^x^x
x (lvl 5 operation) 3 = x(lvl 4 operation)x(lvl 4 operation)x
..

预先感谢您。

附言：上述内容并不是编程代码或语言

- Arty McLabin

---

这是一个 Haskell 问题吗？ - Alois Mahdal

请查看原始的三参数阿克曼函数！ - pigworker

我投票关闭这个问题，因为它涉及数学而非编程。请参考这个Math.SE问题。 - duplode

还有上箭头符号。 - J. Abrahamson

@Alois Mahdal：我知道很多关于lambda表达式的东西，但我认为Haskeller们更有可能知道答案 :) - Arty McLabin

Answer 1

Tetration是指数运算之后的下一个超级运算符。该运算符按照Knuth表示法,用↑↑或ASCII码中的^^表示。

这个序列中的下一个运算是pentation，然后是hexation，heptation，octation等等。Ackermann的三元函数通过递归计算这些运算。

╭────────┬────────────────┬─────────────┬───────────────────╮
│  Level │     Name       │  Notation   │ Ackermann (3-arg) │
╞════════╪════════════════╪═════════════╪═══════════════════╡   
│    1   │   Successor    │ a++ (unary) │   φ(a, 1, 0)      │
│    2   │   Addition     │ a+b         │   φ(a, b, 0)      │
│    3   │ Multiplication │ a×b         │   φ(a, b, 1)      │ 
│    4   │ Exponentiation │ a↑b         │   φ(a, b, 2)      │
│    5   │   Pentation    │ a↑↑b        │   φ(a, b, 3)      │
│    6   │   Hexation     │ a↑↑↑b       │   φ(a, b, 4)      │
│    7   │   Heptation    │ a↑↑↑↑b      │   φ(a, b, 5)      │
│    8   │   Octation     │ a↑↑↑↑↑b     │   φ(a, b, 6)      │
╰────────┴────────────────┴─────────────┴───────────────────╯

- trincot

Answer 2

实际上，在指数运算之外，没有其他通用的操作（主要是由于没有需求）。一种可能的扩展是tetration，它使用相同值的幂栈进行缩写。简要介绍一下（使用Knuth的上箭头符号表示法）

a ^^ 1 = a
a ^^ n = a^(a^^(n-1))
       = a ^ a ^ ... ^ a  (n items)

向上箭头符号本身可以堆叠，a^^^a 是一个高度为 a^^a 的 a 堆栈，a^^^^a 是一个高度为 a^^^a 的 a^^a 堆栈，以此类推。（生成的数字非常大；阅读有关格雷厄姆数的内容，以了解您可以构建多大的数字。）

- chepner

Answer 3

通过使用“参数范畴”对自然数进行表示，以及不使用其他形式的递归，实现阿克曼函数（无论是哪个版本），这是将此问题转换为Haskell问题的一种方式。

paraNat :: t -> ((Integer, t) -> t) -> Integer -> t
paraNat base step n | n > 0 = step (m, paraNat base step m) where m = n - 1
paraNat base step _         = base

众所周知，“参数形式”对应于“原始递归”，而阿克曼函数不属于“原始递归函数”类别，但这个问题有解决方法。关键在于paraNat的返回类型t是多态的，而“原始递归函数”的类别将t固定为自然数。

（我意识到用提问来回答问题有点不正常，但我希望这个回答还是有趣的。如果大家认为有问题，我会删除这个回答。）

- pigworker

---

有趣的是，今天我重新发明了 Ackermann 函数的纯复制，这让我想知道它以前是否存在。Haskell 等于爱。 - Arty McLabin

你也可以不使用多态来实现。 - augustss