Video在线视频

大家好

这一节我们介绍

图灵机的计算能力

图灵机的计算能力如何呢

大家知道

图灵机为现代电子计算机

奠定了坚实的理论基础

那么

图灵机的计算能力

到底怎么样呢

很多介绍图灵机的书籍

都有大致这样的描述

说图灵机本身虽然简单

但计算能力很强

有点不可思议吧

是的

那么

我们如何理解

图灵机的计算能力很强呢

要从理论上来探讨或者论证

图灵机的计算能力

真的不是一件容易的事情

那么就让我们换一个角度

来理解图灵机的计算能力

大家知道

现实的计算机计算能力很强

C语言也是很多程序员喜欢的

高级程序设计语言

大量的软件

也都是用C语言开发的

比如著名的

UNIX Windows操作系统

如果我们设法证明

C语言的计算能力

图灵机也都具有

你还会怀疑图灵机的能力吗

那么怎么证明呢

哦 你不要着急

我们得换换思路

让我们先来定义一门

非常非常简单的语言

简单到什么程度呢

简单到只有三个语句

我们不妨称之为M语言

M即Middle

也就是中间语言的意思

好吧

让我们先一睹M语言的芳容吧

M语言总共只有三个语句

第一个语句叫递增语句

inc(x)

也就是increase(x)

它的含义就是让x的值加一

第二个语句叫递减语句

dec(x)

也就是decrease(x)

它的含义就是使x的值减一

第三个语句叫循环语句

while(x)

然后的话

里面有一个循环体

就是Body of the loop

然后后面还有一个语句

就是前面讲过的第二个语句

decrease(x)

这个语句是什么意思呢

就是当x不为零的时候

我们就执行括号里面这一个循环体

每执行一次循环体

x都减一

然后再判断x的值是否为零

如果x的值还不为零

那继续执行循环体

再减一

以此类推

不断地循环

一直到x的值到零为止

好

M语言

就是这么三个语句组成的

现在我们来证明

M语言的能力等价于C语言

这事儿不难

只要能用M语言等价描述

C语言中的每一个语句

即可表明C语言能做的事情

我M语言都能做

让我们先看看

C语言中的赋值语句

也就是把x的值

加上y的值赋值给y

我们完全可以用

下面的M语言程序来表示

也就是

while(x)

循环体里面的话呢

就是两个语句

一个是increase(y)

一个是decrease(x)

再看看

C语言中的条件语句

if(x) A

也就是说

当x的值不为零的时候

我们就执行语句A

这么一个句子

我们可以用M语言来表述

也就是while(x)

循环体里面的话呢

就是语句A

再加一个decrease(x)

就可以等价描述

这么一个条件语句了

再比如

C语言中把变量初始化为零

也就是把零赋值给变量x

我们可以用这么一个

while循环来表示

while(x)

循环体里面只有一个语句

decrease(x)

每循环一次

x的值都减一

一直到x为零为止

以此类推

我们没有必要

在这里列举所有的语句

C语言中任何一个语句

我们都可以以此方式

用M语言来等价模拟

因此

也就可以表明

M语言在表达能力

在功能上与C语言等价

您看 果然“人小鬼大”吧

接下来

我们再证明M语言能做的事情

图灵机都能做

由于M语言只有3个语句

只要我们构造出

3个等价的图灵机即可

实践证明

我们可以做到

具体如下

一 语句increase(x)对应的图灵机

以及它的状态转换图

如图所示

该图灵机如何构造

在这里我们不做详细的介绍

大家知道我们可以做到就行了

二 同样我们可以构造出语句

decrease(x)对应的图灵机

以及相应的状态转换图

就像这样

三 while循环语句的图灵机

以及相应的状态转移图

稍微复杂一些

没关系

能做到就行

因此 我们完全可以说

M语言能做的计算

图灵机都能胜任

而前面我们又论证了

C语言能做的事情

M语言都能做

因此

我们可以说C语言能做的事情

图灵机也都能做

事实上

现代计算机能进行的计算

图灵机都可以模拟

但是反过来则不然

从理论上来说

图灵机可以求解

一台计算机能解决的任何问题

这个结论可以在

邱奇--图灵论题中找到

需要注意的是

这只是论题

不是定理

定理可以在数学上得到证明

但论题却不能

虽然这个论题

可能永远得不到证明

但有些强有力的论断在支持它

首先

我们尚未发现

有图灵机不能模拟的算法

其次

所有在数学上

已经得到证明的计算机模型

都与图灵机模型等价

这个论断是得到证明了的

为了表彰图灵所作出的

杰出的贡献

计算机界专门设有一个

一年一度的“图灵奖”

颁发给最优秀的计算机科学家

这枚奖章就像

电影界“奥斯卡奖”一样

为计算机界的获奖者

带来至高无上的荣誉

好 这一节就讲到这

谢谢大家