比特派官网下载app|比特币上的图灵机 - CoinGeek

这篇文章首先发表在 Medium 上。

我们已经凭经验证明，任何图灵机都可以在比特币上进行模拟，从而最终证明它是图灵完备的。 我们已经实现了一个识别平衡括号的图灵机并将其部署在比特币区块链上。 任何其他图灵机都可以用同样的方式模拟。

图灵机介绍

图灵机由以下组件组成（简化）：

推荐阅读 1

Shiba Inu：总部位于伦敦的加密货币交易所添加了 Bone ShibaSwap（BONE）

3小时前 2

应税加密货币和加密货币税收循环的可能性

4小时前

• 当前状态，来自一组有限的状态（其中一个状态标记为初始状态，一些状态标记为接受状态）
• 带有存储单元和可在磁带上移动的读/写头的磁带
• 一个所谓的转换函数，它告诉机器做什么和什么时候做。

在下面的示例中，我们展示了用于检查平衡括号的图灵机。 它的初始状态是 A，它包含一个接受状态。 转换函数说，例如，如果机器处于状态 A 并且它的头部读取符号“）”，它应该在该单元格中写入“X”并向左移动，转换到状态 B。

检查平衡括号的图灵机

丘奇图灵论题

Church-Turing Thesis 指出图灵机可以计算任何可以计算的东西。 它是计算的定义，也是对计算机进行推理的基本工具。

在比特币上模拟图灵机

我们展示了一种在比特币上模拟图灵机的通用方法。 我们拍摄正在运行的图灵机的快照：磁头位置、当前状态和磁带。 快照存储在有状态的比特币智能合约中。 更具体地说，它们在比特币交易的输出中。 运行图灵机的每一步都由比特币交易触发。 图灵机可以继续运行，除非它进入接受状态。

模拟图灵机 (TM)

执行

为了证明在比特币上模拟图灵机的可行性，我们实现了前面提到的图灵机检查平衡括号，如下图。

检查平衡括号的图灵机合约

每次在交易中调用公共函数 transit() 时，机器前进一步。

• 第 3-6 行：定义状态，包括初始状态和接受状态
• L9-12：定义所有符号
• L19-30：将转换函数定义为表格
• L37：从头部读取符号
• L40-43：使用当前状态和头部符号； 我们在转换函数表中查找以找到新状态（L46），写入磁带（L48），并移动磁头（L50）。
• L51-59：最初，磁带只包含输入字符串，例如“(())()()”。 如果磁带在左侧（L52）或右侧（L56）用完，则会添加一个空白单元格。 这确保磁带可以任意长并且是无界的（但不是无限²）。

部署

我们已经将上面的图灵机部署到比特币上，并在输入字符串“(())()()”上运行它。 完整的执行如下所示。

图灵机接受 (())()()

这是第 0 步的图灵机：

第 0 步的图灵机

你可以看到图灵机的快照被编码在这个交易中。

第 0 步：txid

同样，这是第 3 步：

第 3 步的图灵机

它被编码如下：

第 3 步

图灵完备证明

通过简单地更改状态、符号和转换函数，可以直接修改上面的图灵机合约以实现任何其他图灵机。 因此，任何图灵机都可以在比特币上进行模拟，最终证明比特币是图灵完备的。 QED。

在可计算性理论中，如果一个数据操作规则系统可以用来模拟任何图灵机，则称它是图灵完备的。

更新：12/2022

有一篇独立的论文证明基于 UTXO 的区块链是图灵完备的，使用的逻辑与我们的类似：Self-reproducing Coins as Universal Turing Machine。

更新：2/2023

另一篇独立论文通过模拟任何计数器机器证明比特币是图灵完备的：Computationally sound Bitcoin tokens。 它需要更改比特币脚本以包含契约，这实际上是不需要的，因为 OP_PUSH_TX。

致谢

感谢 Pasquale Valentin 帮助部署比特币合约。

***

[1] 我们之前已经通过在其上实施图灵完备系统（例如 Conway 的生命游戏和规则 110）来证明比特币是图灵完备的。[2] 克雷格·怀特 (Craig Wright) 的无限与无限 | 2021 年 9 月 14 日

观看：BSV 上的智能合约和计算

width=”562″ height=”315″ frameborder=”0″ allowfullscreen=”allowfullscreen”>

比特币新手？ 查看 CoinGeek 的比特币初学者部分，这是了解更多关于比特币（中本聪最初设想的）和区块链的终极资源指南。