机器可计算性之用途究竟是什么？数学图解指导您轻松入门

2023-11-22 理论教育版权反馈

【摘要】：为了考量一台计算机的计算能力，图灵发明了一个抽象装置，我们现在将其称为图灵机。以函数为例，通常来讲，如果我们理论上能用图灵机计算某个函数，我们则称该函数为“可计算”函数。围绕可计算性理论，人们做了大量研究，只要人们还有意发展使用计算机操作的自动化项目，它的重要性就不会减弱。可计算性的边界，即一台计算机计算能力的极限。

1.多维度看全

通用计算机的发展是20世纪技术领域最重要的事件之一。艾伦·图灵在理论和实践层面都为之做出了重要贡献。为了考量一台计算机的计算能力，图灵发明了一个抽象装置，我们现在将其称为图灵机。图灵机并不是一个实际存在的机器，但是我们不难在脑海中将它严谨地构造出来。

以函数为例，通常来讲，如果我们理论上能用图灵机计算某个函数，我们则称该函数为“可计算”函数。邱奇-图灵论题表明，每个能用算法来表达的函数都是可计算函数，但是这个论题还没有被证明（并且人们也不清楚怎样才算将它证明）。

围绕可计算性理论，人们做了大量研究，只要人们还有意发展使用计算机操作的自动化项目，它的重要性就不会减弱。

2.关键点梳理

经典图灵机由一条足够长的纸带和一个既能读取符号进入存储器，也能在纸带空白处写入符号的机器头组成。这个机器包含有限数量的存储槽位（也叫作“寄存器”）来存储符号，还包含一个额外的存储空间，为计算机提供指令，交代它要执行怎样的操作（“程序”）。

图灵机只是一个范例。生活中的笔记本电脑、智能手机、电视机机顶盒等，都运用了和图灵机一样的原理。

参考阅读//(www.chuimin.cn)

No. 6 哥德尔不完全性定理，第16页

No. 69 不可能的构造，第142页

No. 100 P 与NP，第204 页

右图：图灵设计的计算机“甜点”（Bombe），曾在“二战”时被用于破解纳粹的恩尼格玛密码。