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

[forecasting]

构造图灵机的理论原因是解决希尔伯特二十三问题中的两个有关：一个是第二问题，即算术公理的相容性或一致性问题，一个是第十问题，即是否存在算法判定Diophantine方程有无整数解。

前者为Godel在1931年解决，即所谓哥德尔不完备定理，不那么严格地说，就是任何一个包含Peano一阶算术的形式系统，如果是一致的，那么有命题不可证明（也不可证伪），随即可以得出，算术公理系统的一致性或者相容性不可证（第二不完备定理）。

后者是年轻的苏联数学家Yuri Matiyasevich1970年解决的，也是否定的结论，不存在算法可以判定Diophantine方程有无整数解。这工作是在Martin Davis, Hilary Putnam, and Julia Robinson基础之上解决的，所以叫DPRM定理。当然希尔伯特第十问题也是由于图灵构建图灵机而使得此问题的表述明确，因为Hilbert原问题并没有精确的算法概念。换言之，算法是在提出图灵机之后才得以精确明确的。

[forecasting]

Godel为了解决Hilbert第二问题，提出了Godel numbering，或者哥德尔编码，就是把命题和证明映射/编码为自然数，用原始递归函数（原始可计算函数）和一些初等的数论证明了他的第一不完备定理。

原始递归函数/原始可计算函数进一步扩展，就成了递归函数/可计算函数（全函数），最后就是所谓递归偏函数/可计算偏函数（偏函数），研究这个的就是数理逻辑领域之一可计算理论/递归论。大家最后发现可计算偏函数和图灵机等价，就是能一一对应起来，图灵机及其对应的递归偏函数的输入/定义域和输出/值域完全一样。

[forecasting]

当然，这是最有名的两个解决。在此之前，挪威数学家Thue就提出了半群的字问题（词问题）并提出semi-Thue system：
https://en.wikipedia.org/wiki/Axel_Thue
https://en.wikipedia.org/wiki/Semi-Thue_system

semi-Thue system和Thue system两者都等价于图灵机，也就互相等价（在可计算的意义上）

[forecasting]

半群的词问题不可判定（学过微分几何的也知道这个定理，不过记不起来是不是在微分几何著作里证明过没有了。）

美国逻辑学家/数学家Emil Post也构建了类似系统（Post system）得到了类似结果

https://en.wikipedia.org/wiki/Emil_Leon_Post

苏联数学家Andrey Andreyevich Markov(他老爹也是数学家)同时独立解决了这个问题。

https://en.wikipedia.org/wiki/Andrey_Markov_Jr.

[forecasting]

先说Markov，他和他老爹都是数学家，所以谁做了什么，我经常很糊涂，但明确的是马尔可夫正规算法是小马尔可夫做的，在莫绍揆老先生写的还是翻译的《算法论》里浏览过。

另外有限状态马尔科夫链等价于有限状态自动机。但Markov Chain是他老爹做的：
https://en.wikipedia.org/wiki/Andrey_Markov_Jr.
与FSA的关联是后来发现的，并不是他老爹的发明。

原先清华哲学系的唐稚松跟苏联这个学派或者传统有比较近的关系，但几乎没读过唐稚松的什么东西。

[forecasting]

Emil Post是个天才，可惜名气远远小于成就。他大约1921年就得到了Godel不完备定理的结果，可惜，他没及时发表。大约1940‘s又提出了Post问题，就是不可计算度/可计算度的问题，引发了可计算理论的发展。

他的Post System类似Thue system，与图灵机等价，也是一个字符串重写系统。换言之，他也提出了图灵机的等价计算模型，而且早于图灵。

https://web.archive.org/web/20100820215 ... 45-ead.xml

他一生不幸，有抑郁躁狂双相精神病，因为电击治疗引发心脏病而去世。生前驾车把胳膊放在车窗外被其他车拿掉了。

[forecasting]

另外一个等价于图灵机的就是λ演算，归于Alonzo Church名下，就是图灵读博士的导师：
https://en.wikipedia.org/wiki/Alonzo_Church

当然λ演算也可以证明等价于图灵机。

[forecasting]

最后一个登场的是Noam Chomsky

https://en.wikipedia.org/wiki/Noam_Chomsky

https://chomsky.info/

他是一个语言学家，综合美国描写语言学派的理论结果和Post system（不确定是从Post system还是从Thue System而来）提出Chomsky Hierarchy，学形式语言和编译原理的都学过他的四层语言和文法/语法，正则语法/正则语言，上下文无关语法/上下文无关语言，上下文有关语法/上下文有关语言，递归可枚举语法/递归可枚举语言，分别对应于FSA，PDA, LBA, TM, 除FSA，TM而外，PDA，LBA都是不确定的才对应于上下文无关语法/上下文无关语言，上下文有关语法/上下文有关语言，LBA的问题到现在还没有解决。

对了，前段时间Hinton和Chomsky还为语言和智能问题吵嘴。

他提出其层级时，人工智能正迎来第一次热潮，大师云集达特茅茨召开第一次AI会议（Dartmouth Summer Research Project on Artificial Intelligence ）
https://en.wikipedia.org/wiki/Dartmouth_workshop

[forecasting]

说到这里，一共有递归/可计算偏函数，Turing Machine，λ演算， Post System（Thue System），Chomsky grammar/Chomsky Hierarchy，Markov Algorithm，或者把Godel证明不完备定理的结果作为一种（逻辑系统）这些计算/证明/变换/重写的模型。

人们通过不同途径，从不同角度想弄清或者捕捉计算/递归的概念，到最后找到的几个计算模型都是等价的。于是就有了Church-Turing Thesis，这是个论题，是摸索到的感悟，加上证据，不是证明，也证明不了。

[forecasting]

但是这些模型/系统等价，是可以证明的。所以，人能计算的，机器也能计算，只能是这个样子，反之，机器能计算的，人也能计算。就出了C-T Thesis.

单单就可计算函数而言，大家有了一些很有意思的结论，这些结论可以对应到图灵机上，于是通用图灵机，操作系统，储存程序的计算机（Von Neuman 结构的计算机）就有了坚实的理论基础。

那些倒腾形式语言的就得到一些定理和技术，就有固有歧义问题不可判定，LEX和YACC这样理论和技术结合得十分完美的东西，也给编程语言指明了方向 Thue, Post, Chomsky和可计算理论，自动机理论的先驱们指明的。

[forecasting]

好了，现在可以一边写TM，一边说Von Neuman结构的计算机了（别忘了简称VNC）。

有鉴于目前Artificial Intelligenc 热翻天，后面半八卦半正经地顺便说一点图灵在人工智能上的成就和生物学上的成就，后者大概没几个人注意。

[forecasting]

隔壁讨论LLM是不是做出了证明。
证明是什么？证明就是计算，计算就是证明，所以Godel关于证明长度的论文也是关于计算复杂性的论文。
我们也严格地定义了什么是证明。对照定义和LLM等等，这些模型的确输出了证明，但是未必正确。跟人的证明一样吗？人的证明也有错，也经常搜索匹配。
那么我们觉得这些模型跟人的证明到底在哪里不同？

其实就是人能发明或者发现证明，而这些模型则不可能。

[forecasting]

另有一个量子计算机/图灵机。这个在物理上很难或者无法实现，但不妨碍它成为一个理论模型。

理论模型的用处是什么？一个显而易见的用处就是给计算复杂性分层分类。不大为人熟悉的或强或弱的计算模型有很多，目的都是为了解决理论问题，并没有要实现。例如带Oracle的图灵机超过了图灵机的计算能力，是为了研究不可计算或者判定的问题（后来扩展到计算复杂性问题）

AM模型，IP模型等等都是为了解决复杂性问题提出来的，量子图灵机也可以如此用，尽管它几乎肯定没法实现。

[Vogel]

码字辛苦了！有时间来读！看看能不能抓bug %$#@

[forecasting]

码字辛苦了！有时间来读！看看能不能抓bug %$#@

好，严格和易懂之间难以平衡，也不容把严格的东西变成易懂的，容易写得随意而出问题。

[Vogel]

先问下，是你写得嘛，
有时间看哈。。

[eflame99]

先说几个非核心问题：Von Neumann结构的计算机是弱的通用图灵机。

其实并不是。如果是的话，请问怎样在图灵机上实现病毒。

[forecasting]

先问下，是你写得嘛，
有时间看哈。。

为啥问这个问题？