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

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

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

初看好像也没什么，但这样的图灵模型一定是经过理论证明过可行的，那么它的理论依据是什么？
为什么这么搞。它解决的是什么问题，它有什么局限？
9994 次点击
所在节点    程序员
82 条回复
northisland
2020-11-18 16:02:48 +08:00
@no1xsyzy 职责我语文不厚道了，手机+摸鱼，能写出圣经么？
northisland
2020-11-18 16:05:32 +08:00
ibus 的 Google Pinyin，不打错别字是不可能的
Curtion
2020-11-18 16:37:53 +08:00
图灵机是计算模型，相同的还有 lambda 演算，它们本质上是可计算性的问题，理论还囊括了哥德尔不完备定理，你查到的图灵机说明是它的的外在形式，结合停机问题更容易理解。
lmmortal
2020-11-18 17:18:22 +08:00
最初的纸带应该是打孔的，用有没有孔表示 0 和 1
valedelfino
2020-11-18 17:29:55 +08:00
与其说计算机语言的的原理是图灵机倒不如说 imperative programming 是由图灵机来的， 与之相对的 functional programming 是由 lambda calculus 变来的，turing machine 是一种计算模型， 它能够解决我们用计算机能解决的所有问题， 与计算机本身的结构无关。
还有就是 turing machine 比 fsa 厉害， 顺序大概就是，fsa/nfa ≤ cfg/pda ≤ turing machine
hhw123
2020-11-18 17:41:07 +08:00
数字电路
valedelfino
2020-11-18 17:46:49 +08:00
@valedelfino 计算机的原理*
jimmyismagic
2020-11-18 17:53:50 +08:00
我的理解，图灵机就是 cpu+存储
dfzj
2020-11-18 18:02:10 +08:00
图灵机的发明就是为了解决数学或者元数学领域 [关于什么是可计算的这一命题] 而产生的，
我们用的计算机只是按照图灵机的原理进行物理实物实现，也就是冯诺依曼实现
ljpCN
2020-11-18 18:07:50 +08:00
图灵机本身就是一个数学形式的描述
BoarBoar
2020-11-18 18:15:51 +08:00
@northisland #37 数学模型本就是抽象的理论指导，为啥要考虑实现和输出？你公司里是写抽象接口的码农等级高，还是实现 crud 的厉害？
cnt2ex
2020-11-18 18:35:12 +08:00
计算机之父这个称谓本身就有多个，电子计算机之父，理论计算机之父，通用计算机之父等等。
图灵机的贡献主要是理论上的。对于通用计算机这个概念来说，在有图灵完备这个概念之前，查尔斯·巴贝奇在 1837 年就已经构想出了分析机，之后被证明是图灵完备的，而图灵机在 1936 年才被提出，可以说和图灵机没什么关系。而现代电子计算机则主要是冯诺依曼模型，也很难说这是不是受到图灵机启发才有的。
oneforallsoft
2020-11-18 18:43:15 +08:00
歪个楼
在下才疏学浅 只想说图灵关于 人工智能的图灵测试 在在下眼里经不起推敲
oneforallsoft
2020-11-18 18:43:45 +08:00
图灵没那么神 图灵测试是错误的
zhangysh1995
2020-11-18 19:28:50 +08:00
推荐一下我自己在小破站做的科普 N 和 NP 问题的视频，具体可以看我 github 主页的信息。

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

现在的计算机是图灵机的具体实现，冯诺依曼贡献的是计算机的体系结构。
zhangysh1995
2020-11-18 19:31:56 +08:00
@oneforallsoft 如果你看了图灵的论文就不会这么说了。
zhangysh1995
2020-11-18 19:33:04 +08:00
看了这个帖子我认识到了不应该这么严肃认真回复。
yuruizhe
2020-11-18 19:46:59 +08:00
@zhangysh1995 大三的时候老师上课介绍过这个定义，也是以停机问题举例的，依稀记得，图灵机可解 NP 问题，但现在 NP 问题还不确定是否可解，所以现存的计算机都不是图灵机，好像是这么个说法
w1573007
2020-11-18 19:49:29 +08:00
计算理论…专门的一门课，专门讲理论的
ryd994
2020-11-18 20:32:17 +08:00
@yuruizhe 现代计算机都是冯诺伊曼机。冯诺依曼机是一种图灵机。图灵机可以解 np 问题，但是无法保证在有限的时间内确认是否有解。当然，你硬要写个程序去解也是可以的。只是当程序一直计算不出结果时，你不知道是自己的程序有 bug，还是这个问题根本就没有解。

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

@oneforallsoft

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

https://tanronggui.xyz/t/726485

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

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

© 2021 V2EX