计算模型

从函数重写的λ演算到布尔电路和量子系统，许多形式框架定义了计算的含义，比较它们的计算能力可以揭示哪些模型是等价的，哪些是真正不同的。

Definition

计算模型是一个精确的抽象框架，它规定了允许哪些操作以及计算如何进行；不同的模型可能计算相同类别的函数，但在简洁性、并行性或它们明确的资源方面有所不同。

Scope

该领域涵盖了λ演算和函数模型、递归函数和寄存器机、布尔电路和电路复杂度，以及量子计算，探讨了每种模型如何表达算法，它们的可计算性能力如何通过丘奇-图灵论题关联，以及它们的效率如何分化。

Sub-topics

• 布尔电路与电路复杂性
• Lambda演算与函数模型
• 量子计算模型
• 递归函数与寄存器机

Core questions

• 形式化计算概念有哪些不同的方式？
• 哪些模型在它们可以计算的函数方面是等价的，为什么？
• 一旦效率、并行性或物理可实现性变得重要，模型之间有何不同？
• 像量子计算这样具有物理动机的模型能否超越经典效率？

Key theories

丘奇-图灵论题下的等价性

λ演算、递归函数、寄存器机和图灵机都计算完全相同的函数类别，这种收敛性是计算与图灵可计算性等同的基础。

效率上的差异

在可计算性上一致的模型在资源上可能存在显著差异：电路揭示了并行和非均匀计算，而量子模型似乎提供了加速，因此即使在可计算性上没有差异，模型的选择对于复杂度也至关重要。

Clinical relevance

不同的模型阐明了真实计算的不同方面：λ演算是函数式编程语言的理论基础，电路模拟硬件和并行计算，寄存器机反映了传统处理器，而量子模型指导了新兴量子硬件和算法的设计。

History

在20世纪30年代，丘奇的λ演算、哥德尔和克莱尼的递归函数以及图灵机被分别提出，随后被证明是等价的。后来的模型增加了新的维度：电路复杂度形式化了并行和硬件计算，而费曼在1982年提出的量子模拟为量子计算模型奠定了基础。

Key figures

• Alonzo Church
• Alan Turing
• Stephen Kleene
• Richard Feynman

Seminal works

• church1936
• sipser2013
• aroraBarak2009

Frequently asked questions

如果它们计算相同的函数，为什么还要研究许多模型？

等价性仅适用于原则上可以计算的内容。不同的模型使得表达或分析不同的事物变得容易：λ演算阐明了函数式编程，电路揭示了并行性和硬件成本，量子模型捕捉了物理现象，因此每种模型都是解决不同问题的正确视角。

所有计算模型都等价吗？

所有合理的经典模型都计算相同类别的函数，这支持了丘奇-图灵论题。但它们在效率上可能存在巨大差异，并且利用不同资源（如量子叠加）的模型，即使计算相同的函数，也可能更快地解决某些问题。