图灵机（Turing Machine）和Von Neumann结构的计算机（一）

[forecasting]

先占位，兴致来了再写。
先上定义，讨厌的定义，可以浏览一下或者跳过，等把相关的内容都说清楚了再回来看。第三个是个动态图示的材料，直观多了：
https://plato.stanford.edu/entries/turing-machine/

https://en.wikipedia.org/wiki/Turing_ma ... ne%20model.

动态图示，直观
https://turingmachine.io/

[hci]

欢迎

[forecasting]

先占位，兴致来了再写。

先说几个非核心问题：Von Neumann结构的计算机是弱的通用图灵机。说它弱，是因为其存储不是无限的，而通用图灵机的带子是无限长的。图灵机未必是通用的，比如交通信号灯，电梯控制器就是很特殊的图灵机，通用图灵机可以模拟（simulate）任何图灵机，所以Von Neumann（往后简称VNC）计算机运行任何一道程序比如word就变成了另一台图灵机，往往是一台特殊的图灵机，就是那道程序使得VNC模拟一台特殊图灵机。为什么说往往，而不说一定？这就是第二个问题。

通用图灵机（Universal Turing Machine，UTM）有一种很特别的程序，运行这道程序，它还是模拟UTM，不过界面什么的变了，不同的UTM理论上有无限台，它们彼此都能互相模拟，最简单的模拟方法就是运行那种特别的程序去模拟各种其他的，这特别的程序就叫操作系统，换言之，操作系统（OS）也可以有无数个，看你喜欢了。一般大家都喜欢简洁高效友好的。但是VNC运行OS也仍然是一台弱的通用图灵机，因为它没法改变存储有限的事实。

[forecasting]

说说发明图灵机实现VCN的现实和理论原因。先写先发再检查

算个题目，2371*18321=? 看看需要哪些东西，怎么做才能算出来？

第一，你得有张纸，或者一块黑板，whatever，能写/记录的地方。我们把它变成长长的纸带子，无限长，两边延申，免得不够用

第二，得有一支笔，或者一块粉笔，用大地做记录，得用一个树枝或者小棍子，whatever。我们用写头来表示这支笔，包括上不用时擦掉数字的黑板擦的功能。

第三，得有一双眼睛去看着黑板/纸张上的数字。我们把眼睛变成读头，并且把第二那个写头和读头，合并。看看你做题时的动作，不停地左右上下移动手和眼睛，读写。左右上下移动局限于纸带子，就成了左右移动。换言之，读写头可以左右移动，读写，当然也可以不写。
第四，得用脑子背着乘法口诀指挥手拿着粉笔涂涂写写。那个背着口诀指挥手和眼睛（左右移动读写）的器官，叫大脑，我们改叫它控制器/控制单元/control unit。这大脑背口诀指挥手眼移动读写，有时候用乘法口诀，有时候用加法，有时候又比较数字大小（记得怎么进位吗？进位之前得比较大小）。为节省纸张或者黑板，得擦掉那些已经不用的数字和符号。也就是说要自己碰到什么，决定用什么口诀（规则），往左往右移动，写下什么（稍后详细分析算2371*18321=？的过程，看大脑怎么变换状态依照口诀计算的。现在先不详细说。）。

第五，手眼读写的是数字，叫符号，显然符号是有限个，就像人用的数字是有限个，十进制就是0---9，十个符号。汉字多，也不过几万个，大约四万左右。2371*18321=这个算式必须把各个符号分开，所以带子要变成无数个格子，一个格子装/写一个符号或者不写符号（空格）

第六，那个乘法口诀，是有限个的算法口诀，还记得九九乘法表吗？小学就要背诵的，或者加法口诀，很简单，但刚开始学的时候不会，得先学数数，然后做加法最简单的口诀是，先数第一个数，再在第一个数后面接着数第二个数，就得到加法。

于是，计算，得有1，布满了格子的无限长的纸带子，2，读写头，3，控制单元/有限状态自动机，4，有限个符号，5，口诀，6，读写头得能左右移动，读或者写。7，控制器/状态自动机的状态和规则。

[forecasting]

第四，得用脑子背着乘法口诀指挥手拿着粉笔涂涂写写。那个背着口诀指挥手和眼睛（左右移动读写）的器官，叫大脑，我们改叫它控制器/控制单元/control unit。这大脑背口诀指挥手眼移动读写，有时候用乘法口诀，有时候用加法，有时候又比较数字大小（记得怎么进位吗？进位之前得比较大小）。为节省纸张或者黑板，得擦掉那些已经不用的数字和符号。也就是说要自己碰到什么，决定用什么口诀（规则），往左往右移动，写下什么（稍后详细分析算2371*18321=？的过程，看大脑怎么变换状态依照口诀计算的。现在先不详细说。）。

大脑一开始先读到符号，就得决定是什么符号要做什么，比如读到乘法，就得从读一般符号（状态与动作）转而准备背乘法口诀/或者查乘法口诀（状态与动作），一般符号就要决定继续读下去还是怎么的（状态与动作）。为简化这复杂的过程，给大脑/控制器/有限状态自动机指定一些状态而且状态之间按照读到的符号而转换，并且每个状态碰到什么符号就对应读写头写下什么符号，（转到什么状态），左移/右移。

用q_i表示自动机当前的状态 , s_i 表示读到的当前符号，x_j表示在当前位置写下的符号，q_j表示将要转移到的状态，L/R表示向左或者向右移动。

那么就是函数 f （delta）把 q_i, s_i 映射到 q_j， x_j，L/R。 也就是把两元组映射到三元组。不过这函数未必处处有定义，叫偏函数（如果碰到一个状态和符号的组合，f没有定义会怎样？），如果处处有定义，就叫全函数。机器一开始的状态是q_0,停机结束的状态一般未必是唯一一个，用一个结束状态的集合表示就是F。这个函数把状态和符号映射到状态，符号，左/右，也可以在有限的表上列出来，看那三个连接。这个状态和符号对应到状态，符号，左/右有限的表格有有限个项，也就是有限个规则。

然后回头去看看图灵机的定义，看是不是能对应起来。所以Turing Machine其实就是模拟人的计算。如果你还有疑惑，见过熟练打算盘的人没有？那算盘是纸带子（有限长），眼睛和手是读写头，脑袋是自动机，转换状态，背口诀指挥眼睛移动，指挥手拨弄算盘珠（写下符号）。有一些老会计算盘打得特别快，比我们用计算器算快多了。

[forecasting]

下面的文字当故事看，看不懂的术语先跳过去。
英国数学家艾伦·图灵（Alan Turing）是剑桥大学国王学院（King’s College, Cambridge）的学生，于1934年毕业获得数学学士学位。图灵在1935年被选为国王学院的研究员，不久后，1936年提出图灵机（Turing Machine），在他的经典论文《On Computable Numbers, with an Application to the Entscheidungsproblem》（《论可计算数及其在判定问题中的应用》）中，定义了或抽象构建了这种抽象计算模型。

论文发表于1936年《伦敦数学会会刊》（Proceedings of the London Mathematical Society），并于1937年正式出版。

图灵在这篇论文中提出了图灵机作为一种理想化的机器，来描述算法的基本概念和计算的本质。论文的目的是解决德国数学家大卫·希尔伯特（David Hilbert）在1928年提出的判定问题（Entscheidungsproblem），即是否存在一个算法能够判定任意数学命题的真伪。他证明了存在一些数学问题无法通过算法解答（不可计算）。他的工作奠定了计算理论的基础，图灵机也成为现代计算机科学的核心概念之一，用于定义算法可计算性的标准。

[forecasting]

仍然是故事，看不懂的术语就先跳过去，相关概念将来会随文解释。

1936年到1938年前往美国普林斯顿大学（Princeton University）跟随阿隆佐·邱奇（Alonzo Church）攻读博士学位，1938年获得博士学位。

图灵在普林斯顿的研究主要集中在可计算性理论和逻辑，尤其是lambda演算和递归函数理论等领域。邱奇在可计算性理论上有着重要贡献，是“邱奇-图灵论题”（Church-Turing Thesis）的另一位提出者，这一论题为数学中的计算能力和算法能力提供了理论基础。

邱奇-图灵论题（Church-Turing Thesis）是个论题，并不是一个定理，没有证明，也不可能证明。它说的是，人能够计算的也是图灵机能够计算的，图灵机能够计算的也是人能够计算的。换言之，人的计算能力和图灵机的计算能力一样，如果不考虑时间长短和花费的纸张/带子。

[forecasting]

仍然是故事，有术语读不懂就跳过去，

回到英国不久，1939年9月1日，当时纳粹德国入侵波兰。这次入侵导致了英国和法国在9月3日对德国宣战，正式拉开了欧洲战场的序幕。

大约是在1939年第二次世界大战爆发之际，艾伦·图灵（Alan Turing）开始破译德军的恩尼格玛密码的工作。他受雇于英国政府密码学校（Government Code and Cypher School, GC&CS），并被派往英国布莱切利庄园（Bletchley Park），这是英国秘密的密码破译中心。

在布莱切利庄园，图灵与其他数学家和密码学家一起致力于破解德军的加密通信，尤其是恩尼格玛（Enigma）密码系统。图灵开发了名为“Bombe”的机械装置，用来测试可能的加密配置，从而加速了恩尼格玛密码的破译。尽管破译工作早在战争前就开始，但图灵的加入和 Bombe 机器的发明显著提升了破译的速度和成功率。

图灵和布莱切利庄园团队的工作对盟军的战争胜利起到了至关重要的作用，尤其是在海战中对付德国的 U 型潜艇。

关于这段故事，有一本英国记者写的超级机密。

有趣的是，computer原来指图灵手下的那些做手工计算的计算员，她们基本都是女士。谢天谢地，图灵是个同性恋，不然在布莱切利庄园（Bletchley Park）他该眠花宿柳，女士们也会不死不休地爱上他。

[forecasting]

仍然是关于图灵的故事。

图灵在1952年因同性恋行为被定罪，这在当时的英国属于非法行为。他被判处化学阉割以代替监禁，这对他的身体和心理健康造成了严重影响。尽管他在数学、计算机科学和密码学领域做出了卓越贡献，但最终他因当时的法律与社会偏见而承受了极大痛苦。

阿伦·图灵在1954年6月7日被发现死于英格兰威姆斯洛的家中，床边有一个咬了一口的苹果。官方验尸报告确认他死于氰化物中毒。虽然有人推测他的死可能是意外，但验尸官的结论更倾向于自杀。这与图灵当时的境遇和压力有关，尤其是他因性取向被起诉所带来的负面影响。

当时以及稍前后的英国相比现在保守得多，D. H. Lawrence因其小说如儿子与母亲，恋爱中的妇女，虹，查特莱夫人的情人等而遭遇排斥乃至诉讼。人们不理解也无法接受那些大胆的性爱和情感描写，甚至劳伦斯的母亲也指责劳伦斯，当然他的小说成了禁书。

2009年，英国政府正式为对图灵的非人道待遇道歉，2013年他被追授了皇家特赦。这一赦免引发了公众对其他因同性恋行为遭到不公正对待的受害者的关注。如今，图灵的成就被全球认可，他的遗产在科学领域发挥巨大影响，改变了人们的生活，使得人们进入了信息时代。2012年英国举办图灵百年活动，以纪念悼念这位富有创新精神，有巨大成就又过早离世的科学家。

他的成就不止上文提到的这些，后面还会提及其他的成就，尤其计算生物、AI的测试标准等等，一直影响至今。

[TheMatrix]

大脑一开始先读到符号，就得决定是什么符号要做什么，比如读到乘法，就得从读一般符号（状态与动作）转而准备背乘法口诀/或者查乘法口诀（状态与动作），一般符号就要决定继续读下去还是怎么的（状态与动作）。为简化这复杂的过程，给大脑/控制器/有限状态自动机指定一些状态而且状态之间按照读到的符号而转换，并且每个状态碰到什么符号就对应读写头写下什么符号，（转到什么状态），左移/右移。

用q_i表示自动机当前的状态 , s_i 表示读到的当前符号，x_j表示在当前位置写下的符号，q_j表示将要转移到的状态，L/R表示向左或者向右移动。

那么就是函数 f （delta）把 q_i, s_i 映射到 q_j， x_j，L/R。 也就是把两元组映射到三元组。不过这函数未必处处有定义，叫偏函数（如果碰到一个状态和符号的组合，f没有定义会怎样？），如果处处有定义，就叫全函数。机器一开始的状态是q_0,停机结束的状态一般未必是唯一一个，用一个结束状态的集合表示就是F。这个函数把状态和符号映射到状态，符号，左/右，也可以在有限的表上列出来，看那三个连接。这个状态和符号对应到状态，符号，左/右有限的表格有有限个项，也就是有限个规则。

然后回头去看看图灵机的定义，看是不是能对应起来。所以Turing Machine其实就是模拟人的计算。如果你还有疑惑，见过熟练打算盘的人没有？那算盘是纸带子（有限长），眼睛和手是读写头，脑袋是自动机，转换状态，背口诀指挥眼睛移动，指挥手拨弄算盘珠（写下符号）。有一些老会计算盘打得特别快，比我们用计算器算快多了。

我等着看 Turing machine -----> Von Neumann 结构。

[forecasting]

我等着看 Turing machine -----> Von Neumann 结构。

换个图灵机（Turing Machine）和Von Neumann结构的计算机（ 二 ）写，Turing Machine还没罗嗦完呢。

[forecasting]

再回到严肃的话题，不过我们不证明这些结论或定理，要看这些结论或定理的证明，可以去读Hopcraft Ullman等人写的Introduction to Automata， computation and formal language。记得Stanford的网站上还有他们教学的slides。

可以改改图灵机，看看能否增强其计算能力，加读写带子，加状态等等，不考虑时间和所用带上格子，计算能力没增加。但如果适当设计状态和符号，会得到一种图灵机，这种图灵机读取其他图灵机的编码就可以模拟任意其他图灵机。这种图灵机叫通用图灵机（Universal Turing Machine，UTM）。这个定理或结论可以去看Introduction to Automata， computation and formal language，可以看这个链接： https://en.wikipedia.org/wiki/UTM_theorem 不耐烦就先跳过去

[forecasting]

如果限制一下带子长度呢？那就是弱图灵机，计算能力赶不上图灵机，因为图灵机的带子无限长。

如果限制读写头为只读不能写，读头移动从左到右，那么就成了有限状态自动机，Finite State automaton，FSA。当然可以修改一下有输出，但计算能力没变，有输出的叫转录机。

增强一下FSA：如果又带有一个先进后出的下推栈（是一种特殊的带子，带子上的读写头既能读又能写），就成了下推栈自动机。pushdown automaton，PDA

再增强一下，如果限制带子长度为输入符号串的线性函数的长度，就是输入符号串长度倍数，读写头有读写功能，左右都可以移动，去掉下推栈，那么计算能力大大受限，叫 Linear bounded automaton，LBA。

再扩展就是图灵机，已经说过了。

从上到下，计算能力逐步增强，当然还可以有其他类型，可以在这个层次上。

[forecasting]

增加带子和读写头不会增强TM的计算能力，但能方便使用。所以键盘（TM只读的带子），显示器（TM只写的带子），硬盘（读写 ）内存（读写 ）缓存（读写，但是内嵌到cpu里去了，搞得cpu成了一个弱的通用图灵机），网卡。

总之所有的外围设备都是带子，因此在UNIX里面都作为文件来管理，unix的两位作者肯·汤普森（Ken Thompson）和丹尼斯·里奇（Dennis Ritchie）看来深懂Turing Machine。对了，我们说OS总是把通用图灵机（UTM）变成另一台UTM，不过方便使用，效率高而已。

[forecasting]

TM每算一步，都要读带子的一个格子，所以一台TM或者一道程序读了多少次带子格子，就是计算了多少步。这些计算步的量就叫时间复杂性。计算时用了多少格子就叫空间复杂度。要知道一个格子可以多次读写，但空间复杂度没增加，时间复杂度却增加了。所以这是两个衡量计算复杂性的指标。两者的关系就去看关于计算复杂性的数好了，书名改天查了发上来，记得不准确了。

计算复杂度里最有名的问题就是NP=P？ 王浩的学生Cook提出来的，他是图灵奖得主。其中NP是不确定（Non-deterministic）Turing Machine Polynomial时间内所能计算的问题。那什么是不确定图灵机? 可以把NTM想象成它每完成一步都能猜测下一步走哪个路径最有效，就是能猜测最有效的计算路径的Turing Machine。数学上就是那个转移函数f（delta）把 q_i, s_i 映射到 一个由q_j， x_j，L/R组成的集合，而此集合只含一个元素的情况就叫Deterministic Turing Machine，不然就叫Non-deterministic Turing Machine。换言之，NTM每一步都同时计算好几个计算路径，并且知道或者能猜中那条最有效率而能成功计算的计算步。显然其计算复杂度要一般要小于Deterministic Turing Machine。

NP=P？就是说，NTM在多项式计算复杂度内计算的问题是不是DTM能在多项式计算复杂度内计算的问题？大多数计算机科学家都猜测等式不成立，不过现在也没啥进展，没法证明。

计算复杂度在Godel那里就已经提出来了，但Godel说的是证明长度，其实等价于计算复杂性。

当然计算复杂度还有很多类或者层，从线性到多项式到指数到双指数，等等，也有比线性复杂度更简单的，也有比双指数复杂的。具体去看计算复杂度的输了，改天发个图上来。

或许有人会问，提高计算机的速度不就解决把计算复杂度降下来了吗？Blum证明计算复杂度跟图灵机计算速度（n步/秒）没关系，它衡量的是计算步，或者使用的带上的格子数量，无论你设计多快的计算机，都少不了走那些计算步，用那些格子。

[forecasting]

上述的计算复杂度只牵涉最后TM回答（输出）是/否（1或0）的问题，也就是判定问题。同属计算复杂性而与上述的稍有不同的是，如果计算具体问题输出非判断问题的字符串（数字），就成了FP，FNP类计算复杂性。看下面的链接：

https://en.wikipedia.org/wiki/FP_(complexity)

https://en.wikipedia.org/wiki/FNP_(complexity)

一般人说的计算复杂度都是FP，FNP等，不是NP，P等。

有兴趣可以讨论，这些定义有一些细微，得稍微小心才能区分开来。

[forecasting]

另外一种截然不同的复杂度是所谓Kolmogorov Complexity，就是给定描述某问题的字符串，能输出此字符串的最短程序的长度。这是不能计算的，是一个非常深刻的领域。

Shannon最先想寻找通用图灵机的最少状态Q_min和最少符号（带符号）S_min，发现两者的乘积有某种不变量的意思，后来Chaitin提出并解决了一系列问题，其他两位大家也相继发现并研究这个问题，发展为一个学科。顺便说一句，Shannon发现UTM最少的状态Q_min为2，一个状态无法设计出通用图灵机。

[hahan]

为啥图灵机这个非常awkward 的模型还没被摒弃？

[forecasting]

为啥图灵机这个非常awkward 的模型还没被摒弃？

也有大量的其他模型，为方便可以构造。问题是，构造新的模型并不容易。如果你能构造一计算模型还能表述/证明不平凡的定理，那肯定会名利双收。

因为习惯和传统，大量定理是用它表述和证明的，更重要的是因为简单，其实这个最简单了，一些变种表述定理或者证明定理不比它强。

[forecasting]

物体所能承载的最大信息，也就是信息上界，跟其面积成正比，也就是跟其质量平方成正比。信息/熵原来跟质量分不开！所以计算和计算复杂性（空间复杂度）也受限于物理定律。因此怀疑Church-Turing thesis可以从物理里面推导出来。