Chess_Bridge 版 (精华区)

发信人: dad (andy), 信区: Chess_Bridge
标  题: 围棋与计算机一从地球到月球
发信站: 哈工大紫丁香 (Wed Jul  7 15:44:56 1999), 转信

从电脑诞生之日起，人们对于电脑就充满了幻想。尤其是在人工智
能上，对于电脑超过人脑，有人兴奋，有人担忧，但曾经几乎所有
人都认为这会是真的。尤其当“深蓝”击败卡斯帕罗夫之后，人们
已经开始担忧，但这种担忧实在是来的太早了。

本世纪七八十年代,对人工智能学家们来说，就象是无忧无虑的童年。
他们雄心勃勃，甚至排出了电脑替代人脑的时间表。在表中，现在
就已经应该是电脑超过人脑的日子了。现在，“深蓝”确实战胜了卡
斯帕罗夫，但人工智能学家们的时间表早已被抛到了脑后。有人甚
至打了这样一个比喻来说明人工智能上所取得的成就：人们想登上
月球，他们造了一个梯子，用这个梯子爬上了一棵树，然后自豪地
宣称：“现在，我们已向月球前进了一大步！”

现在，电脑已经渗入到了我们生活的各个方面，在生产和生活中，
我们已经有些难以想象脱离电脑的状况了，如果说这些形形色色的
电脑只不过是花里胡哨的各种梯子，似乎实在是说不过去。

我们先看看梯子是怎么回事吧。

梯子的发明人是图灵博士。图灵在考虑可计算的机器的性质时，首
先是设想一个人在计算，他把这个人的计算行为抽象成了这样一台
机器：有一条无穷长的纸带子，一个有很多状态的机器在纸带上左
右滑动，并且可以根据所读到的内容改变自己的状态或者改写纸带
的内容。这就是大名鼎鼎的图灵机了。当前的所有计算机，在理论
上都是可以被图灵机模拟的。

请注意图灵机有一个重要的能力：改写纸带的能力。如果没有这个
能力，那这台机器叫做有穷自动机。它和图灵机间的计算能力差着
三个档次呢。（注意：在一条无穷长的纸带上读东西，在另一条纸带
上写东西的机器也是有穷自动机）。

判断这些东西的计算能力用的是这些机器所能接受的语言的概念。
这个语言虽然是抽象的语言，但也和我们平时所说的语言差不多，
你只要理解成这机器能听懂什么话也就差不太多了。乔姆斯基把语
言分成了0，1，2，3四个等级，0级能力最强，3级最差。这四个
等级之间有着难以逾越的鸿沟。

这里的3级语言也叫做正规语言，就是有穷自动机能听懂的，2级
语言叫做上下文无关语言，意思是一个词，不用管它的上下文，就
可以听懂了。1级语言就是上下文相关的了，也就是说机器还得揣
摩这话前后的意思。零级语言就是图灵机可以接受的语言了。

我们用数数的本事就可以体会1，2，3型语言的能力差别了。

对于数数，有这么一个笑话：两个贵族比赛，看谁说出的数更大，
第一个人绞尽脑汁，冥思苦想十几分钟后说：3，轮到第二个人，
他想了很久很久，最后说：你赢了。

数到3的本事哪型语言都会，我这里说的数数本事是从一数起，只
要不老死，数多少个都行。3型语言，也就是正规语言，是不会数数
的。2型语言（上下文无关语言）会数数，但同时数两个数就不会了。
1型语言就是数多少个数都行的了。而0型语言的能力又比1型语言
强的多。也就是说，图灵机看上去简单，实际上是还是很牛的。

但是图灵自己就发现了图灵机也有不照的时候了，这就是图灵机的停
机问题。我们可以这样说明图灵机的停机问题：假设当图灵机听懂了
一句话，它就不再琢磨这句话了，现在我给图灵机一句话，问它“你
听的懂吗？”如果它听的懂，它会回答“是”，但如果它听不懂，很可
能它永远也不会知道自己听不懂。

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: www-post@bbs.hit.edu]