图灵机


作者 RanC

这是一篇旨在帮助理解图灵机及相关概念是什么,而非证明其正确性的回答,它包含以下内容:

1.什么是图灵机
2.图灵机可以解决什么问题
3.什么是图灵完备
4.直观理解图灵完备 - Brainfuck语言

1. 什么是图灵机

图灵机(Turing Machine)是图灵在1936年发表的 "On Computable Numbers, with an Application to the Entscheidungsproblem"(《论可计算数及其在判定性问题上的应用》)中提出的数学模型。既然是数学模型,它就并非一个实体概念,而是架空的一个想法。在文章中图灵描述了它是什么,并且证明了,只要图灵机可以被实现,就可以用来解决任何可计算问题。

图灵机的结构包括以下几个部分:

1.一条无限长的纸带(tape),纸带被分成一个个相邻的格子(square),每个格子都可以写上至多一个字符(symbol)。

2.一个字符表(alphabet),即字符的集合,它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符(blank),意思是此格子没有任何字符。

3.一个读写头(head),可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容,此外也可以每次向左/右移动一个格子。

4.一个状态寄存器(state register),它追踪着每一步运算过程中,整个机器所处的状态(运行/终止)。当这个状态从运行变为终止,则运算结束,机器停机并交回控制权。如果你了解有限状态机,它便对应着有限状态机里的状态。

5.一个有限的指令集(instructions table),它记录着读写头在特定情况下应该执行的行为。可以想象读写头随身有一本操作指南,里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时,擦除,改写为1,并向右移一格。此外,令下一状态为运行。”这样的命令。其实某种意义上,这个指令集就对应着程序员所写下的程序了。

image

在计算开始前,纸带可以是完全空白,也可以在某些格子里预先就有写上部分字符作为输入。运算开始时,读写头从某一位置开始,严格按照此刻的配置(configuration),即:

当前所处的位置
当前各自的内容

来一步步的对照着指令集去进行操作,直到状态变为停止,运算结束。而后纸带上留下的信息,即字符的序列(比如类似“...011001...”)便作为输出,由人来解码为自然语言。

要重申一下,以上只是图灵机模型的内容,而非具体的实现。所谓的纸带和读写头都只是图灵提出的抽象概念。为便于理解打一个比方。算盘虽然不是图灵机(因为它没有无限长的纸带,即无限的存储空间),但它的行为与图灵机一致。每一串算珠都是纸带上的一格,一串算珠上展示的数字便记录着当前格中的字符(可以是空白,可以是 12345 )。人类的手即是读写头,可以更改每串算珠的状态。算盘的运行遵循人脑中的算法,当算法结束,算盘停机。

2.图灵机可以解决什么问题

在文章中,图灵所做的事是证明了,假设上述模型里所说的功能都能被以某种形式物理实现,那么任意可计算问题都可以被解决。这里所说的可计算问题,涉及到计算理论(Computation Theory)的概念。这个领域的概念很繁杂,先简单梳理一下。

在计算机领域,或者说自动机领域,我们研究的一切问题都是计算问题(Computational Problem)。它泛指一切与计算相关的问题。

is a mathematical object representing a collection of questions that computers might be able to solve.

计算问题的一些举例:

1.给定一个正整数 n,判断它是否是质数
2.给定一个 01 序列,把它们按位取反
3.给定一个字符串,判断某个字符是否存在,及查找存在位置
4.给定一个逻辑蕴含的命题,求它的逆否命题

非计算问题:

今晚吃什么

计算问题有的可以解决,有的不可解决。这就引出了计算问题的可计算性(Computability)。它可以被理解为“是否存在一个算法,能解决在任何输入下的此计算问题”。如上面的问题 1,我们当然可以找到一个算法来解决判断任意正整数 n 是否为质数的问题(比如从2遍历到 n-1,看 n 是否可以整除它)。所以,问题 1 就是可计算的。

也有一些不可计算的计算问题,比如著名的停机问题(Halting Problem)。它的表述是这样的:给定一段程序的描述和该程序的一个有效输入,运行此程序,那么程序最终是会终止,还是会死循环下去?

given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever.

这个问题很绕人,有点像那个著名的理发师悖论,但它确实是一个计算问题。更具体的,它是一个不可判定问题(Undecidable Problem)。即不存在一个通用算法,可以在任意输入下解决此问题。

回到这一节的主题。简而言之,对于一个问题,对于任意输入,只要人类可以保证算出结果(不管花多少时间),那么图灵机就可以保证算出结果(不管花多少时间)。

3.什么是图灵完备

图灵完备性(Turing Completeness)是针对一套数据操作规则而言的概念。数据操作规则可以是一门编程语言,也可以是计算机里具体实现了的指令集。当这套规则可以实现图灵机模型里的全部功能时,就称它具有图灵完备性。直白一点说,图灵完备性就是我给你一工具箱的东西,包括无限内存、if/else 控制流、while 循环……那么你现在图灵完备了吗?

概念本身倒是非常直观,但整件事似乎还是让人云里雾里。我曾经一直不懂的就是为什么图灵给出的那个命题是正确的。换句话说,凭什么有了纸带以及其他的那一套东西,就可以自信解决任意可计算问题呢?尽管我不能通读他的那篇论文里的证明,但是通过一门叫做 Brainfuck 的编程语言,还是可以获得一些直觉。

4. 直观理解图灵完备——Brainfuck 语言

如今主流的编程语言(C++,Java,Python,以及等等等等)都是图灵完备的语言。关于语言优劣之争也只是在其封装、优化等方面,以及因为这些区别而产生的“不同语言适用于不同情况”的争执。如果我们回到最底层,就会发现它们可以实现的功能其实完全一样,并且本质上就是一个图灵机。

在1993年,Urban Müller 发明了 Brainfuck 语言。这门语言可以说是编程语言界的 helloworld 了——它一共只含有 8 个有效字符,每个有效字符就是一条指令。语言虽然极致轻量,它却是一门图灵完备的编程语言。如果能理解它的工作原理,那么对于理解图灵机是有很大帮助的。

Brainfuck is fully Turing-complete.

先贴上一段 BF 的代码,体验一下它的画风:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++ .------.--------.>>+.>++.

程序编译运行后,控制台打印 "Hello World!"。

BF 的工作机制与图灵机高度一致。首先它存储数据的方式是一个不限长的一维整数数组,里面的数值全部初始化为 0。此外,有一数据指针,每一时刻都指向数组的某一任意元素。指针可以向左/右移动,也可以读取/修改当前值。

语言里的 8 个有效字符分别是:

>
指针向右移动一格
<
指针向左移动一格
+
使指针当前格数值加一
-
使指针当前格数值减一
.
把当前格数值按 ASCII 表输出到终端
,
从终端接受一 byte 的数据,存储其 ASCII 数值到当前格
[
当指针当前值为 0 时,程序跳转至与之对应的 ] 之后;否则程序正常执行
]
程序跳转回与之对应的 [ 处

有了这些工具,我们可以很快做出一个计算乘法的程序。因为 ASCII 表中 'A' 对应的值为 65,可以使用 5 * 13 算出 65 并输出得到字符 'A'。

+++++

[
>+++++++++++++
<-
]

>.

把指针初始处的格子命名为 cell 0,cell 0 右边的那个格子命名为 cell 1。那么第一句将其递增 5 次变为 5。然后,循环执行“右移指针,递增 13 次, 左移指针,递减 1 次”。当 cell 0 的值最终被递减为 0 的时候,循环结束。此时 cell 1 的值执行了 5 次“递增 13 次”的操作,即 65。指针右移至 cell 1,输出此格子,则在终端会看到 'A'。

image

我写这个例子的目的是演示只用图灵机的模型,就可以确实计算出乘法的结果。那么自然更加复杂的计算也可以被拆解成图灵机操作(尽管可能非常琐碎)。此外,这个语言因为简洁,也是第一次练习写编译器的一个非常好的选择。

以上:https://www.zhihu.com/people/zhang-ru-cheng-46/activities