算法图灵机及可计算性理论

图灵机与可计算性理论图灵对计算本质的揭示在哥德尔研究成果的影响下20世纪30年代后期，图灵﹙A．M．Turing﹚从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识。根据图灵的研究，直观地说，所谓计算就是计算者﹙人或机器﹚对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。图灵用形式化方法成功表述可计算这一过程的本质。图灵机〔TuringMachine)有限状态控制器1111110000000BBB1…………读写头当图灵机的读写头扫描到一个格的字符时，根据控制器的当前状态和扫描到的字符，决定图灵机的动作。包括3方面：(1)控制器进行状态转换〔决定下一状态〕；(2)读写头在当前格写上新的字符；(3)决定读写头向左或向右移动一格。图灵机〔TuringMachine)TM运行由确定:当前状态为q，所读字符为s，读写头不变，，，读写头左移一格，s不变，，读写头右移一格，s不变，无定义，那么停机Church-Turing论题：但凡可计算的过程都可用图灵机实现其他图灵机模型“实际的〞的图灵机模型单带图灵机〔1TM〕多带图灵机〔kTM〕随机存取机〔RAM〕“实际的〞单位时间内完成的工作量有一个多项式上界所有“实际的〞计算模型多项式时间等价其他图灵机模型但凡能用算法方法解决的问题，也一定能用图灵机解决；但凡图灵机解决不了的问题，任何算法也解决不了。从理论上，从根本上说，一个算法就是一个确定的、对任意输入都停机的图灵机。可计算函数与可计算语言的定义同图灵机的停机问题有密切的关系。设L为一个语言，假设被一个图灵机M接受，那么称L为一个递归可枚举语言；假设L被一个图灵机M接受，且对任意输入串，M都停机，那么称L为一个递归语言。设为一个整函数，若存在图灵机M实现f的计算功能（其中，对某些输入M可能不停机），则称f为一个部分递归函数；若存在图灵机M实现f的计算功能，且对于f任意一组输入，M都能停机，称f为一个完全递归函数。一个函数〔语言〕是可计算函数〔语言〕当且仅当它是一个完全递归函数〔递归语言〕。一个函数〔语言〕是局部可计算的当且仅当它是一个局部递归函数〔递归可枚举语言〕。对于可计算函数，可以设计算法进行计算。对于每一个输入，算法都能终止，并输出计算结果。多带图灵机确定的图灵机是现代电子计算机的理论模型。一个对任意输入都停机确实定图灵机在多项式时间内可解的问题，必然存在多项式时间复杂度的计算机求解算法。不确定的图灵机只是一种理论上的计算模型。不确定图灵机可解的问题，虽然也可以用确定的图灵机求解，但时间上的消耗〔或说求解步数〕是不一样的。用不确定的图灵机以多项式时间界可求解的问题，用确定的图灵机不能保证在多项式时间界内可求解，但用确定的图灵机以指数时间界是肯定可以求解的。用确定的图灵机以多项式时间界可解的问题称为P类问题；用不确定的图灵机以多项式时间界可解的问题称为NP类问题。确定的图灵机可以看作不确定的图灵机的一种特殊情形，因此这两个问题集合之间存在子集关系，即。现在的问题是：P是NP的真子集吗？换个提法：是否如果，即用不确定的图灵机以多项式时间界可求解的问题，也都存在多项式时间界确实定的图灵机求解算法，这就意味着可以用现代电子计算机在多项式时间界内求解。这个问题引起了许多计算科学家和计算机科学家的极大兴趣，因为大量有实际应用背景的问题〔其中许多都可以归结为图论或最优化理论问题〕都可以在多项式时间界内用不确定图灵机求解〔而又未找到多项式时间复杂性的计算机算法〕。另一方面，自这个问题提出已经经历40多年，虽然许多专家和学者做了大量的工作，却一直未能得到肯定或否认的结果。美国的Ｃｌａｙ数学研究所于2000年5月24日在巴黎法兰西学院宣布设立100万美元奖金，征解“NP=P?〞问题，而且把这个问列位该研究所悬赏征解的七个问题之首。NP=P?计算机科学王冠上的明珠由我国118位科学家〔其中有25位中国科学院院士〕合作编写的《21世纪100个科学难题》〔吉林人民出版社，1998年6月出版〕一书也把这个问题列入其中。“千僖难题〞之一：P〔多项式算法〕问题对NP〔非多项式算法〕问题“千僖难题〞之二：霍奇(Hodge)猜测“千僖难题〞之三：庞加莱(Poincare)猜测“千僖难题〞之四：黎曼(Riemann)假设“千僖难题〞之五：杨－米尔斯(Yang-Mills)存在性和质量缺口“千僖难题〞之六：纳维叶－斯托克斯(Navier-Stokes)方程的存在性与光滑性“千僖难题〞之七：贝赫(Birch)和斯维讷通－戴尔(Swinnerton-Dyer)猜测91、朗兰兹纲领

92、球堆积问题

93、相变的数学理论

94、p－np问题

95、超级计算理论

96、庞加菜猜测及低维拓扑

97、黎曼猜测

98、中华民族及现代人类的起源

99、人类基因组研究中的社会学、伦理学和法律问题100、物质和精神的关系问题

40多年来，许多计算机科学家对“NP=P?〞问题的求解做出了大量工作。虽然未得到最终解答，但也取得了许多颇有理论价值的成果，其中最具代表性的成果是关于NP-完全问题的理论。由PNP知，前面所列举的P类问题也是NP类问题。但对一些NP类问题，这些NP类问题是否属于P类，至今尚不知道。问题1命题演算合取范式的可满足性问题〔CNF的SAT问题〕。命题公式是由命题变元和逻辑运算符组合而成的逻辑表达式。合取范式〔简记为CNF〕是命题公式的一种标准形式：式中只有合取〔〕、析取〔〕和否认〔〕三种运算符，而且否认运算只能出现在命题变元的前面；整个逻辑表达式是一个合取式〔即最外层运算都是合取运算〕，每个合取项是一个析取式，每个析取项是一个命题变元或命题变元的否认。对于给定的一个命题演算合取范式，如果存在对〔式中出现的〕各个命题变元的一个指派，使得该合取范式的值为真〔T〕，那么称该合取范式是可满足〔SAT〕的。否那么说该合取范式是不可满足的。

TF该合取范式是可满足的多项式规约与NP完全问题的根本理论NPC几个结论：关于P、NP和NPC的关系〔假设NPP)1971年，S.A.Cook证明布尔表达式的可满足性问题是一个NPC问题，从而肯定地答复了NPC问题的存在性。随后，通过多项式归约，人们又找出了许多NPC问题。NP完全问题的研究是人们试图答复这个重大的计算科学难题所做的第一种系统性的探索。主要研究工作可以归纳为3个方面。(1)对某个NPC问题设计出〔确定的〕多项式时间界算法。如果这个工作取得成功，那么就证明了NP=P；(2)证明某个NPC问题不存在〔确定的〕多项式时间界算法。如果这个工作取得成功，那么就证明了NPP；(3)通过多项式归纳等手段继续挖掘出一些NPC问题，扩大NPC问题的范围。(1)、(2)两方面的研究工作是根本性的，而且这两方面的工作，最多只有一个方面存在通向成功之路。第(3)方面的工作不是根本性的，这方面工作的作用在于为第(1