BB(3, 4) > Ack(14)
2024-05-23
本文介绍了Pavel发现的一种3状态4符号图灵机，它能够计算“阿克曼级别”的函数，并在纸带上留下[(2↑^15 5)+14]个非零符号后停止。文章详细分析了该图灵机的行为，并通过双重归纳法证明了其停止性。此外，文章还探讨了该图灵机的不同起始状态对其最终得分的影响，并将其与其他已知图灵机进行了比较。
49