图灵机是什么 科普：什么是图灵机？

图灵机是图灵机理论中提出的理想模型，可以实现任何复杂的计算。

什么是图灵机

英国数学家艾伦·图灵于1936年提出了图灵机理论。“图灵机”假设有一张无限大的纸，上面有正方形，每个正方形可以存储一个符号，纸可以左右移动。

图灵机可以做以下三个基本操作:

读指针头指向的符号。

修改框中的字符。

向左或向右移动磁带以修改其相邻框的值。

我们举个小例子，看看图灵机是怎么计算的。这个例子比较简单。我们将在空白色纸带上打印三个数字1 1 0。

首先，我们将数字1写入指针头指向的框中:

接下来，让我们将纸带向左移动一个方框:

现在，让我们把数字1写在指针头所指的方框中:

接下来，我们继续将纸带向左移动一格，并写下数字0:

这样，我们完成了一个简单的图灵机操作。

用图灵机完成异或运算

让我们试试稍微复杂一点的操作。我们尝试在1 1 0上做一个异或运算，也就是把1 1 0变成0 0 1。用图灵机完成计算类似于把下面的操作指令输入图灵机，构成一个小程序。

符号读取

写入指令

传送指令

空

-

-

0

写1

将磁带移到右边

一个

写入0

将磁带移到右边

我们假设图灵机磁带现在如下图所示:

现在符号读数为0。根据操作说明，我们应该在方框中写1，并向右移动一个方框:

现在读取的符号是1。根据操作说明，我们应该将0写入框中，并将一个框向右移动:

同样，现在读取的符号是1，我们重复同样的操作。

最后我们读了一个空白色字符，图灵机什么都不做。

用图灵机完成任何复杂的计算

以上，我们利用图灵机成功完成了异或运算。理论上我们也可以完成加减乘除，但是步骤(指令)比较复杂。以下网站是图灵机的在线模拟器，实现一些基本操作，比如加减运算等。有兴趣的可以自己试试。

在线图灵机模拟器

图灵机的意义

让我们试试这个思考过程:

我有很多复杂的公式要计算，自己动手的话要花很长时间。

思考:有没有一件事可以帮我算出公式，不管有多复杂？

思考:我可以设计一个模型来证明这个实现是可行的吗？(数学家喜欢建模型证明~)

思考:通过提出图灵机理论，任何计算都可以简化为一个固定的步骤，无论计算多么复杂，都可以实现。

一些动手能力很强的数学家利用电子工程知识，形成一套多真空管的设备，实现了图灵机的理论模型。

随着电子工程的不断发展，原本巨大的电脑变得越来越小，慢慢变成了今天的电脑。

图灵机理论通过假设模型证明任何复杂的计算都可以通过简单的运算完成，从而从理论上证明了“无限复杂计算”的可能性，直接为计算机的诞生提供了理论基础。

从这个思维过程来看，图灵机的出现为计算机的诞生奠定了理论基础，这就是图灵机诞生的意义。