图灵机(Turing Machine‘’)
英国数学家Alan Turing 于1936年发表的《On Computable Numbers，with an Application to the Entscheidungsproblem》(论可计算数及其在判定性问题上的应用)中提出的数学模型。Entscheidungs 是德语，即decision problem，可判定性问题。该问题由德国数学家David Hilbert提出，能不能存在一种算法，输入合规的逻辑语句(Formal Logic Statment)，得到准确的“是”或“否”的回答。 比如：是否有一个数大于所有数？否。
阿兰图灵想出一种假想的计算机，叫图灵机，提出简单的数学计算模型，用于解决任何可计算问题。
图灵完整性的含义
图灵证明，您无法通过在计算机上模拟程序来预测程序是否会终止。简单来说，我们无法在不运行程序的情况下预测程序的路径。图灵完备系统可以在“无限循环”中运行，这是一个术语（过度简化）用于描述不终止的程序。创建一个运行永不结束的循环的程序是微不足道的。但是由于起始条件和代码之间的复杂交互，无意中永无止境的循环可以在没有警告的情况下出现。在以太坊中，这提出了一个挑战：每个参与节点（客户端）必须验证每个事务，运行它调用的任何智能合约。但正如图灵所证明的那样，以太坊无法预测智能合约是否将终止，或者它将运行多长时间而不实际运行（可能永远运行）。无论是偶然还是故意，都可以创建一个智能合约，使其在节点尝试验证时永远运行。这实际上是DoS攻击。当然，在一个需要一毫秒验证的程序和一个永远运行的程序之间是一系列令人讨厌的资源占用，内存膨胀，CPU过热的程序，它们只会浪费资源。在世界计算机中，滥用资源的程序会滥用世界资源。如果无法预先预测资源使用情况，以太坊如何限制智能合约使用的资源？
图灵机：
图灵机是一台理论计算设备，有无限长的纸带，类似存储设备。一个读写头，用于读写纸带。一个状态变量，用于保存当前状态。一组规则，用于描述机器做什么，根据当前状态和读写头看到的符号，执行指令。指令包括读写纸带，改变状态，移动纸带等。 图灵机包括：
- 一条无限长纸带(tape)，纸带分成一个一个格子(square)，每个格子可以写最多一个字符(symbol)
- 一个字符表(alphabet)，纸带上字符全集及一个空白字符(blank)，表示没有字符。
- 一个读写头(head)，读写格子的指针。可以读写擦去格子中的内容。可以左右移动一个格子
- 一个状态寄存器(state register)，用于保存状态。追踪整个机器的状态(运行，停止)。
- 一个有限指令集(instructions table)，读写头在特定情况下应该执行的行为。就是程序。
开始时，纸带空白，或者某些地方预先存有数值。机器启动时，根据配置(configuraton)，指针指在某一位置。
初始值包括：指针所在位置，指针所指位置的值，纸带上其他格子的值(一般空白)。
然后根据指令执行，直到结束。
想象的图灵机组成图：
上图中，有一个无限长的纸带(tape)，分成格子。有一个0-11格的状态寄存器。有程序指令输入。大的立方体就是读写头指针(head)，会根据状态和指令完成动作。如读写擦除纸带，移动指针。 机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
图灵机举例
纸带上有个10组成的序列。0为字符串结束。现在需要统计1的个数。是奇数则在纸带上输出0，偶数则输出1。 先制定指令：
| id | state | current symbol | instruction |
|---|---|---|---|
| 0 | even | 1 | set state=”odd”; move head right |
| 1 | even | 0 | set state = “halt”; move head right; write 1 |
| 2 | odd | 1 | set state=”even”; move head right |
| 3 | odd | 0 | set state = “halt”; move head right; write |
| 4 | halt | _ | halt |
初始状态 state=”even”
如我们判定纸带上“110”的1的个数：
- 执行第0个指令，读到第一个1，状态变为 odd，读写头移到第2个1.
- 状态是odd，读到第二个1，执行指令3，状态变为even，读写头往右移(到了第三个字符0)
- 状态是even，字符是0，执行第1个指令，状态变为停止，读写头移到右边，写下结果：1. 即该字符串有偶数个字符“1”。
图灵证明了如果有足够的时间和内存(纸带长度)，可以执行任何计算。它是一台通用计算机。
图灵完备(Turing Complete)
什么是图灵完备？ 实现通用图灵机等价的计算语言或指令。即一切可计算问题，在不考虑资源的情况下，都可以用该语言完成计算，即为图灵完备。
停机问题：(Halting problem)，给定图灵机问题描述和纸带数据，能否在不执行的情况下，判定机器会永远算下去还是会停机(Halt)。停机问题不能用图灵机解决。Church 和图灵证明了计算机是有极限的，不是任何问题都能解决。叫Church-Turing 理论。
假设一个语言只有加法，那么是图灵不完备的。如果我要根据不同的条件走不同计算就不能实现。 正则表达式非图灵完备。因为很多计算通过正则表达式不能完成。
图灵测试
计算机能欺骗人类相信他是人类，才算是真正智能。图灵测试成为人工智能测试的基础。现代版叫“公开全自动图灵测试”，用于区分计算机和人类。如一些验证码，或者指令动作，都是图灵测试。
图灵是同性恋，1952年在调查图灵的“入室盗窃案”时被泄露，被起诉“行为严重不检点”，要么入狱，要么服激素药。他选择了后者。1954年自杀。年仅41岁。 end
如非注明转载, 均为原创. 本站遵循知识共享CC协议,转载请注明来源
