图灵机和图灵完备

周海汉 2019-06-09
2019-06-09

图灵机(Turing Machine‘’)

英国数学家Alan Turing 于1936年发表的《On Computable Numbers,with an Application to the Entscheidungsproblem》(论可计算数及其在判定性问题上的应用)中提出的数学模型。

用于解决任何可计算问题。

图灵完整性的含义

图灵证明,您无法通过在计算机上模拟程序来预测程序是否会终止。简单来说,我们无法在不运行程序的情况下预测程序的路径。图灵完备系统可以在“无限循环”中运行,这是一个术语(过度简化)用于描述不终止的程序。创建一个运行永不结束的循环的程序是微不足道的。但是由于起始条件和代码之间的复杂交互,无意中永无止境的循环可以在没有警告的情况下出现。在以太坊中,这提出了一个挑战:每个参与节点(客户端)必须验证每个事务,运行它调用的任何智能合约。但正如图灵所证明的那样,以太坊无法预测智能合约是否将终止,或者它将运行多长时间而不实际运行(可能永远运行)。无论是偶然还是故意,都可以创建一个智能合约,使其在节点尝试验证时永远运行。这实际上是DoS攻击。当然,在一个需要一毫秒验证的程序和一个永远运行的程序之间是一系列令人讨厌的资源占用,内存膨胀,CPU过热的程序,它们只会浪费资源。在世界计算机中,滥用资源的程序会滥用世界资源。如果无法预先预测资源使用情况,以太坊如何限制智能合约使用的资源?

图灵机包括:

  1. 一条无限长纸带(tape),纸带分成一个一个格子(square),每个格子可以写最多一个字符(symbol)
  2. 一个字符表(alphabet),纸带上字符全集及一个空白字符(blank),表示没有字符。
  3. 一个读写头(head),读写格子的指针。可以读写擦去格子中的内容。可以左右移动一个格子
  4. 一个状态寄存器(state register),用于保存状态。追踪整个机器的状态(运行,停止)。
  5. 一个有限指令集(instructions table),读写头在特定情况下应该执行的行为。就是程序。

image 开始时,纸带空白,或者某些地方预先存有数值。机器启动时,根据配置(configuraton),指针指在某一位置。 初始值包括:指针所在位置,指针所指位置的值,纸带上其他格子的值(一般空白)。 然后根据指令执行,直到结束。

想象的图灵机组成图: image

上图中,有一个无限长的纸带(tape),分成格子。有一个0-11格的状态寄存器。有程序指令输入。大的立方体就是读写头指针(head),会根据状态和指令完成动作。如读写擦除纸带,移动指针。 机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。

什么是图灵完备?

实现通用图灵机等价的计算语言或指令。即一切可计算问题,在不考虑资源的情况下,都可以用该语言完成计算,即为图灵完备。

假设一个语言只有加法,那么是图灵不完备的。如果我要根据不同的条件走不同计算就不能实现。 正则表达式非图灵完备。因为很多计算通过正则表达式不能完成。

end


如非注明转载, 均为原创. 本站遵循知识共享CC协议,转载请注明来源