自动机实际上是如何“计算”的?

计算科学 复杂
2021-11-29 05:28:39

在我对可计算性的研究中,我遇到了“机器”的概念,它是本质上计算的设备的抽象表示。我读过图灵机和 Wolfram 的二进制元胞自动机,我理解它们。规则、状态、颜色等以及它们是如何工作的。然而,我真正不明白的是它们如何被视为计算的抽象。为什么自动机甚至用来表示计算机?

它们以某种状态开始并永远运行(除非指定了终止状态)。我在这里试图说明的关键点是它们不接收外部输入,并且本质上是它们自身的函数:它们的当前状态是其起始状态的某种函数。

2个回答

图灵机只是计算机的一个简单模型。一方面,只有一组受限的操作。在现代 PC 上,您有更多的操作。另一方面,一个人拥有无限的空间和时间,这对于现代 PC 来说并非如此。所以,目标只是,你可以轻松地分析图灵机。所以你说,你可以结合这些简单的操作来获得现代 PC 的复杂操作,并且假设内存限制不是问题,这对于大多数软件来说都是正确的。

然后很容易分析,算法是否可以在计算机上运行,​​或者编程语言是否是图灵完备的。

如果您在这个无限大的内存带上写一些位,您可以对 Turing Mashine 进行编程;-)。我想你会在网上找到一些图灵模拟器,或者你可以观看这个关于计数程序的精彩示例视频。

最简单的计算机模型由自动机及其磁带组成。

自动机启动时,输入就在磁带上。该程序在(即定义)自动机中,或者它是输入的一部分(对于通用图灵机)。并且输出在自动机停止时(如果它停止)在磁带上。如果存在无限循环,在实际程序中也会发生不停止。

因此,(足够通用的)自动机捕获了真实程序执行的所有特征。事实上,可以将任何算法映射到图灵机上,这给出了术语“算法”的标准、数学上严格的定义。