图灵机详解
1936 年,在电子计算机出现之前,24 岁的数学家艾伦·图灵追问:一项计算是“机械的”究竟意味着什么?他的答案是一台想象中的机器,简单到几乎不能再简单:它按照一张固定的规则表,在纸带上一次一格地读写符号。结果这台机器定义了计算本身,并且表明有些问题是任何计算机都永远无法回答的。
图灵的问题
1928 年,大卫·希尔伯特提出:是否存在一种机械程序,能对数学中的每一个命题判定它能否被证明?这就是判定问题(Entscheidungsproblem)。要回答它,就必须有人准确说明什么是机械程序。在 1936 年的论文《论可计算数》(On Computable Numbers)中,图灵设想一位用纸笔工作的计算员,并把这项工作拆解成最小的步骤:看一个符号,改变它,移到相邻的符号,并记住一点自己正在做什么。结果就是图灵机。
机器
图灵机有一条分成许多格的纸带,向两个方向无限延伸,每格存放一个符号,通常是空白。一个读写头停在某一格上,机器处于有限多个状态之一。规则表对每个状态和读写头可能读到的每个符号,给出要写的符号、移动的方向和下一状态。机器每一步应用一条规则。当它进入停机状态时就停止,纸带上留下的内容就是它的答案。
作为规则表的程序
每张规则表都是一个程序。要给二进制数加 1,机器先走到数的右端,然后向左移动,把 1 变成 0,直到遇到一个 0 或空白,再把它变成 1。要检查一个单词是否为回文,它擦掉第一个符号,用状态记住它,跑到另一端检查最后一个符号是否相同,然后重复。长的程序,例如做乘法或排序的程序,也是由同样几类规则搭建而成的。
通用机器
图灵最重要的想法是:规则表本身也可以写在纸带上。通用图灵机读取任意另一台机器的描述及其输入,然后一步一步地模仿它。因此一台固定的机器就能运行所有程序:这正是每一台存储程序计算机背后的原理,在那里软件只是内存中的数据。任何能模仿通用图灵机的系统都称为图灵完备,包括每一种编程语言、康威的生命游戏和元胞自动机规则 110。
丘奇–图灵论题
同一年,阿隆佐·丘奇用他的 λ 演算描述了计算,结果这两种定义能计算的函数完全相同。此后的每一种模型,从寄存器机到现代处理器,也都如此。丘奇–图灵论题指出,任何能通过逐步程序计算的东西,都能用图灵机计算。它无法被证明,因为“逐步程序”是一个非形式化的概念,但至今从未发现反例。
停机问题
图灵接着证明,有些问题没有机械的答案。假设有一台机器能对每个程序和输入判定该程序最终是否停机。构造一个新程序,让它就自己去询问这个判定器,然后反其道而行:如果被告知会停机,它就永远循环;如果被告知会循环,它就停机。两种回答都是错的,所以这个判定器不可能存在。停机问题是不可判定的,判定问题也随之不可判定:没有任何算法能解决所有数学问题。
忙碌海狸
1962 年,蒂博尔·拉多把停机问题变成了一个游戏:在所有具有 n 个状态、使用符号 0 和 1、从空白纸带启动后会停机的机器中,哪一台写下的 1 最多,这样的机器最多能走多少步?这些数,即忙碌海狸数,增长得比任何可计算函数都快,因为一旦有办法计算它们,就能解决停机问题。已知的值是:两个、三个和四个状态分别为 6、21 和 107 步;对于五个状态,海纳·马克森(Heiner Marxen)和于尔根·邦特罗克(Jürgen Buntrock)找到的冠军要走 47,176,870 步,这个值在 2024 年由在线协作项目 bbchallenge 以经计算机验证的证明确立。对于六个状态,已知有些机器运行的步数多到无法用普通记数法写出来。
动手探索
打开图灵机模拟器,运行八个现成程序或编写你自己的程序。一步步跟随读写头,看看哪条规则被触发;观察永不停机的计数器,检查回文,再运行忙碌海狸:四状态冠军的 107 步正好放进图示,五状态冠军的 4700 万步在最快速度下只需几秒钟。
常见问题
图灵机真的被造出来过吗?
没有按图灵描述的样子造出来,因为它的纸带是无限长的;但这个想法提出后不久,真正的存储程序计算机就问世了,图灵本人在第二次世界大战后也参与了设计。此后,爱好者们用木头、乐高,甚至在生命游戏中造出了可以运行的模型,它们都只有有限长的纸带,而这对任何会结束的计算都已足够。
三个状态的步数 14 和 21 有什么区别?
忙碌海狸问题有两个:写下最多的 1,以及走最多的步数。对于三个状态,模拟器中的机器在 14 步内写下最多的六个 1,而另一台三状态机器走了最多的 21 步,却只留下五个 1。对于两个、四个和五个状态,同一台机器在两方面都是冠军。
图灵完备意味着强大吗?
它意味着只要时间和内存足够,就能计算任何可计算的东西,但这并不说明速度。图灵机做简单的算术也需要很多步,而有些系统几乎是意外地成为图灵完备的,例如纸牌游戏、电子表格公式和 Minecraft 的红石。
为什么计算机不能直接运行一个程序,看看它会不会停机?
如果程序会停机,运行它就能表明这一点;但如果它还没停下来,你就无法判断它是永远不会停,还是只是需要更多时间。图灵的证明表明,没有任何更聪明的方法适用于每一个程序,尽管对许多具体程序来说,这个问题是可以回答的。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开图灵机模拟器