Investor's wiki

图灵完备

图灵完备

图灵完备是指一台机器,只要有足够的时间和内存以及必要的指令,就可以解决任何计算问题,无论多么复杂。该术语通常用于描述现代编程语言,因为它们中的大多数都是图灵完备的(C++、Python、JavaScript 等)。

##什么是图灵机?

在现代计算机出现之前,艾伦·图灵假设有一天会出现一台可以解决任何问题的机器。这台机器被称为图灵机。

Alan 将他的机器想象成一条长长的磁带,上面以二进制代码(1 和 0)的形式写入信息。这台机器还有一个读/写头,它沿着磁带移动,一个一个地读取每个方块。代码会向机器询问一个计算问题,磁带的长度将达到解决方案所需的长度。

当磁头沿着磁带移动时,机器会遵循简单的指令来控制它的反应。它读取磁带,按照说明进行操作,并在移动时执行特定操作以编写新代码。这种新的代码模式就是问题的答案。图灵的假设机器可以回答任何可以用代码表达的计算问题(并且有一个可计算的答案)。

当设备或编程语言可以通过运行任何程序或解决图灵机可以运行或解决的任何问题来复制图灵机时,它就被认为是图灵完备的。另一方面,如果设备或编程语言无法做到这一点,则称其为图灵不完整。

一个简单的计算器是图灵不完整系统的一个示例,因为它只能进行几种类型的计算。相比之下,可编程科学计算器(能够执行各种计算)可以被视为图灵机。

区块链和图灵完备性

区块链技术的一些应用是图灵完备的,而另一些则是图灵不完备的。这根据实施的脚本技术而有所不同。例如,比特币中使用的脚本语言被有意设计为图灵不完整,因为它符合其目的,增加的复杂性可能会带来问题。通过保持简单,开发人员可以高精度地预测它在有限数量的使用情况下将如何反应。

另一方面,以太坊被构建为图灵完备的区块链。这很重要,因为它需要了解构成智能合约的协议。通过图灵完备,以太坊有能力理解和实施任何未来的协议,即使是那些还没有想到的协议。换句话说,以太坊的图灵完备性意味着它能够使用其代码库执行几乎任何任务,只要它具有正确的指令、足够的时间和处理能力。