level 9
1976 Michael O. Rabin and Dana S. Scott——非确定性有限状态自动机理论的开创者＜本文发表于: 相约加拿大:枫下论坛 www.rolia.net/forum ＞Michael O. Rabin and Dana S. ScottCitationFor their joint paper "Finite Automata and Their Decision Problem," which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field. ----------------------------------------------------------------
2007年05月12日 15点05分
1
level 9
1976 Michael O. Rabin and Dana S. Scott——非确定性有限状态自动机理论的开创者 Michael O. Rabin and Dana S. Scott Citation For their joint paper "Finite Automata and Their Decision Problem," which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field. ----------------------------------------------------------------
2007年05月12日 15点05分
2
level 9
这样，当x为100位的数时，x2为200位的数，y则为这200位的中间100位所组成的数。由x算y是容易的，而由y求出x 则非常困难，因为可能的x非常之多。正是这个问题促使拉宾进一步研究计算任务的最小计算量这一一般性问题，也就是计算的固有难度问题，从而成为最早研究计算复杂性问题的先驱之一。1959年和1960年，拉宾在耶路撒冷先后发表了有关此问题的两篇论文，即“计算速度和递归集合的分类”（Speed of computation and classification of recursive sets, 3rd Convention of recursive sets, Tech. Rep. No.1, O. N. R.,Jerusalem, 1960）。论文虽然没有用“计算复杂性”这个名词而用了“计算速度”和“计算难度”这类名词，但学术界公认这两篇论文是研究计算复杂性的最早、最权威的论文中的两篇，对1964年正式提出“计算复杂性”这一术语的哈特马尼斯（J. Hartmanis）和斯特恩斯（R. E. Stearns, 这两人是1993年图灵奖获得者）以及计算复杂性理论的另一奠基人布卢姆（M. Blum,1995年图灵奖获得者）都曾产生过深刻影响。其中布卢姆正是听了拉宾的有关演说才开始研究计算复杂性并完成其博士论文的。拉宾的研究成果在一定程度上改变了人们的研究方向。例如，波兰数学家普里斯伯克（M. Presburger）在1930年于华沙举行的一次国际数学家会议上所发表的论文中提出了这样一个命题：只包括自然数相加运算的数学系统是完备的，也就是说这样的系统在图灵机上都是可计算的。因此这被称为普里斯伯算术系统，不少计算机科学家试图编写出能证明这个系统中的定理的计算机程序。但拉宾指出，这是极其困难而无法实现的。对于只有100个符号的这样的系统，即使是1万亿台每秒运行1万亿次的计算机，也要运行1万亿年才能得出结果！1974年在斯德哥尔摩的IFIP大会上他作了一次学术演讲，公布了他和耶鲁大学的费歇尔（M. Fisher）的这项研究成果，宣称“这就是通向人工智能的理论障碍”。拉宾演说那天，正好是美国总统尼克松因水门事件被迫宣布辞职这一天，拉宾原以为代表们都去看尼克松演说的电视转播而不会有多少人来听讲，却不料演说一开始人们就潮水一样涌了进来，对演说的反应十分强烈，拉宾讲完以后人们在麦克风
前排
成长队向他提问。对于从事普里斯伯格系统研究的许多人来说，他们听了拉宾演说以后的感觉是非常难受，似乎“世界末日”到了似的。但拉宾本人则并不悲观，他认为应该放弃的只是以完全确定的方式去获得结果，这种结果可能出错，然而出错的可能性微乎其微，也就是说可以把概率算法（probabilistic algorithm,或叫随机算法，randomize algorithm）用到这类问题中来，这是拉宾的又一个贡献。所谓概率算法，就是带有随机操作的一类算法。这种算法在计算的某一步或某些步产生符合规定要求的随机数，然后根据产生出的随机数决定下一步的计算。例如，在计算的某一步有两种选择：执行A或执行B。此时随机产生一个0或1。若产生的是0则执行A，若产生的是1则执行B。这相当于根据掷一枚硬币的结果（正面或反面）决定下一步的计算。将概率的思想用到算法中始于数值计算，在计算方法中通常称作蒙特卡罗法，是在20世纪40年代中提出的。它的基本思想是建立概率模型，通过统计模拟或抽样得到问题的近似解。通常要求计算结果的期望值等于问题的精确解，并且计算误差的期望值随可供使用的时间增加减小。近20年来概率算法在非数值计算中得到很好的应用。例如，已经设计出关于排序和搜索、素数判定、有限域上的多项式分解和求根、字符串的模式匹配等方面的有效概率算法。概率算法同样也应用到并行计算中，得到概率并行算法。 ＜ r o l i a. n e t ＞利用这种概率算法的思想拉宾在1974年斯德哥尔演说时就已有了萌芽，但还不够成熟。第二年休假时他去了麻省理工学院，得知了加里.米勒（Gary Miller）的研究工作。米勒证明，利用著名的黎曼假设（G. F. B. Riemann，1826-1866，德国的数学家兼物理学家），可以用一般的确定性算法判断很大的数是否是素数。拉宾利用米勒的研究结果和数论中关于素数密度的理论，终于在1976年提出了一个判定素数的概率算法，取得了极大成功，这个算法的理论根据是：当n是合数时，在1到n-1的整数中有一半以上是n为合数的“见证人”。算法的基本做法是：随机地产生一个1与n-1之间的整数b，检查b 是否是n 为合数的“见证人”。若b是“见证人”，则计算结束并得出n 为合数的结论；否则重复这个过程。至多进行k次，若产生的k个随机数b都不是n 为合数的“见证人”，则得出n为素数的结论。算法所需要的时间为O（log3n）。当计算的结果是n为合数时，结果肯定是
正确的
。但是，“n为素数”的结果有可能是错误的。此时n 为合数的概率，即得出错误的概率不超过1/2k。当k 足够大时，这是一个很小的数。譬如，取k=10，错误的概率小于0.001。这已经是在实验中不大可能发生的事件了。实践表明，算法在实际使用中几乎不会给出错误的结论。
2007年05月12日 15点05分
4