一.逻辑和证明，集合，函数
1.逻辑难题
/html/88/6426/
二.算法，整数和矩阵
三．数学推理，归纳与递归
现在描述计算机科学里的一个最著名定理的证明，证明存在不能用任何过程来解决的问题，即证明存在不可解的问题。研究的这个问题是停机问题，问是否存在这样做的过程：以计算机程序和程序的输入作为输入，确定当程序依据是这个输入运行是否最终停止。可以以此帮助测试程序是否进入死循环，当编写和调试程序时肯定会有帮助。图灵证明了不存在这样的过程。
在给出停机问题是不可解的证明之前先要注意，运行程序并观察程序做什么，仅仅如此并不能确定当程序在给定输入上运行时是否终止。如果程序停止，就得到了答案，但如果经过任何固定长度的时间之后程序仍然在运行，就不知道就是永不停机，还是没有等到足够长的停机时间。毕竟运算10亿年之后才停止的程序是不难设计出来的。
证（归谬证明，严格证明需要用图灵机的概念解说）：假定停机问题有解，即存在所谓的H(P,I)的过程。过程H(P,I)有两个输入，一个是程序P,另一个是程序P的输入I。如果H确定当给定的I作为输入时P停止，则H(P,I)产生字符串“停机”作为输出，否则，H(P,I)产生字符串“死循环”作为输出。从而导出矛盾。
过程在编码时表示成字符串，把这个字符串解释成比特序列。这意味着程序本身可用作数据。因此可认为程序是另一个程序的输入，甚至是自身的输入。因此，H可用程序P作为两个输入，即程序和这个程序的输入。H应当能够确定当P给定自身的拷贝作为输入时是否停机。
要证明不存在解决停机问题的过程H，就构造简单过程K(P)，K(P)利用H(P,P)的输出来这样工作：如果H(P,P)的输出是“死循环”，这意味着当P给定自身拷贝作为输入时死循环，则K(P)停机，如果H（P,P）的输出是“停机”，这意味着当P给定自身拷贝作为输入时停机，则K(P)死循环。
现在假定把K作为K的输入。注意，如果H(K,K)的输出是“死循环”，则根据K的定义可知K(K)停机，否则，如果H(K,K)的输出是“停机”，则根据K的定义可知K(K)死循环，与H所说的相悖。在两种情形之下都存在矛盾。
因此H不能总是给出正确答案，所以不存在解决停机问题的过程。
数学归纳法
1.良序性&&每个非空的非负整数集都有最小元
例：在一种主客场循环赛中，每个选手与其他选手恰好比赛一次并且每次比赛分出胜负。所谓选手p1,p2,p3....,pm形成回路，就是p1战胜p2，p2战胜p3，...&,pm战胜p1.用良序原理证明：如果在主客场循环赛中的选手存在长度为m的回路（m&=3），则必定存在这些选手中的三个选手的回路。
证：假设不存在三个选手的回路，因为主客场中至少存在一个回路，所以存在长度为n的回路的所有正整数n的集合是非空的。根据良序集，这个正整数集合有最小元k，根据假设k必定大于3,因此，存在选手回路p1,p2,...pk并且不存在更短的回路。
现在假设不存在这些选手中三个选手的回路，所以这里k&3.考虑这个回路的前三个元素是p1,p2,p3.在p1与p3之间的比赛有两种可能的结果。如果p3战胜p1，那么p1,p2,p3就是长度为3的回路，与不存在三个选手的回路的假设相矛盾。因此，必定是p1战胜p3，这意味着可以从回路p1,p2,p3..,pk中忽略p2来获得长度为k-1的回路p1,p2,p3...,pk，与最短回路长度为k的假设相矛盾。因此结论是必然存在长度为3的回路。
2.无穷下降法
无穷下降法通常用来证明命题函数P(n)，对于所有正整数k来说，P(k)都为假。如果对于至少一个整数k来说，P(k)为真，那么良序性就蕴含着存在最小的正整数s，使得P(s)为真。这个方法继续寻找满足s’&s的正整数s’，使得对于s’来说，P(s’)为真。所以对于所有的正整数来说，P(n)必定都为假。一般用来证明某些方程没有整数解，例如这个证明了费马大定理中n=4的情形中方程x^4+y^4=z^4没有正整数解。
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：205001次
积分：3885
积分：3885
排名：第3735名
原创：193篇
评论：104条
(3)(1)(3)(4)(3)(9)(1)(2)(7)(12)(16)(20)(17)(2)(14)(2)(2)(10)(2)(13)(12)(5)(5)(19)(15)一维空间--离散数学图灵机文章(一)
&&&&&&&&&&&& &&&
You are all my reasons!　
桃李花林又一在
淫荡一日同风起，风骚直上九万里
仙子凌波微步罗衫飘忽十步一回头
我的最爱：网游，程序，文学
我的分类（专题）
blog名称:一维空间日志总数:163评论数量:248留言数量:33访问次数:496226建立时间:日
计算理论可以追溯到1900年，当时著名的大数学家希尔伯特在世纪之交的数学家大会上给 国际数学界提出了著名的23个数学问题。其中第十问题是这样的：存在不存在一种有限的、 机械的步骤能够判断“丢番图方程”是否存在解？这里就提出来了有限的、机械的证明步骤 的问题，用今天的话说就是算法。但在当时，人们还不知道“算法”是什么。实际上，当时 数学领域中已经有很多问题都是跟“算法”密切相关的，因而，科学的&“算法”&定义呼之 欲出。之后到了30年代的时候，终于有两个人分别提出了精确定义算法的方法，一个人是 图灵，一个人是丘奇。而其中图灵提出来的图灵机模型直观形象，于是很快得到了大家的普 遍接受。& 不知道你是否听说过图灵这个名字。可能有些人知道牛顿，知道爱因斯坦，甚至知道冯 诺依曼，但不知道图灵。然而图灵的贡献绝对不亚于这些科学大师。图灵最大的贡献就是把 算法这样一个基本的、深刻的概念用他的图灵机模型讲清楚了。正是因为图灵奠定的理论基 础，人们才有可能发明20世纪以来甚至是人类有史以来最伟大的发明：计算机。因此人们 称图灵为：计算机理论之父。& 图灵生活的年代经历了第二次世界大战。在二战期间他曾经为英国政府效力成功破译了 德国的密码，因而为英国做出了突出贡献。其实也正是因为二战，英国政府才肯掏钱让图灵 制造最原始的计算机，当然这种计算机是专门用来破译密码用的，而不是我们现在用的通用 计算机。（有一部片子叫《密码迷情》英文名是《enigma》就是根据图灵当时破译德国密码 的故事改编的，大家有兴趣可以去找一找。）& 图灵这个人很古怪，只喜欢自己一个人闷头研究，不喜欢与别人交流。并且据说他还是 一个同性恋者。要知道在当时的英国，同性恋行为可是大逆不道的。最后，在他事业刚刚达 到顶风的时候，他自杀了。为了纪念这个伟大的学者，计算机界设立了最高荣誉奖：ACM 图灵奖。& 图灵机的产生一方面奠定了现代数字计算机的基础（要知道后来冯诺依曼就是根据图灵 的设想才设计出第一台计算机的）。另一方面，根据图灵机这一基本简洁的概念，我们还可 以看到可计算的极限是什么。也就是说实际上计算机的本领从原则上讲是有限制的。请注意， 这里说到计算机的极限并不是说它不能吃饭、扫地等硬件方面的极限，而是仅仅就从信息处 理这个角度，计算机也仍然存在着极限。这就是图灵机的停机问题。这个问题在图灵看来更 加重要，在他当年的论文中，其实他是为了论证图灵停机问题才“捎带手”提出了图灵机模 型的。& 提到了图灵停机问题，我不禁又要提一提哥德尔定理、罗素悖论、康托尔的集合论等 等一系列大事儿。早在19世纪末的时候，康托尔为集合论做了奠基性的研究。要知道，数 学虽然五花八门，但是人们发现，运用集合这个概念可以概括所有的数学，也就是说集合是 一切数学的基础。因而如果为集合论奠定了公理化的基础，也就等于为数学奠定了基础。康 托尔就是做了这方面的贡献。另外，他为了证明实数的个数比自然数多这个结论，发明了一 种被称为“对角线删除”的证明方法。没想到的是，这个方法影响非常深广，直到后来的图 灵停机问题、哥德尔定理其实都是该方法的不同延伸。& 19世纪末的人们忙于为基于集合论的数学建立公理体系大厦。然而就当这座大厦即将 完工的时候，一件可怕的事情发生了，罗素提出来的罗素悖论粉碎了数学家的梦想。关于罗 素悖论的一个通俗化版本是：“村子里有一个理发师，他给自己定了一条规矩：‘不给那些所 有给自己理发的人理发’。现在就要问，这个理发师该不该给自己理发？”。如果你尝试回答 这个问题就会发现奇怪的事情：这个问题本身似乎是不可能的！正是因为这种奇怪的逻辑， 哲学家罗素才颠覆了整个数学大厦的基础！& 因为集合论中存在着矛盾，所以整个数学体系存在着根本性的矛盾，然而具有讽刺意 味的是，数学一直以严格著称！这种感觉就好像正当你得意洋洋的时候有人突然闪了你一个 耳光！人们在一阵慌乱之后开始逐渐稳下阵角寻找避免罗素悖论产生的方法，并总希望通过 细心的选择数学公理能够将类似罗素悖论这样的怪物一劳永逸的排除精确数学体系之外。这 就是后来希尔伯特提出来一套数学纲领的原因，他希望找到一套公理体系能够排除悖论，并 挽救纯粹而美丽无暇的数学。虽然希尔伯特没能完成他的梦想，但他坚信梦想是对的。& 然而，没过多少年，一个名不见经传的年轻逻辑学家哥德尔提出来的定理却彻底粉碎 了希尔伯特的梦。这就是后来著名的哥德尔定理！该定理大致上说：任何一个数学的公理化 体系都不是“完美的”。换个角度说，任何数学公理化系统都是死的，它总需要人为地从外 界注入新的公理进去才能让它日趋完善，而它自己并不能完全自动避免矛盾产生。哥德尔定 理可以说整个扭转了人们的世界观。因为被认为最“完美”最“纯粹”的数学都是不完全的， 那么纯粹完美的世界也应该不存在。哥德尔定理还指出了“理性”和“分析”方法的极限。 这才是后来人们步入到了“综合”时代的部分原因。更有趣的是，哥德尔用来证明他定理的 方法正和康托尔证明实数比自然数多、图灵停机问题以及罗素悖论的方法是一脉相承的。& 所有这些都是20世纪上半个世纪发生的大事，后来发生了什么？计算机出现了、信息 时代来临了，似乎科学技术是万能的，它们总会改善我们的生活，满足我们的欲望。渐渐的， 人们似乎淡忘了图灵、歌德尔、康托尔等等大师们的思想了。然而近年来随着复杂性科学的 研究，人们却又有了重拾这些相对古老而根本问题的迹象了！& 二、图灵机& 下面言归正传，我们开始讲图灵机的概念。我先把图灵机的模型给你，虽然有些无趣， 不过请坚持看下去，我会在下面运用大家比较好理解的形式重新解释的。在这里你仅仅需要 认识它的轮廓。一个图灵机是形如下面的一个装置：& .ü..?..?..?..?..?..& & 这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。（中间那个大盒子）， 内部状态（盒子上的方块，比如A,B,E,H），另外，还有一个程序对这个盒子进行控制。这 个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。& 它工作的时候是这样的：从读写头在纸带上读出一个方格的信息，并且根据它当前的内 部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移 动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。& 具体的程序就是一个列表，也叫做规则表，是这样的：& 当前内部状态s&输入数值i&输出动作o&下一时刻的内部状态s'& B&1&前移&C& A&0&往纸带上写1&B& C&0&后移&A& …&…&…&…& 因此，图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表就可以确 定它下一时刻的内部状态和输出动作了。& 图灵机就是这么简单！不可思议吧？而只要你变化它的程序（也就是上面的规则表）， 那么它就可能为你做任何计算机能够完成的工作。因此可以说，图灵机就是一个最简单的计 算机模型！& 也许，你会觉得图灵机模型太简单，怎么可能完成计算机的复杂任务呢？问题的关键是 如何理解这个模型。& 三、如何理解图灵机？& 1、小虫的比喻& 我们不妨考虑这样一个问题。假设一个小虫在地上爬，那么我们应该怎样从小虫信息 处理的角度来建立它的模型？& 首先，我们需要对小虫所在的环境进行建模。我们不妨就假设小虫所处的世界是一个无 限长的纸带，这个纸带上被分成了若干小的方格，而每个方格都仅仅只有黑和白两种颜色。 很显然，这个小虫要有眼睛或者鼻子或者耳朵等等感觉器官来获得世界的信息，我们不妨把 模型简化，假设它仅仅具有一个感觉器官：眼睛，而且它的视力短得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因而这个方格所在的位置的黑色或者白色的信息就是小虫 的输入信息。& 另外，我们当然还需要为小虫建立输出装置，也就是说它能够动起来。我们仍然考虑最 简单的情况：小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格。& 仅仅有了输入装置以及输出装置，小虫还不能动起来，原因很简单，它并不知道该怎样 在各种情况下选择它的输出动作。于是我们就需要给它指定行动的规则，这就是程序！假设 我们记小虫的输入信息集合为I={黑色，白色}，它的输出可能行动的集合就是：O={前移， 后移}，那么程序就是要告诉它在给定了输入比如黑色情况下，它应该选择什么输出。因而， 一个程序就是一个从I集合到O集合的映射。我们也可以用列表的方式来表示程序，比如：& 程序1：& 输入&输出& 黑色&前移& 白色&后移& 这个程序非常简单，它告诉小虫当读到一个黑色方格的时候就往前走一个方格，当读到 一个白色方格的时候就后退一个格。& 我们不妨假设，小虫所处的世界的一个片断是：黑黑黑白白黑白……，小虫从左端开 始。& 那么小虫读到这个片断会怎样行动呢？它先读到黑色，然后根据程序前移一个方格， 于是就会得到另外一个黑色信息，这个时候它会根据程序再次前移一个方格，仍然是黑色， 再前移，这个时候就读到白色方格了，根据程序它应该后退一个格，这个时候输入就是黑色 了，前移，白色，后移……，可以预见小虫会无限的循环下去。& 然而，现实世界中的小虫肯定不会这样傻的在那里无限循环下去。我们还需要改进这个 最简单的模型。首先，我们知道小虫除了可以机械地在世界上移动以外，还会对世界本身造 文本框:&……文本框:&开始 成影响，因而改变这个世界。比如虫子看到旁边有食物，它就会把那个东西吃掉了。在我们 这个模型中，也就相当于我们必须假设小虫可以改写纸带上的信息。因而，小虫可能的输出 动作集合就变成了：O={前移，后移，涂黑，涂白}。这个时候，我们可以把程序1改为比 如：& 程序2：& 输入&输出& 黑&前移& 白&涂黑& 纸带是黑黑白白黑……，小虫会怎样行动呢？下面的图表示出了这个例子中每一步小虫 的位置（标有圆点的方格就是小虫的当前位置），以及纸带的状况。& 开始：小虫在最左边的方格，根据程序的第一行，读入黑色应该前移。& 第二步：仍然读入黑，根据程序的第一行，前移。& 第三步：这个时候读入的是白色，根据程序的第二行，应该把这个方格涂黑，而没有其他的 动作。假设这张图上方格仍然没有涂黑，而在下一时刻才把它表示出来。& 第四步：当前方格已经是黑色的，因此小虫读入黑色方格，前移。& 第五步：读入白色，涂黑方格，原地不动。& 第六步：当前的方格已经被涂黑，继续前移。& 第七步：读入黑色，前移& 小虫的动作还会持续下去……。我们看到，小虫将会不停的重复上面的动作不断往前走， 并会把所有的纸带涂黑。& 显然，你还可以设计出其他的程序来，然而无论你的程序怎么复杂，也无论纸带子的情 文本框:&……文本框:&……文本框:&……文本框:&……文本框:&……文本框:&……文本框:&…… 况如何，小虫的行为都会要么停留在一个方格上，要么朝一个方向永远运动下去，或者就是 在几个方格上来回打转。然而，无论怎样，小虫比起真实世界中的虫子来说，还有一个致命 的弱点：那就是如果你给它固定的输入信息，它都会给你固定的输出信息！因为我们知道程 序是固死的，因此，每当黑色信息输入的时候，无论如何它都仅仅前移一个方格，而不会做 出其他的反应。它似乎真的是机械的！& 如果我们进一步更改小虫模型，那么它就会有所改进，至少在给定相同输入的情况下， 小虫会有不同的输出情况。这就是加入小虫的内部状态！我们可以作这样的一个比喻：假设 黑色方格是食物，虫子可以吃掉它，而当吃到一个食物后，小虫子就会感觉到饱了。当读入的信息是白色方格的时候，虽然没有食物但它仍然吃饱了，只有当再次读入黑色时候它才会 感觉到自己饥饿了。因而，我们说小虫具有两个内部状态，并把它内部状态的集合记为： S={饥饿，吃饱}。这样小虫行为的时候就会不仅根据它的输入信息，而且也会根据它当前 的内部状态来决定它的输出动作，并且还要更改它的内部状态。而它的这一行动仍然要用程 序控制，只不过跟上面的程序比起来，现在的程序就更复杂一些了，比如：& 程序3：& 输入&当前内部状态&输出&下时刻的内部状态& 黑&饥饿&涂白&吃饱& 黑&吃饱&后移&饥饿& 白&饥饿&涂黑&饥饿& 白&吃饱&前移&吃饱& 这个程序复杂多了，有四行，原因是你不仅需要指定每一种输入情况下小虫应该采取 的动作，而且还要指定在每种输入和内部状态的组合情况下小虫应该怎样行动。看看我们的 虫子在读入黑白白黑白……这样的纸带的时候，会怎样？仍然用下面的一系列图来表示，灰 色的圆点表示饥饿的小虫，白色的圆点表示它吃饱了。为了清晰，我们把小虫将要变成的状 态写到了图的下一行。& 假定它仍然从左端开始，而且开始的时候小虫处于饥饿状态。这样读入黑色，当前饥 饿状态，根据程序第一行，把方格涂白，并变成吃饱（这相当于把那个食物吃了，注意吃完 后，小虫并没动）。& 第二步：当前的方格变成了白色，因而读入白色，而当前的状态是吃饱状态，那么根 据程序中的第四条前移，仍然是吃饱状态；& 第三步：读入白色，当前状态是吃饱，因而会重复第二步的动作。& 文本框:&……文本框:&涂白方格，变成吃饱文本框:&……文本框:&前移，仍然吃饱文本框:&……文本框:&前移，保持吃饱 第四步：仍然重复上次的动作。& 第五步：读入黑色，当前状态是吃饱，这时候根据程序的第二行应该后移方格，并转 入饥饿状态；& 第六步：读入白色，当前饥饿状态，根据程序第三行应该涂黑，并保持饥饿状态（各 位注意，这位小虫似乎自己吐出了食物！）；& 第七步，读入黑色，当前饥饿，于是把方格涂白，并转入吃饱状态（呵呵，小虫把刚 刚自己吐出来的东西又吃掉了！）。& 第八步，读入白色，当前吃饱，于是前移，保持吃保状态。& 这时候跟第四步的情况完全一样了，因而小虫会完全重复5、6、7、8步的动作，并永 远循环下去。似乎最后的黑色方格是一个门槛，小虫无论如何也跨越不过去了。& 小虫的行为比以前的程序复杂了一些。尽管从长期来看，它最后仍然会落入机械的循环 或者无休止的重复。然而这从本质上已经与前面的程序完全不同了，因为当你输入给小虫白 色信息的时候，它的反应是你不能预测的！它有可能涂黑方格也有可能前移一个。当然前提 是你不能打开小虫看到它的内部结构，也不能知道它的程序，那么你所看到的就是一个不能 预测的满地乱爬的小虫。如果小虫的内部状态数再增多呢，那么它的行为会更加的不可预测！& 好了，如果你已经彻底搞懂了我们的小虫是怎么工作的，那么你已经明白了图灵机的工 作原理了！因为从本质上讲，最后的小虫模型就是一个图灵机！& 2、如何理解图灵机模型*& 刚才用小虫说明了图灵机的工作原理，相信你的第一个反映就是，这样的模型太简单了！ 他根本说明不了现实世界中的任何问题！下面，我就要试图说服你，图灵机这个模型是伟大 的！& 首先，我想说的是，其实我们每一个会决策、会思考的人就可以被抽象的看成一个图灵 机。& 文本框:&前移，保持吃饱文本框:&涂白，转入吃饱文本框:&……文本框:&前移，保持吃饱文本框:&……文本框:&后移，变成饥饿文本框:&……文本框:&涂黑，保持饥饿文本框:&……文本框:&…… 为什么可以做这种抽象呢？首先我们可以考虑扩展刚才说的小虫模型。因为小虫模型是 以一切都简化的前提开始的，所以它的确是太太简单了。然而，我们可以把小虫的输入集合、 输出行动集合、内部状态集合进行扩大，这个模型就一下子实用多了。首先，小虫完全可以处于一个三维的空间中而不是简简单单的纸带。并且小虫的视力很好，它一下子能读到方圆 500米的信息，当然，小虫也可以拥有其他的感觉器官，比如嗅觉、听觉等等，而这些改变 都仅仅是扩大了输入集合的维数和范围，并没有其他更本质的改变。同样道理，小虫可能的 输出集合也是异常的丰富，它不仅仅能移动自己，还可以尽情的改造它所在的自然界。进一 步的，小虫的内部状态可能非常的多，而且控制它行为的程序可能异常复杂，那么小虫会有 什么本事呢？这就很难说了，因为随着小虫内部的状态数的增加，随着它所处环境的复杂度 的增加，我们正在逐渐失去对小虫行为的预测能力。但是所有这些改变仍然没有逃出图灵机 的模型：输入集合、输出集合、内部状态、固定的程序！就是这四样东西抓住了小虫信息处 理的根本。& 我们人能不能也被这样的抽象呢？显然，输入状态集合就是你所处的环境中能够看到、 听到、闻到、感觉到的所有一起，可能的输出集合就是你的每一言每一行，以及你能够表达 出来的所有表情动作。内部状态集合则要复杂得多。因为我们可以把任意一个神经细胞的状 态组合看作是一个内部状态，那么所有可能的神经细胞的状态组合将是天文数字！& 似乎你会说，这个模型根本不对，还有很多思维本质的东西没有概括进去。比如记忆 问题，人有记忆，图灵机有么？其实，只要图灵机具有了内部状态，它就相应的具有了记忆。 比如上面讲到的具有饥饿和吃饱两种状态的小虫就会记住它所经历过的世界：如果吃到食物 就用吃饱状态来“记住”吃过的食物。什么是记忆呢？假如你经历了一件事情并记住了它， 那么只要你下一次的行动在相同条件下和你记住这件事情之前的行动不一样了，就说明该事 情对你造成了影响，也就说明你确实记住了它。& 学习的问题反映在模型中了么？学习是怎么回事儿呢？似乎图灵机模型中不包括学 习，因为学习就意味着对程序的改变，而图灵机是不能在运行过程中改变它的程序的。然而， 我们不难假设，你实际上并不能打开一个人的脑袋来看，所以它的实际程序规则你是不知道 的。很有可能一个图灵机的规则没有改变，只不过激活了它的某些内部状态，因而它的行为 发生了本质上的变化，尽管给它相同的输入，它给出了完全不同的输出，因而在我们看来， 它似乎会学习了！而实际上，这个图灵机的程序一点都没变。& 还有很多很多现象似乎都能被图灵机包括，什么是人类的情绪、情感？你完全可以把 它看作是某种内部状态，因而处于心情好的情绪下，你的输入输出是一套规则，而心情不好 的时候则完全是另一套。这仍然没有逃出图灵机的模型范围。& 接下来的问题就是我们人的思维究竟是不是和图灵机一样遵循固定的程序呢？这个问 题似乎初看是不可能的，因为人的行为太不固定了！你不可预言它！然而我会争辩道，无论 如何神经元传递信息、变化状态的规律都是固定的，可以被程序化的，那么作为神经元的整 体：脑的运作必然也要遵循固定的规则也就是程序了。那么，如果是这样，正如图灵相信的， 人脑也不会超越图灵机这个模型，所以，人工智能也必然是可能的！然而，我认为针对这个 问题的答案很有可能没有这么简单，我们将在最后详细讨论这个问题。& 无论如何，我相信你已经能够体会到了，图灵机模型实际上是非常强有力的！& 三、计算& 1、什么是计算& 说了这么多，虽然也许你已经了解到了图灵机的威力，也许还将信将疑，然而，你肯定 仍然看不出来图灵机和计算有什么关系。而实际上，图灵机是一个理论计算机模型，它最主 要的能耐还是在于计算上！所以，下面我们就来看看什么是计算！& 我可以先给出一个很摩登的对计算概念的理解：广义上讲，一个函数变化如把x变成了 f(x)就是一个计算！如果我们把一切都看作是信息，那么更精确的讲，计算就是对信息的变 换！如果采用这种观点，你会发现，其实自然界充满了计算！如果我们把一个小球扔到地上小球又弹起来了，那么大地就完成了一次对小球的计算。因为你完全可以把小球的运动都抽 象成信息，它无非是一些比如位置、速度、形状等等能用信息描述的东西嘛，而大地把小球 弹起来就无非是对小球的这些信息进行了某种变换，因而大地就完成了一次计算！你可以把 整个大地看作是一个系统，而扔下去的小球是对这个系统的输入，那么弹回来的小球就是该 系统的输出，因而也可以说，计算就是某个系统完成了一次从输入到输出的变换！& 这样理解不要紧，你会发现，现实世界到处都是计算了！因为我们完全可以把所有的自 然界存在的过程都抽象成这样的输入输出系统，所有的大自然存在的变量都看作是信息，因 而计算无处不在！也的确，正是采取了这样的观点，国外才有可能发明什么DNA计算机、 生物计算机、量子计算机这些新鲜玩艺！因为人家把DNA的化学反应、量子世界的波函数 变换都看作是计算了，自然就会人为地把这些计算组合起来构成计算机了。然而，似乎我们 的理论家们还在力图证明关于图灵机的某个定理呢，却完全没有意识到计算其实就是这样简 单！& 下面回到图灵机！为什么说图灵机是一个计算的装置呢？很简单，图灵机也是一个会对 输入信息进行变换给出输出信息的系统。比如前面说的小虫，纸带上的一个方格一个方格的 颜色信息就是对小虫的输入，而小虫所采取的行动就是它的输出。不过这么看，你会发现， 似乎小虫的输出太简单了。因为它仅仅就有那么几种简单的输出动作。然而，不要忘了，复 杂性来源于组合！虽然每一次小虫的输出动作很简单，然而当把所有这些输出动作组合在一 起，就有可能非常复杂！比如我们可以把初始时刻的纸带看作是输入信息，那么经过任意长 的时间比如说100年后，小虫通过不断的涂抹纸带最后留下的信息就是输出信息了。那么小 虫完成的过程就是一次计算。事实上，在图灵机的正规定义中，存在一个所谓的停机状态， 当图灵机一到停机状态，我们就认为它计算完毕了，因而不用费劲的等上100年。& 2、计算的组合& 更有意思的是，我们可以把若干个计算系统进行合并构成更大的计算系统。比如还是那 个小球吧，如果往地上放了一个跷跷板，这样小球掉到地上会弹起这个跷跷板的另一端，而 跷跷板的另一边可能还是一个小球，于是这个弹起的小球又会砸向另一个跷跷板……。& 我们自然可以通过组合若干图灵机完成更大更多的计算，如果把一个图灵机对纸带信息 变换的结果又输入给另一台图灵机，然后再输入给别的图灵机……，这就是把计算进行了组 合！也许你还在为前面说的无限多的内部状态，无限复杂的程序而苦恼，那么到现在，你不 难明白，实际上我们并不需要写出无限复杂的程序列表，而仅仅将这些图灵机组合到一起就 可以产生复杂的行为了。& 有了图灵机的组合，我们就能够从最简单的图灵机开始构造复杂的图灵机。那么最简单 的图灵机是什么呢？我们知道最简单的信息就是0和1，而最简单的计算就是对0或1进行 布尔运算。而布尔运算本质上其实就三种：与、或、非。从最简单的逻辑运算操作最简单的 二进制信息出发我们其实可以构造任意的图灵机！这点不难理解：任何图灵机都可以把输入、 输出信息进行01的编码，而任何一个变换也可以最终分解为对01编码的变换，而对01编 码的所有计算都可分解成前面说的三种运算。也许，现在你明白了为什么研究计算机的人都 要去研究基本的布尔电路。奥秘就在于，用布尔电路可以组合出任意的图灵机！& 3、征服无限的方法！& 回忆你小时候是如何学会加法运算的。刚开始的时候，你仅仅会死记硬背。比如你记住 了1+1=2，记住了2+4=6，……。然而无论你记住多少固定数字的运算，你都不叫学会了加 法。原因很简单，假如你记住了n对数的加法，那么我总会拿出第n+1对数是你没有记住 的，因此你还是不会计算。原则上。自然数的个数是无穷的，所以任何两个数的加法可能结果也是无穷的，而如果采用死记硬背的方法，我们头脑怎么可能记住无穷数字的计算法则 呢？但是随着年龄的增长，你毕竟还是最终学会了加法运算！说来奇怪，你肯定明白其实加 法运算并不需要记住所有数字的运算结果，而仅仅需要记住10以内的任意两个数的和，并 且懂得了进位法则就可以了。& 你是怎么做到的呢？假设要计算32+69的加法结果，你会把32写到一行，把69写到 下一行，然后把他们对齐。于是你开始计算2+9=11，进一位，然后计算3+6=9，再计算9+1=10 再进一位，最后，再把计算的这些每一位的结果都拼起来就是最终的答案101。这个简单例 子给我们的启发就是：作加法的过程就是一个机械的计算过程，这里输入就是32和69这两 个数字，输出就是101。而你的程序规则就是具体的把任意两个10以内的数求和。这样， 根据固定的加法运算程序你可以计算任两个数的加法了。& 不知你发现了没有，这个计算加法的方法能够让你找到运用有限的规则应对无限可能情 况的方法！我们刚才说了，实际上自然数是无限的，这样，所有可能的加法结果也是无限的。 然而运用刚才说的运算方法，无论输入的数字是多少，只要你把要计算的数字写下来了，就 一定能够计算出最终的结果，而无需死记硬背所有的加法！& 因而，可以说计算这个简单的概念，是一种用有限来应对无限的方法！我们再看一个 例子：假如给你一组数对：1,2&3,6&5,10&18,36，就这4对，这时问你102对应的数是多 少？很显然，如果仅仅根据你掌握的已知数对的知识，是不可能知道答案的，因为你的知识 库里面没有存放着102对应数字的知识。然而，如果你掌握了产生这组数对的程序法则，也 就是看到如果第一个数是x，那么第二个数就是2x的话，你肯定一下子就算出102对应的 是204了。也就是说，你实际上运用2x这两个字符就记住了无限的诸如1,2&3,6&102,204 所有这样的数对。& 这看起来似乎很奇怪。我怎么可能运用有限的字符来应对无限种可能呢？实际上，当 没有人问你问题的时候，你存储的2x什么也没有，而当我问你102对应的是多少？我就相 当于给你输入了信息：102，而你仅仅是根据这个输入信息102进行一系列的加工变换得到 了输出信息204。因而输入信息就好比是原材料，而你的程序规则就是加工的方法，只有在 原材料上进行加工，你才能输出最终产品。& 这让我不禁想起了专家系统方法。其实专家系统就是一个大的规则库。也就相当于存 储了很多很多的1,2&3,6&5,10这样特殊的规则对。而无论它存储的东西再多，总归会是有限 的，你只要找到一个它没有存储到的问题，它就无能为力了。因而专家系统就会在你问到 102对应是多少的时候失败！如何解决问题？人们想出了很多方法，就比如元规则的方法， 其实元规则就相当于刚才所说的计算加法的程序，或者2x这样的东西。运用元规则的确可 以应对无限种情况了。所以，这就是为什么你问计算机任何两个数相加是多少，它总能给出 你正确的答案的原因，虽然它不必记住所有这些加法对的信息。& 然而仅仅是元规则就能解决所有问题么？& 假如给你三组数对，排列成一个表：& 1,2&3,6&4,8&100,200& 3,9&2,6&8,24&100,300& 1,4&2,8&3,12&100,400& 那么问你在第6行上，3这个数字对应的是多少？我们先要找出第一行的规律是2x没 有疑问，第二行呢？是3x，第三行是4x，那么第6行就应该是7x了，因而在第6行上3 应该对应的是21了！这里跟前面不太一样的是，虽然我们得到了每一行的规则比如第一行 的2x，但是随着行数的增加，这个规则本身也变化了，因而第2行是3x，第3行是4x等等， 因而我们又得到了一个规则本身的规则，即如果行数是n的话，那么这一行的规则就是 (n+1)x。我们显然能够根据输入的n和x计算出数值。把这个道理放到专家系统里面，这种 原理就是元规则的规则，元规则的元规则……，应该是无穷的！然而专家系统本身并不会自动的归纳这些规则，人必须事先把这些元规则写到程序里，这也就是专家系统最大的弊端。 而我们人似乎总能在一些个别的事件中归纳出规则。进一步问，机器可以归纳么？这就相当 于说：可以为归纳方法编出程序么？这也是一个很有趣的问题，下面将要详细讨论！可以设 想，假如我们找到了真正归纳的方法，那么编写出这样的程序，它就会一劳永逸的自己进行 学习归纳了。我们完全再也不用给他编制程序和规则了。这正是人工智能的终极目标！& 4、归纳*& 记得金大侠在他的一本武侠小说：《倚天屠龙记》中曾讲述了这样一段故事：武林泰斗 张三丰在情急之下要把他新创的武功“太极拳”传授给新起之秀张无忌。张无忌除了有一身 精湛的“内功修为”以外还对武学具有极高的悟性。因而当张三丰给他打过一趟太极拳以后， 他就把所有的招式全部记下来了并且当场把所学的太极拳重新再打给张三丰看。在张无忌练 拳的过程中，张三丰反复问他一个问题：“你已经忘掉几招了？”。他的回答令其他人异常不 解，因为他越在那里揣摩太极拳的奥秘，忘记的招数也越来越多。旁边的人不明白，这样的 学法忘的这么快，怎么可能学会武功呢？然而，没过多长时间，张无忌说已经忘掉了所有的 招式。张三丰笑着说：“不错，你终于学会了‘太极拳’”。& 从这个例子中，我们看到了什么？张无忌之所以能学会太极拳，正是因为他已经能够从 具体的一招一式之中抽象出了更高一层次的武学规律，因而，当他把所有的有形的武功招数 都忘记的时候，已经掌握了太极拳的精髓。而太极武功讲究的就是借力打力，以柔克刚。说 白了就是事先并没有固定招式存在，而等到敌人向我进攻的时候我再动态的生成破解的招 术。& 用到图灵机模型中，我们不难发现，如果把具体的武功招术比喻成一些输入，而应对招 术比喻成图灵机的输出，那么太极所讲究的借力打力、以柔克刚的方法其实就是类似上节讲 过的2x这样的图灵程序！因而张无忌学太极拳的过程就是从特殊的输入输出提升到了一般 的算法的过程。也可以说，张无忌运用了归纳学习法！& 然而，仔细观察上一节的叙述，我们会发现。虽然图灵机能够将2x这样的法则计算得 出结果，但是抽象出2x本身并不是机器自动产生的，而是需要我们外在的人编程进去。那 么，面对这样的问题，究竟图灵机能不能像张无忌一样进行归纳思维呢？& 可以设想，如果计算机真有了张无忌那两下子，我们人类可要省事儿多了！我们甚至不 需要为计算机编程序，它就会自动的从若干个具体事例中归纳出一般的通用规律来。然而， 究竟计算机能不能具有真正的归纳能力呢？让我们来仔细考虑一下这个问题。& 我们说如果计算机能自动归纳，也就意味着我们可以为归纳方法来编写一段程序P。这 个程序可以理解为输入的是一些特殊的数对，输出的是能够生成这些数对的程序。也就是说 输入具体的“招术”，输出的是这些“招术”的一般规律。如果说程序P真正可以自己归纳， 那么P就必然可以归纳出所有的规律。我们已经讨论过了，其实任何一个程序都能够被看 作是对输入的一个变换而得到输出。那么程序P自然也是。假设这些对子(a,b),(c,d),(e,f),…… 都是程序P的输入输出对，那么我们挑选出前1000个（总而言之是足够多的对子）。把这 1000个特殊情况输入到P中，那么P就应该能够产生这些对子的共性，也就是P自己这个 程序了！换句话说，程序P产生了它自己，P自己把自己给归纳出来了！这似乎陷入了怪圈 之中！另外，我们人类设计出来P，如果P可以归纳所有的规律，那么P能否也能归纳出“人 归纳P”本身这个规律呢？仍然是怪圈问题！这样的问题似乎还有很多。反过来讲，如果假 设归纳出所有规律的程序P不存在，那么为什么我们人类总能归纳出规律呢？什么样的具 体问题是可归纳的，什么问题是不可归纳的？然而这些看起来非常重要的问题在目前还没有 统一的答案！& 我们还将会看到很多问题都涉及到逻辑中的怪圈，而由于计算理论已经触及了逻辑、信 息的根本，所以把一些问题引向逻辑怪圈并不奇怪。
&回复:离散数学图灵机文章(一)
笨蛋(游客)发表评论于 17:32:21
你很厉害，真的很厉害
我相当佩服你
你让我真正明白了图灵机
谢谢 真佩服你
个人主页 |
发表评论：
Sponsored By W3CHINA Blog 0.8&Processed in 0.032 second(s), page refreshed}