Topic: 图灵完备 (Read 130 times)
是不是经常看到很多白皮书上写过图灵完备？
那么图灵完备说什么东东呢？专门查了些资料，与大家分享下。
什么是图灵机？
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
(很难理解是不是，简单记住第一句就行了)
图灵机能解决什么问题呢？
只要在数学领域、计算机领域、自动化领域等，只要是可以计算的问题，理论上讲，图灵机都可以来计算。比如说，让你算3×3=多少，这种可以计算能够得出结果的问题，图灵机都可以解决。
什么问题图灵机解决不了呢？比如说“周末去哪玩”，这不是一个纯粹的可以计算的问题，图灵机就解决不了。
简单说，对于一个问题，只要你能输入一些图灵机可以识别的数据，问题是可以计算的，图灵机就能给你一个结果。
什么是图灵完备？
图灵完备和图灵机不是一回事。
图灵完备就是指程序员编写的各种代码语言，再加上一种运算规则，能在图灵机这种虚拟机中完美地运算，这些编程语言就叫图灵完备。
图灵完备的代表就是以太坊。
那么图灵完备说什么东东呢？专门查了些资料，与大家分享下。
什么是图灵机？
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
(很难理解是不是，简单记住第一句就行了)
图灵机能解决什么问题呢？
只要在数学领域、计算机领域、自动化领域等，只要是可以计算的问题，理论上讲，图灵机都可以来计算。比如说，让你算3×3=多少，这种可以计算能够得出结果的问题，图灵机都可以解决。
什么问题图灵机解决不了呢？比如说“周末去哪玩”，这不是一个纯粹的可以计算的问题，图灵机就解决不了。
简单说，对于一个问题，只要你能输入一些图灵机可以识别的数据，问题是可以计算的，图灵机就能给你一个结果。
什么是图灵完备？
图灵完备和图灵机不是一回事。
图灵完备就是指程序员编写的各种代码语言，再加上一种运算规则，能在图灵机这种虚拟机中完美地运算，这些编程语言就叫图灵完备。
图灵完备的代表就是以太坊。
Jump to: