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

[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 的啥主题呀