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

2020-11-18 08:46:55 +08:00
 James369
如果说计算机是图灵机演变的，那么图灵机的设计理念是什么？

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

初看好像也没什么，但这样的图灵模型一定是经过理论证明过可行的，那么它的理论依据是什么？
为什么这么搞。它解决的是什么问题，它有什么局限？
9994 次点击
所在节点    程序员
82 条回复
no1xsyzy
2020-11-18 11:26:29 +08:00
@northisland 去 Princeton 是带学生…… 不是打工人
Church 是 von Neumann 的小弟么，这倒是没发现……
Mentor 这个词英文中的含义复杂得多，没那么明显的身份差异。
也是东西方文化差异的一环吧

至于 Turing 在计算机原理基础方面名声主要是 von Neumann 吹出来的…… 大佬背书
真正作为核心贡献者还是 Enigma 破译
luomu24
2020-11-18 11:33:21 +08:00
可以去上上《计算理论》这门课，有讲图灵机、DFA 、NFA 、NP 问题。
northisland
2020-11-18 12:23:54 +08:00
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
2020-11-18 12:35:51 +08:00
Theory of Computation

先学学这个课程
northisland
2020-11-18 12:37:31 +08:00
计算机比只能跑一种算法
northisland
2020-11-18 12:41:34 +08:00
图灵机假设足够强大，也只是只能执行一种程序的多纸带机械。
换程序就换纸带。。。想起任天堂卡带偷笑了


跟现代的机电计算机差远了。。。冯诺依曼一年换一辆凯迪拉克最高配，图灵开二手福特，是有原因的。🤣
northisland
2020-11-18 12:43:16 +08:00
不晓得为什么国内有这么多图灵吹。。。难道是这个不幸的老哥吃过资本主义铁拳？
aguesuka
2020-11-18 12:52:53 +08:00
图灵机是计算模型。
计算机从一开始就是冯诺依曼结构(当然计算能力等价于图灵机)如果你对从门电路造计算机感兴趣就去看冯诺依曼结。
如果对可计算领域感兴趣就去看 lambda 运算和它的可判定性问题，相比图灵机，lambda 运算同样是图灵完备的但是规则更少更优美。
northisland
2020-11-18 13:15:35 +08:00
我认为没什么数学原理。。。


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

伟人的灵魂和想法，在电路中陪伴着世界。
kidding
2020-11-18 13:53:23 +08:00
看了下图灵机的定义，感觉就是个 FSA （有限状态机）的样子... 正好最近在学 Introduction to the Theory of Computation
ResidualSoils
2020-11-18 14:17:56 +08:00
@minami 好难找到这篇文章
no1xsyzy
2020-11-18 14:18:49 +08:00
@northisland 你在说什么？
图灵机是数学模型，不是任何种类的计算机

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

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

至于冯架构，冯他本人亲自吹图灵，在别人采访他的时候他着重强调了图灵的名字。
我就跟你说，冯就是第一图灵吹，图灵的名气除了 Enigma 就是冯吹出来的。
你讽刺图灵吹先讽刺冯行不行？
no1xsyzy
2020-11-18 14:21:27 +08:00
@kidding FSA 和 FSM 是一个东西吧……
对图灵机进行了实用主义的劣化，但确实非常实用，导致正则表达式能诞生了
northisland
2020-11-18 15:05:28 +08:00
@no1xsyzy 这图灵机数学模型出来半世纪前，
ibm 创始人就发明 30x10 的打孔纸，还有一起工作的机械计算机，帮助美国进行人口普查清算了。

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

我中午吃饭也是补课出来的，貌似图灵机有 n 根纸带，一根弄输入，一根弄输出，剩下 n-2 根搞内部逻辑。
easing
2020-11-18 15:40:08 +08:00
@northisland #34 大哥，图灵机是计算模型，不是机器。。是为了研究可计算理论而创建的一种模型，用来判定到底什么是可计算的，什么是不可计算的，也就是研究计算的边界问题。跟实际的机器毛关系都没有。要说关系，那也要说元图灵机以及后来优化的各种寄存器机器模型。
no1xsyzy
2020-11-18 15:44:47 +08:00
@northisland 不谈效率，提供恰当的接口约定，图灵机能跑毁灭战士（ Ray cast ），也能跑神经网络
不谈效率，你 IBM 机械计算机行吗？
northisland
2020-11-18 15:45:36 +08:00
@easing
楼主问的是现代的计算机，和图灵机有什么关系。。。 看你的回答，我只能说没啥关系了。。。


@no1xsyzy
确实只有一个纸带，数学模型只考虑输出，不考虑怎么内部实现和输出，2333
northisland
2020-11-18 15:47:19 +08:00
@no1xsyzy 引发了我的兴趣，下班再摸一下图灵大神
no1xsyzy
2020-11-18 15:57:20 +08:00
@northisland 说到底，图灵机不是拿来用的，是拿来使它 “用不了” 的。
通过这一个非常简单的数学模型，证明了 “存在证明不了真假的命题”，破缺了逻辑系统的完备性。
做到相同工作的还有 Lambda Calculus，基本前后，采用两种截然不同的做法做到了完全相同的事情。
而再上升是哥德尔不完备定理。

对了，语文建议重修下，你的文字，形散神也散。
no1xsyzy
2020-11-18 15:59:41 +08:00
@northisland 确实没啥关系，我 #17 说了，现实意义就是 “轻易地就能构造性地证明某一语言能够实现一个图灵机的模拟器。”
比实现 lambda calculus 或者实现元解释器方便多了……

剩下就是冯亲自吹的（

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/726485

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX