递归函数与寄存器机

递归函数理论从少数基本操作构建可计算函数，而寄存器机则使用存储在寄存器中的整数进行计算。这两种模型与图灵机相辅相成，共同证实了可计算性的稳健性。

Definition

通用递归函数是通过组合、原始递归和无界最小化从常量、后继函数和投影函数构建的函数；寄存器机是抽象设备，通过递增、递减和测试有限寄存器集中存储的自然数内容进行计算。

Scope

本主题涵盖原始递归函数、通过添加无界最小化获得的通用递归函数、作为可计算函数但非原始递归函数的阿克曼函数、寄存器机和计数器机及其通用性，以及所有这些模型与图灵可计算性的等价性。

Core questions

• 如何在不使用任何机器的情况下算术地定义可计算函数？
• 为什么除了原始递归之外还需要无界最小化？
• 简单的寄存器机如何实现完整的计算能力？
• 为什么这些算术和机器模型与图灵机一致？

Key theories

与图灵可计算性的等价性

通用递归函数和寄存器机计算的函数正是图灵可计算函数，通过纯算术和基本机器术语定义的模型，强化了丘奇-图灵论题。

超越原始递归

阿克曼函数是全函数且可计算，但其增长速度过快，无法成为原始递归函数，这表明无界搜索是必不可少的，并且原始递归函数是可计算函数的一个真子类。

寄存器机的通用性

明斯基证明，一个只有两个计数器以及递增、递减和零测试操作的机器已经图灵完备，这极端地展示了完整计算所需的结构是多么少。

Clinical relevance

寄存器机比磁带更直接地模拟真实处理器的整数算术；原始递归对应于总是终止的程序，是全功能语言和终止分析的基础；递归函数视图将计算与数学基础联系起来。

History

哥德尔和赫布兰德在20世纪30年代早期定义了通用递归函数，克莱尼发展了该理论，包括最小化的作用。阿克曼早些时候展示了他的快速增长函数，明斯基在20世纪60年代引入了寄存器机和计数器机，证明了即使是双计数器机也具有通用性。

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

原始递归函数和通用递归函数有什么区别？

原始递归函数使用有界循环构建，并且总是终止，但它们不能捕获所有可计算函数。添加无界最小化（一种可能无限运行的搜索）会产生通用递归函数，它们与图灵可计算函数完全一致。

只有两个计数器的机器如何能像计算机一样强大？

明斯基证明，两个存储自然数的寄存器，仅通过递增、递减和零测试操作，可以通过将磁带编码到寄存器中来模拟图灵机。这种构造效率极低，但它证明了最少的硬件已经达到了完整的计算能力。