计算机的原理是图灵机吗，那图灵机的数学原理是什么？

[James369]

如果说计算机是图灵机演变的，那么图灵机的设计理念是什么？

从百科查到：
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

初看好像也没什么，但这样的图灵模型一定是经过理论证明过可行的，那么它的理论依据是什么？
为什么这么搞。它解决的是什么问题，它有什么局限？

[tadebao]

0 和１呀

[James369]

@tadebao 显然不是，应该是跟递归有关

[crclz]

计算的的原理是《 CSAPP 》、《汇编语言》、《操作系统》，建议没读过的去读一读

[muooOOO]

数学原理应该是基于布尔代数吧，

[mengzhexin]

研究生课程有请，可计算性和计算复杂性

[minami]

数学原理是一阶逻辑——“图灵机是有这样一种性质的数学概念：所有一阶逻辑命题真伪性的判定问题，都可以转化为判定一个图灵机是否“停机”的问题。进而图灵又证明了不存在一个一般的判定图灵机是否停机的算法，从而否决了希尔伯特寻找一种通用算法进行命题真伪判断的梦想”。
ps：建议看一遍《计算的极限》系列文章

[James369]

@mengzhexin 有机会还是要考个研究生，还是有点东西

[user8341]

图灵机不是唯一的计算模型，还有 lambda 演算等等，然而所有的计算模型都能证明与图灵机等价，或者计算能力不超过图灵机。图灵机是这些计算模型里面最直观的最简单的。大家普遍相信图灵机不可计算的，就是不可计算的定义。

图灵机用一种直观的方式定义了什么是计算。用这个模型可以得出计算的极限——可计算性。什么问题是可计算的，什么问题是不可计算的。图灵机奠定了现代计算机的理论基础。

但是真正造出计算机的是冯诺依曼。科学界更推崇概念的推早提出者，所以大家更推崇图灵的贡献。图灵机与计算机的相似之处还有它也用两个符号也存储程序。

[forgottencoast]

@James369 研究生主要靠自学，所以你现在就可以自学了，没必要等到考上研究生。

[seraphv3]

它的理论依据是什么？
----------------------
有一本翻译的书《图灵的秘密》解读了图灵提出图灵机的那篇论文《论可计算数及其在判定问题上的应用》，网上有扫描电子版。图灵的论文构造了一种“普适图灵机”（ Universal Turing Machine ），可以把任何图灵机编码成程序存储在纸带上，由普适图灵机来执行这个程序。我以前翻译过图灵的那篇论文，仔细读过一遍。图灵提出图灵机的目的是描述“可计算的过程”，解决希尔伯特的关于逻辑形式体系的“判定问题”。最后判定问题转化为了图灵机的停机问题，即用一个程序判断任何图灵机是否会最终执行结束。最终的结论是，停机问题是无解的。

[hahastudio]

这就要上可计算性理论了

[Maboroshii]

难道不是与非门？

[linux40]

递归可枚举类

[luoqeng]

[希尔伯特第十问题要求寻找判定丢番图方程是否有解的算法。]( https://www.changhai.org/articles/science/mathematics/hilbert10/1.php)

[imilano]

@minami 顺着关键词搜索，捡到宝了，感谢😆

[misaka19000]

看我以前写的文章

https://www.nosuchfield.com/2017/01/05/Computation-of-computers/

[no1xsyzy]

图灵模型现在的现实意义主要就是为了方便地证明某一语言是 “万能的”，即 “能够进行任何可进行的计算”
换句话说，“图灵完备的”
因为图灵机比较容易实现，人们轻易地就能构造性地证明某一语言能够实现一个图灵机的模拟器。

——

至于原理是图灵机的来源。
实质上（大部分机器的）原理是冯诺依曼架构。
主要是冯是个图灵迷弟，他亲自上场吹图灵。

[northisland]

相比图灵，冯诺伊曼是真大佬。

我知道的八卦是：

图灵是战前乘末等舱跑到美国的打工人，
给终身教授冯诺依曼的小弟做博士。

冯诺依曼老哥是普林斯顿的大佬，一年换一辆全新凯迪拉克

见《自由的老虎 · 面对面的办公室》。

[zero469]

建议阅读《计算理论导论》

[Mark24]

这是 hexo 的啥主题呀

[no1xsyzy]

@northisland 去 Princeton 是带学生…… 不是打工人
Church 是 von Neumann 的小弟么，这倒是没发现……
Mentor 这个词英文中的含义复杂得多，没那么明显的身份差异。
也是东西方文化差异的一环吧

至于 Turing 在计算机原理基础方面名声主要是 von Neumann 吹出来的…… 大佬背书
真正作为核心贡献者还是 Enigma 破译

[luomu24]

可以去上上《计算理论》这门课，有讲图灵机、DFA 、NFA 、NP 问题。

[northisland]

https://lingeros-tot.github.io/2019/03/05/%E5%9B%BE%E7%81%B5%E6%9C%BA%E6%A8%A1%E5%9E%8B%E4%B8%8E%E5%8F%AF%E8%AE%A1%E7%AE%97%E6%80%A7/
我看得是这个，感觉图灵机很烧脑，不是电子计算机，是机械计算机。

被 ibm 公司 Hollerith 的 1900 年以前的打孔卡计算机产品吊打。

机械计算机，历史相当久远，手摇的加法器，乘法器，积分器什么的，是 16xx 年左右欧洲的科技。


我还是吹冯诺依曼

[ericgui]

Theory of Computation

先学学这个课程

[northisland]

计算机比只能跑一种算法

[northisland]

图灵机假设足够强大，也只是只能执行一种程序的多纸带机械。
换程序就换纸带。。。想起任天堂卡带偷笑了


跟现代的机电计算机差远了。。。冯诺依曼一年换一辆凯迪拉克最高配，图灵开二手福特，是有原因的。🤣

[northisland]

不晓得为什么国内有这么多图灵吹。。。难道是这个不幸的老哥吃过资本主义铁拳？

[aguesuka]

图灵机是计算模型。
计算机从一开始就是冯诺依曼结构(当然计算能力等价于图灵机)如果你对从门电路造计算机感兴趣就去看冯诺依曼结。
如果对可计算领域感兴趣就去看 lambda 运算和它的可判定性问题，相比图灵机，lambda 运算同样是图灵完备的但是规则更少更优美。

[northisland]

我认为没什么数学原理。。。


把图灵机的[状态孔]换成[cpu 指令]，把[转移函数]换成[cpu 指令电路]，这就是现在大家手上的计算机。
而这一套，貌似冯诺伊曼的贡献更大。

伟人的灵魂和想法，在电路中陪伴着世界。

[kidding]

看了下图灵机的定义，感觉就是个 FSA （有限状态机）的样子... 正好最近在学 Introduction to the Theory of Computation

[ResidualSoils]

@minami 好难找到这篇文章

[no1xsyzy]

@northisland 你在说什么？
图灵机是数学模型，不是任何种类的计算机

不能换纸带，只有一根不可替换的、无限长的纸带。
你看到多根纸带的、纸带上能写 0 1 以外的东西的、能替换纸带的，都不是图灵机。

跟资本主义铁拳又有什么关系？
V2 不客气地说大都是小资和中产。
国内能听说过图灵的，要么是电影，要么是学计算机还能学计算机相关历史的 —— 也大多是小资和中产。

至于冯架构，冯他本人亲自吹图灵，在别人采访他的时候他着重强调了图灵的名字。
我就跟你说，冯就是第一图灵吹，图灵的名气除了 Enigma 就是冯吹出来的。
你讽刺图灵吹先讽刺冯行不行？

[no1xsyzy]

@kidding FSA 和 FSM 是一个东西吧……
对图灵机进行了实用主义的劣化，但确实非常实用，导致正则表达式能诞生了

[northisland]

@no1xsyzy 这图灵机数学模型出来半世纪前，
ibm 创始人就发明 30x10 的打孔纸，还有一起工作的机械计算机，帮助美国进行人口普查清算了。

个人 diss 一下所谓图灵机的表述。因为东西，向前比不够 ibm 创始人酷，向后比也不够冯诺伊曼体系酷。

我中午吃饭也是补课出来的，貌似图灵机有 n 根纸带，一根弄输入，一根弄输出，剩下 n-2 根搞内部逻辑。

[easing]

@northisland #34 大哥，图灵机是计算模型，不是机器。。是为了研究可计算理论而创建的一种模型，用来判定到底什么是可计算的，什么是不可计算的，也就是研究计算的边界问题。跟实际的机器毛关系都没有。要说关系，那也要说元图灵机以及后来优化的各种寄存器机器模型。

[no1xsyzy]

@northisland 不谈效率，提供恰当的接口约定，图灵机能跑毁灭战士（ Ray cast ），也能跑神经网络
不谈效率，你 IBM 机械计算机行吗？

[northisland]

@easing
楼主问的是现代的计算机，和图灵机有什么关系。。。 看你的回答，我只能说没啥关系了。。。


@no1xsyzy
确实只有一个纸带，数学模型只考虑输出，不考虑怎么内部实现和输出，2333

[northisland]

@no1xsyzy 引发了我的兴趣，下班再摸一下图灵大神

[no1xsyzy]

@northisland 说到底，图灵机不是拿来用的，是拿来使它 “用不了” 的。
通过这一个非常简单的数学模型，证明了 “存在证明不了真假的命题”，破缺了逻辑系统的完备性。
做到相同工作的还有 Lambda Calculus，基本前后，采用两种截然不同的做法做到了完全相同的事情。
而再上升是哥德尔不完备定理。

对了，语文建议重修下，你的文字，形散神也散。

[no1xsyzy]

@northisland 确实没啥关系，我 #17 说了，现实意义就是 “轻易地就能构造性地证明某一语言能够实现一个图灵机的模拟器。”
比实现 lambda calculus 或者实现元解释器方便多了……

剩下就是冯亲自吹的（

[northisland]

@no1xsyzy 职责我语文不厚道了，手机+摸鱼，能写出圣经么？

[northisland]

ibus 的 Google Pinyin，不打错别字是不可能的

[Curtion]

图灵机是计算模型，相同的还有 lambda 演算，它们本质上是可计算性的问题，理论还囊括了哥德尔不完备定理，你查到的图灵机说明是它的的外在形式，结合停机问题更容易理解。

[lmmortal]

最初的纸带应该是打孔的，用有没有孔表示 0 和 1

[valedelfino]

与其说计算机语言的的原理是图灵机倒不如说 imperative programming 是由图灵机来的， 与之相对的 functional programming 是由 lambda calculus 变来的，turing machine 是一种计算模型， 它能够解决我们用计算机能解决的所有问题， 与计算机本身的结构无关。
还有就是 turing machine 比 fsa 厉害， 顺序大概就是，fsa/nfa ≤ cfg/pda ≤ turing machine

[hhw123]

数字电路

[valedelfino]

@valedelfino 计算机的原理*

[jimmyismagic]

我的理解，图灵机就是 cpu+存储

[dfzj]

图灵机的发明就是为了解决数学或者元数学领域 [关于什么是可计算的这一命题] 而产生的，
我们用的计算机只是按照图灵机的原理进行物理实物实现，也就是冯诺依曼实现

[ljpCN]

图灵机本身就是一个数学形式的描述

[BoarBoar]

@northisland #37 数学模型本就是抽象的理论指导，为啥要考虑实现和输出？你公司里是写抽象接口的码农等级高，还是实现 crud 的厉害？

[cnt2ex]

计算机之父这个称谓本身就有多个，电子计算机之父，理论计算机之父，通用计算机之父等等。
图灵机的贡献主要是理论上的。对于通用计算机这个概念来说，在有图灵完备这个概念之前，查尔斯·巴贝奇在 1837 年就已经构想出了分析机，之后被证明是图灵完备的，而图灵机在 1936 年才被提出，可以说和图灵机没什么关系。而现代电子计算机则主要是冯诺依曼模型，也很难说这是不是受到图灵机启发才有的。

[oneforallsoft]

歪个楼
在下才疏学浅 只想说图灵关于 人工智能的图灵测试 在在下眼里经不起推敲

[oneforallsoft]

图灵没那么神 图灵测试是错误的

[zhangysh1995]

推荐一下我自己在小破站做的科普 N 和 NP 问题的视频，具体可以看我 github 主页的信息。

图灵机是一个理论上的计算模型，可以理解为把 0 1 打在纸带上面，通过读取来进行操作。可以有两条纸带，一条操作，一条数据。理论依据请看 Church-Turing 的论文，具体描述了这个模型的构造和能力。关于图灵机最有名的是 停机问题（ Halting Problem ），就是说不存在一个程序能够判断给定的程序能否停止。有兴趣可以看一看一些计算理论的内容。

现在的计算机是图灵机的具体实现，冯诺依曼贡献的是计算机的体系结构。

[zhangysh1995]

@oneforallsoft 如果你看了图灵的论文就不会这么说了。

[zhangysh1995]

看了这个帖子我认识到了不应该这么严肃认真回复。

[yuruizhe]

@zhangysh1995 大三的时候老师上课介绍过这个定义，也是以停机问题举例的，依稀记得，图灵机可解 NP 问题，但现在 NP 问题还不确定是否可解，所以现存的计算机都不是图灵机，好像是这么个说法

[w1573007]

计算理论…专门的一门课，专门讲理论的

[ryd994]

@yuruizhe 现代计算机都是冯诺伊曼机。冯诺依曼机是一种图灵机。图灵机可以解 np 问题，但是无法保证在有限的时间内确认是否有解。当然，你硬要写个程序去解也是可以的。只是当程序一直计算不出结果时，你不知道是自己的程序有 bug，还是这个问题根本就没有解。

确定有解一般很简单，找出解就行了。确认没有解却难得多。

@oneforallsoft

[user8341]

@yuruizhe 你可能记错了。NP = P 是在计算复杂性的领域讲的。确实也是图灵机相关，但是它的模型是确定性图灵机和非确定性图灵机。非确定性图灵机至少现在还造不出来。NP 跟 P 都是可计算的，只是时间复杂度不一样。

[user8341]

@user8341 量子计算机，进展到什么程度了？好像说谷歌造出来个原型？

[ryd994]

@oneforallsoft 图灵测试本来就不是一种测试。
只是图灵写了一篇文章，讨论了一下他个人对于人工智能的理解，提出了他对于智能的定义。
而这个定义中用了一个游戏来说明。
后人断章取义，把这个游戏叫做图灵测试。


多读书，少瞎 jb 想。但凡看认真查过图灵测试的来源，哪怕只是看了英文版维基，都不会说出你这种话来。

[ryd994]

@kidding 图灵机当然不是 FSA 啊。图灵机有无限的纸带呢

[ryd994]

楼上这么多黑纸带和机械计算机的。你们不会真以为图灵机实际存在吧？不会真以为有人用图灵机计算实际问题吧？

电子计算机再快，也解决不了图灵机无法解决的问题。图灵机的计算能力，是程序解决问题的能力边界。我们现在用的计算机，无论实现，无法超越这个边界。

[zhangysh1995]

Well, 你这个理解有偏差呐。如果不是老师讲错了，可能是你记错了。停机问题和 NP/P 是两件事情。 @yuruizhe

[zhangysh1995]

@ryd994 我觉得前面几楼那个自己臆想的，没必要和他认真讨论。自己不愿意查资料，没必要浪费我们时间。

[oneforallsoft]

@ryd994
就是因为看了维基百科 才意识到有人跟我的看法一样 很多批评图灵测试

[siyemiaokube]

这届 v 站水平不行啊（手动狗头

1:图灵机是目前人类实际制造出的最强的计算模型，在这之上依然有神谕机等计算模型。但是正如 oracle 这个名字一样，目前还无法实现。

2:图灵机是**可计算**理论中的概念，与计算复杂性没有特别直接的关系，在任意的时间复杂度内能够模拟图灵机的计算模型都是图灵完备的。比如 brainf@ck 语言没有内置的乘法语句，但是也可以做乘法。（这个例子有一点小问题）

3:由于我们已经证明了多带图灵机和图灵机可以相互模拟，所以，在设计图灵机的算法时，为了方便，我们常常直接设计多带图灵机的算法。

4:任何图灵完备的计算机都可以解决 np 问题，这甚至可以是 np 问题的定义。np 表示的是非多项式。np 问题是说随着问题规模的增大，渐进意义下需要超多项式级别（比如指数级、阶乘级）的时间才能解决这一问题。
关于 np，通俗文化中常见的讨论是“np=p ？”问题，一般来说我们认为 np-complete 问题不可能存在多项式算法，但是至今未能证明。

5:自动机理论确实对于实际的硬件开发（主要是指令集）有一定指导意义，但是也仅止于此。

6:图灵测试和图灵机之间不存在任何关系。图灵测试是与中文房间相对的思想实验，用于指导人们思考“理性”的定义。

[siyemiaokube]

7:冯诺依曼结构是计算机硬件组成的指导性模型，而图灵机是计算模型，两者所对应的领域没有任何关系。

8: 图灵机的计算能力，是**目前人类能够制造出的计算机的**程序解决问题的能力边界。但是我们在理论的计算模型上可以提出更强大的程序（算法）。

9:量子计算机和并行计算有一定的相似性，但是两者都不影响**可计算性**。

10:哥德尔不完备定理是说内蕴了四则运算的公理系统能够表示出一些这个公理系统内部无法判断真伪的命题。它还有一个名字叫哥德尔完备定理。

[hahastudio]

看起来 V 站真正计算机专业的并不多啊

[NoobX]

建议阅读计算原理类的理论书籍
计算过程主要是利用了 DFA，NDFA，PDA，CFDA 等 Automata 完成的
跟编程中的状态机思路比较类似

[hello2060]

这个问题，你到年薪 500 万之前不需要考虑吧

[ericgui]

@northisland 图灵一辈子是英国人，哪里去美国了？二战前的欧洲仍然是世界科技中心

[northisland]

说计算机专业本科生、研究生能学过图灵的，过分了。



今天翻了一下计算机组成原理的权威书《量化》，没讲图灵。
又翻了一下我们当年上人工智能的教科书《 MLAPP 》和参考书《 PRML 》。都没有图灵。
算法那本书，状态机是重点。学图灵机，也是老师跟郭德纲相声一样讲个故事。


都别🐔儿忽悠了。

图灵大神，是那种站在天上，通过数学，俯视到了机电计算机的天花板的数学家。
因为多种原因，他生前没有真实的机电计算机可以玩。

你我，都在机电计算机的屋子里讨生活，一辈子有几次能从屋子里摸到天花板，就牛逼大了。

[northisland]

@ericgui 大哥，你能上网么？

[KENNHI]

学一下计算机组成原理和编译原理

[no1xsyzy]

@ryd994 冯诺伊曼体系架构 != 冯诺伊曼机
冯诺伊曼机是指自复制机器：某一个机器，提供恰当的原料，可以造出自己。这一点上，大部分生命，包括病毒（无论它是不是生命）都是冯诺伊曼机

话说单片机有些还是哈佛架构，14 位长的指令 EEPROM 和 8 位长的数据 RAM 分开的。至于这些单片机是不是 “现代计算机” 倒是个问题

@ryd994 @yuruizhe 俺寻思 NP 是复杂度问题，不是计算能力问题。

@northisland 主要你写的文字太散又太长
（题外话，圣经用的文字非常基础，母语译本小学水平就能看懂了，决不是文学巨作。你举狄更斯作例子更恰当……吧）
手机就少写点，多花时间想清楚想表达什么，然后言简意赅地用一行解决问题。

@ericgui 去 Princeton 找 Church 修了个 PhD……
Church 就是那个跟图灵机差不多时间提出 lambda 演算的那个

[northisland]

@no1xsyzy 老哥，《圣经》的文学成就，吊打任何中国文学。


你说《圣经》汉字文字水平基础，
是因为你看的是 1900 年左右的[中文和合本]——中国精英还没发起新文化运动，传教士已经用白化文翻译了好几十年了。
你要是翻圣经[马士曼博士译本]，我觉得能满足你对汉语审美的某种要求。

审美之外，是内容。
欣赏不来就别瞎说了，
你看下以及雨果、歌德、托尔斯泰是怎么赞美圣经的。

[northisland]

@no1xsyzy http://bible.fhl.net/ob/ro.php?book=124&procb=3

二马圣经了解一下，希望有一天，伟大的思想点亮你心中不开窍的灯。

[FrandsA]

关于 “图灵机解决的是什么问题 ？”

它解决了希尔伯特提出的关于计算的第三部分问题：是不是所有命题都是数学可判定的？也就是说，是不是对所有命题都有明确程序能在有限时间内告诉我们命题是真是假？

图灵通过构想出了“图灵机”来定义了这个问题中关于“明确程序”的部分从而证明了这个问题的答案是否 。

[jwangkun]

三体入侵了么