使用阿克曼函数？

Question

在我大学的离散数学课程中,教师向学生展示Ackermann功能,并指导学生在纸上开发功能.

除了作为递归优化的基准之外,Ackermann函数是否有任何实际用途？

Answer 1

是.(逆)Ackermann函数出现在算法的复杂性分析中.当它发生时,它意味着你几乎可以忽略该术语,因为它变得如此缓慢(很像log(log ... log(n)......)),即lg*(n).例如:最小生成树(也在这里)和不相交集森林构造.

另外:Davenport-Scinzel序列

Answer 2

Ackermann函数的原始"使用"是为了表明存在非原始递归的函数,即不能仅通过使用具有预定上限的循环来计算.

Ackermann函数就是这样一个函数,它变得太快而不能原始递归.

我认为没有真正的实际用途,它变得太快而无法发挥作用.您甚至无法在合理的空间中明确表示超出(4,3)的数字.