第2章可计算性理论基础.doc

第2章 可计算性理论基础
可计算性理论 (computability theory) 是研究计算的一般性质的数学理论，也称算法理论或能行性理论. 可计算理论的重要课题之一就是通过建立计算的数学模型给出“计算”这一直观概念的数学描述，并明确区分哪些是可计算的，哪些是不可计算的.
“计算”是人类基本的思维活动和行为方式, 也是人们认识世界与改造世界的基本方法. 随着计算机的诞生和计算机科学技术的发展, 计算技术作为现代技术的标志, 已成为世界各国许多经济增长的主要动力, 计算领域也已成为一个极其活跃的领域. “计算”作为一门学科是在上个世纪末才为人们真正认识的，这要归功于美国计算机学会（简称ACM）和美国电气和电子工程师学会计算机分会（简称IEEE-CS）组成的联合攻关组成员的艰苦卓绝的工作 Denning P J, et al. Computing as a discipline. Communications of the ACM [J]. 1989, Vol.32(1).
. 目前，计算学科正以令人惊异的速度发展, 并大大延伸到传统的计算机科学的边界之外, 成为一门范围极为宽广的学科 董荣胜, 古天龙. 计算机科学技术与方法论 [M]. 北京: 人民邮电出版社, 2002.
. 如今, “计算”已不再是一个一般意义上的概念, 而是“各门科学研究的一种基本视角、观念和方法, 并上升为一种具有世界观和方法论特征的哲学范畴” 郝宁湘. 计算: 一个新的哲学范畴. 哲学动态 [J]. 2000年第11期.
.
可计算性理论是计算机软件与理论的重要组成部分之一，也是计算机科学的理论基础. 20世纪30年代图灵在可计算性理论方面取得的研究成果，对后来出现的存储程序计算机 (即冯·诺伊曼型计算机) 的设计思想产生了重要影响. 目前，可计算性理论的基本概念、思想和方法已被广泛应用于计算机科学的各个领域，如算法设计与分析、计算机体系结构、数据结构、编译方法与技术、程序设计语言语义分析等.
在本章中, 我们不仅能了解到计算概念的形成与发展, 弄清计算的本质, 而且能感受数学的魅力和数学家们在建立可计算性理论基础过程中所展现出的聪颖与智慧. 通过本章的学习, 要充分认识可计算性概念本质, 深入理解可计算性概念数学表示和定义的基本思想方法, 初步弄清各类可计算性函数之间的关系, 重点掌握递归函数的基本概念与基本性质.
§1 计算概念的形成与发展
计算概念的形成与发展经历了漫长的历史，它是计算科学思想史研究的主要线索之一. 尽管目前我们还无法考证人类究竟是从什么时期开始计数和进行数的运算，但从现有的考古发现和有文字记载的史料中，我们仍然可以捕捉到早期人类在计算领域取得的成就以及从中体现出的人类智慧. 在《力量—改变人类文明的50大科学定理》一书中，作者将公式“1+1=2”列为之首是有充分道理的，人类对数的可加性的发现和推广应用正是数学科学的全部根基 李啸虎, 田廷彦, 马丁玲. 力量—改变人类文明的50大科学定理[M]. 上海: 上海文化出版社, 2005.
. 计算概念的形成与发展目前尚无系统的研究结果，我们不妨从以下几个方面加以认识.
一、计算概念的初识—抽象思维的进步
人类的计算是伴随着人类文明的起源和进步而产生和发展的. 最初计算的表现形式是“计数”，“数”的概念是人们通过计数认识的. 在漫长的进化和发展过程中，人类的大脑逐渐具有了一种特殊的本领，这就是把直观的形象变成抽象的数字，进行抽象思维活动. 正是由于能够在“象”和“数”之间互相转换，人类才真正具备了认识世界的能力. 从“计数”到“数”的概念形成，是人类在抽象思维领域中迈出的辉煌一步.
考古发现最早人类留有计数痕迹的东西是一些带有刻痕的骨头，这些骨头出土于欧洲西部，距今已有2万至3万年的历史，当时生活在这一地区的是奥里尼雅克（Aurignacian）时期（法国旧石器时代前期）的克罗麦昂（Cro-Magnon）人. 把形象事物以刻痕的形式表示并记录在骨头上，表明当时的人类已或多或少地认识了“映射”的概念，而这一概念却是数学科学中最为基本也是十分重要的一个概念. 人类最早使用计数系统的证据，是1937年在捷克斯诺伐克（Czechoslovakia）出土的2万年前的狼的颚骨，颚骨上“逢五一组”，共有55条刻痕. 这样的计数方式被人类延用至今，“正”字计数法便是例证.
研究地球的构造和历史的地质学家和观察人类的体质和社会特征的人类学家向我们提供了早期人的种种遗迹，他们通过地层里各时期的堆积物的相对位置来估测远古至今各个时代的顺序，并以此来探索人类科学的起源 丹皮尔著, 李珩译. 科学史及其与哲学与宗教的关系（第四版）[M]. 北京: 商务出版社, 1987.
. 另一方面，研究科学思想史的科学家们则倾向于从自然科学最初形成的学科体系中寻觅人类科学思想史的根源，认为：“古代科学最先发展起来的是天文学与数学，其次是力学，此外还有一些生物学与医学方面的研究，因为这几个学科同古代人类的生产与生活关系最为密切.” 林德宏. 科学思想史[M]. 南京: 江苏科学技术出版社, 1985.
然而，如果没有更早期人类对数的认识、数的表示和数的计算等方面取得的成就，无论是在古埃及通过人们反复测量土地诞生的最初的几何学，还是古巴比伦人最早认识的“金星运动周期”和对日食、月食的预报，都是不可能的，这是一个可想而知的事实. 令人遗憾的是，在如今的诸多科学史和科学思想史研究的著作中，这一点往往被忽视了.
二、计算概念的定义—计算本质的揭示
在数学科学领域，与“计算”密切相关的概念之一是“算法”，任何计算都是在一定算法支持下进行的. 公元前3世纪，古希腊和中国的数学家就有了算法的概念，象当时的欧几里得辗转相除法就是最好的例子. 大约在公元9世纪初期，阿拉伯著名数学家、天文学家和地理学家花剌子密就给出了现在人们所熟悉的自然数运算规则. 在一个相当长的时期里，人们把“确定关于数学对象（如整数、实数、连续函数等）的各种命题是否正确”作为数学的基本任务. 随着社会的发展以及生产实际的需要，人们逐步开始关心另一类数学任务，“其中之一是在数学发展早期就被认为有极大的重要性，而且至今还在产生着具有重大数学意义的问题，即解决各种问题的算法或能行的计算过程的存在性问题.” 戴维斯著, 沈泓译. 可计算性与不可解性 [M]. 北京: 北京大学出版社, 1984.
然而，要想真正解决这一问题，就必须对“计算”的概念有一个清楚的认识. 到了20世纪30-40年代，一些著名的数学家几乎同时完全独立地给出了相当于能行可计算函数概念的各种确切定义，其中包括Church的-可定义性概念 Church A. The Calculi of Lambda-conversion [M]. Princeton : Princeton University Press, 1941.
，Herbrand-Gödel-Kleene的一般递归性概念 Kleene S C. General Recursive Function’s of Natural Numbers. Mathematische Ann.[J]. 1936 (112): 727-742.
，Turing的可计算性概念 Turing A M. On Computable Numbers, with an Application to the Entscheidungs problem. Proceedings of London Mathematical Society [J]. 1936-1937(45-46): 230-256, 544-546.
等, 经证明，这些形式上完全不同的概念是等价的. 随着计算机的出现和计算机程序设计语言的发展，到了20世纪50-60年代，人们又从不同的角度给出了可计算性函数的一些定义，其中有基于基本字符集算法的Markov可计算函数，以及基于URM理想计算机的Shepherdson-Sturgis可计算函数等. 同样，后两者所描述的可计算函数类与前面所提到的是相一致的 Cutland N. Computability-An introduction to recursive function theory [M]. London: Cambridge Uni. Press, 1980.
.
三、计算概念的发展—计算方式的进化
人们在计算领域的探索和追求，导致了计算工具的发展，而计算机工具的发展，特别是电子计算机的出现以及它在各个领域的广泛应用，又促进了计算方式的不断进化. 人类的计算方式已由早期的手工和机械方式，进化到了现代的电子计算方式. 计算理论如何发展，计算方式如何进一步演变，是当今人类十分关注的问题. 20世纪90年代，美国计算机科学家Adleman博士在美国《科学》杂志上发表文章，针对组合数学的有关问题，提出了分子计算模型，即DNA计算模型，并以解决7个结点的Hamilton问题为实例，成功地在DNA溶液的试管中进行了运算实验 Adleman L. Molecular computation of solutions to combinatorial problems. Science[J]. 1994(266-11): 1021-1024.
. 与此同时，量子计算在理论上取得重大进展. 量子计算概念是由美国阿冈国家实验室的Paul Benioff在20世纪80年初提出的 Benioff P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines, Journal of Stat. Phys.[J]. 1980(22): 563-591.
. 到了1994年，Bell实验室的应用数学家Peter Shor于当年IEEE基础计算理论年会发表突破性工作——快速整数因数分解方法 Shor P W. Algorithms for quantum computation: discrete log and factoring. Proc. of the 35th Annual Symposium on Foundations of Computer Science ( IEEE Computer Society Press, Los Alamitos, CA), 1994: 12.
，使量子计算的潜在应用实力迅速引起广泛关注. 虽然DNA计算和量子计算目前在理论上尚在雏形，但是我们相信，随着历史的前进和人类科技的进步，人们在新型计算机理论研究与应用方面必将取得辉煌的成就, 这些成就将表明：人类在计算领域的探索是永无止境的，其前景是广阔的.
在本章接下来的小节和段落中，我们将从基于URM理想计算机的Shepherdson-Sturgis可计算性函数描述和Herbrand-Gödel-Kleene一般递归函数的定义两个方面来介绍可计算性理论的基本知识.
§2 算法与能行过程
“计算”是解决问题的最基本手段. 随着计算机科学与技术的发展，“计算”的内涵与外延均发生了巨大的变化，其应用范围涉及到了社会发展的各个领域. “计算”离不开计算的规则与方法，正确的计算规则建立与可行的计算方法设计是正确地解决问题的关键所在. 这其中便涉及到“算法”的概念.
一、算法概念的由来
“算法”在中国古代文献中称为“术”，最早在《周髀算经》、《九章算术》等数学名著中均有充分体现，如《九章算术》中给出的四则运算，求最大公约数、最小公倍数、开平方根、开立方根的方法，求素数的埃拉托斯特尼筛法以及线性方程组求解方法等等，都是为现代人所熟悉的算法.
现代人们普遍使用的英文算法Agorithem一词与阿拉伯数学家花剌子密以及他在代数和算术领域作出的重要贡献密切相关. 花剌子密是生活在8世纪末9世纪初波斯的一位数学家、天文学家及地理学家，也是当时巴格达智慧之家的学者. 花拉子米在数学领域最主要贡献是他在9世纪30年代完成的著作《代数学》，该书首次系统地给出了解决一次方程及一元二次方程的理论与方法，大为扩阔了此前的数学概念，为数学的发展开辟了一条新路径. 正是因为在代数领域的特殊贡献，是他获得了“代数创造者”的殊荣，这一美誉与较之早500多年的古希腊数学家丢番图所获得的“代数之父”美称齐名. 花剌子密在数学领域的另一项重要贡献是关于“算术”的. 在825年他所著的《印度数字算术》一书中，采用了印度-阿拉伯数字系统，即十进制进位制的记数系统， 并给出了数的运算规则. 花剌子密在印度数字方面的著作被翻译成拉丁文，并在中世纪时传入中东和西方，对西方中世纪的科学发展起了重要的作用. 《印度数字算术》的拉丁语翻译是“Algoritmi de numero Indorum”，而花剌子密的拉丁文音译则为Algorithm，其中包含了“花剌子密”运算法则之意，此便是英文中“算法”一词的由来. 如今Algorithm已由一个数学家名字的音译变成了一个十分重要的数学概念.
二、算法概念的描述
迄今为止，尚无算法概念的确切定义，这是因为几乎所有问题的解决方法都可由所谓的算法来描述. 面对问题的多样性和复杂性，当我们试图用语言对“变化莫测”的算法给出一个系统而又明确的定义的时候，总有“此消彼长”或“顾此失彼”的感觉. 对此，人们通常以“共性”的特征给出算法的一般性描述，而在特定的学科或应用领域将相关的算法概念具体化.
算法（Algorithm）是解决一类问题方法，可以理解为由基本运算及规定的运算顺序所构成的完整和有限的解题步骤. 算法的执行过程是针对一类问题中的特例而进行的，即能够对一定规范的特定输入，在有限时间内获得所要求的输出结果，从而达到解决问题的目的.
算法的表示方法很多，通常有自然语言、伪代码、流程图、程序设计语言、控制表等. 用自然语言描述算法往往显得冗长且容易引起歧义，因此很少用于在技术层面上较为复杂的算法描述；伪代码、流程图和控制表等以结构化的方法来表示算法，可以避免自然语言描述中普遍存在的二义性问题，因而是算法表示的常用工具；用程序设计语言的主要目的就是通过对算法进行编程使之在计算机上得以实现.
在实际应用中，算法应具有以下几个方面的特征:
（1）输入项：一个算法有0个或多个输入，是算法执行的初始状态，一般由人为设定. 0输入的情形通常发生在算法的初始状态由算法本身来设定的情况下.
（2）输出项：一个算法必须有一个或多个输出，以反映算法对输入数据加工后的结果. 没有输出的算法是毫无意义的.
（3）明确性：算法的描述必须无歧义并且每一步骤都有确切的定义，以保证算法的实际执行结果是正确的并能符合人们的希望和要求.
（4）可行性：也称有效性或能行性. 算法中描述的任何计算步骤都是通过可以实现的基本运算的有限次执行来完成的，或从直观上讲，每个计算步骤至少在原理上能由人用纸和笔在有限的时间内完成.
（5）有穷性：算法有穷性是指算法的执行过程必须在有限的步骤和时间内终止.
注意：满足前四个特征的一组指令序列在实际应用中不能称为算法，只能称为计算过程. 例如：计算机的操作系统就是一个典型的计算过程，操作系统用来管理计算机资源，控制作业的运行，没有作业运行时，计算过程并不停止，而是处于“等待”状态.
在计算机应用技术领域，算法通常是针对实际问题而设计并且通过编程的手段实现的，其目的是运用计算机解决实际问题，在此情况下，一个无休止运行而无结果的算法是毫无意义的. 因此，在计算机应用领域，掌握算法分析与设计的理论与方法是十分重要的. 一方面，要求我们针对实际问题设计出正确的算法: 如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题; 另一方面，又要求我们学会选择和改进已有的算法: 同样的问题可以有不同的算法，算法的优劣可以用空间复杂度与时间复杂度来衡量，不断提高算法的效率始终是人们不懈努力的追求. 随着存储技术的发展，最能反映算法效率的时间复杂度已成为人们在算法设计与分析过程中关注的最主要方面之一.
注意: 算法设计与分析已形成一套较为完整的理论与方法体系, 对于从事计算机应用与开发的工作和技术人员来说, 这些理论与方法是必须掌握的. 目前有大量关于算法设计与分析的文献、专著和教材，然而作为算法设计与分析的基础，我们必须首先要弄清楚的问题是：计算的本质是什么？“可计算”的确切定义是什么？究竟哪些问题是可计算的？这便是“可计算性理论”要回答的问题.
三、能行过程与可计算性
在数学与计算机科学中，算法又可以说成是一个“能行过程”(effective procedure) 或“能行方法”(effective method). 能行过程是针对“问题”的，通常的说法是“解决某某问题的能行过程”.
解决问题的过程是一个问题状态变化的过程，如果我们用参数的形式来描述问题的状态，那么解决问题的过程就可以看成是一个参数变化的过程. 解决问题开始时的状态称为“初始状态”，初始状态的参数称为“输入参数”；解决问题结束时的状态称为“结果状态”，结果状态的参数称为“输出参数”或“输出结果”.
对一个问题而言，其“输出结果”与“输入参数”之间的关系应该是明确的. 但允许有下述情形: 有这样的“问题”，它们对输入范围内的有些“输入参数”（有效输入）有明确的“输出结果”，而对有些“输入参数”（无效输入）则没有明确的“输出结果”，甚至“结果”根本就不存在. 对这类“问题”，我们在考虑其能行解决方法时，只要针对有效的输入便可.
如果存在解决某问题的能行过程，那么该问题称为是“可解的”或“可计算的”.
注意：如果要说明一类问题是 “不可解” 或 “不可计算的”，那么就必须给出该类问题不存在能行过程的证明.
我们将通过实例进一步认识“能行过程”的概念.
例2-1. 设和是两个正整数，且. 求和的最大公因子的欧几里得算法可以通过下列过程表示:
步骤1. 以除得余数. //求余数
步骤2. 若, 则输出答案，过程终止; 否则转到步骤3. //判断余数是否为0
步骤3. 把的值变为, 的值变为，重复上述步骤. //变换参数值
分析：上述过程由3个步骤组成，输入参数为正整数和；每个步骤的描述是明确的并且可以证明过程终止时输出数据为和的最大公因子；过程的每一步骤都是可以通过一些可实现的基本运算（判断）完成；整个过程经过有穷步后终止. 因此，求和的最大公因子的欧几里得算法是一个能行过程. 因此，求和的最大公因子问题是可计算的.
例2-2. 考虑函数
(2.1)
绝大多数数学家会接受是合法定义的函数，同时也存在能行的过程逐位生成小数点后面的数子Cutland N. Computability-An introduction to recursive function theory [M]. London: Cambridge Uni. Press, 1980: 69.
. 用表示小数点后面第位数字，作为计数器，则可以采用下面的过程来计算：
给定，首先令，计数器，参数.
步骤1. 计算. //求小数点后第位数字
步骤2. 如果，则；否则. //计数器逢“7”加1，否则清0
步骤3. 如果，则输出，过程终止；如果，则重复上述步骤.
分析：上述过程同样由3个步骤组成，对给定的输入，如果小数点后面有个连续的7，那么过程一定会在有限步终止并输出. 问题是：如果小数点后面没有个连续的7，那么上述过程将无休止地运行下去, 而且在任何时候都无法得到我们想要的的结论. 因此，上述过程不是能行过程.
注意：在例2-2中，虽然我们给出的函数的计算过程不是能行过程，但却不能以此断言没有计算函数的能行过程. 也许有计算函数的能行过程，然而至今尚无人知晓. 有趣的是：如果把例2-2中定义的函数改成如下函数
(2.2)
其中，表示函数在输入时无定义. 那么计算函数的过程对于来说就是一个能行的过程. 这是因为对给定的输入，如果小数点后面有个连续的7，那么过程一定会在有限步终止并输出；如果小数点后面没有个连续的7，那么是没有定义的，无需考虑什么“输出结果”的问题.
四、停机问题
算法也好，能行过程也罢，它们的基本表达形式都可以用一组合适指令（well-defined instructions）的有穷序列来描述. 即在计算机科学领域，他们都可以表示为计算机“程序”. 在第一章中（命题1.17）我们证明了所有的计算机程序之多是可数的，因此可以把所有的程序枚举如下:
(2.3)
其中中的下标可视为该程序的编号或编码. 通过上面的分析我们知道，对任意的程序而言，它对某些输入是有明确输出的，运行有穷步后“停机”并给出结果；而对另一些输入可能是没有结果的，并因此进入“死循环”而“不停机”. 因此，我们自然会关心这样的问题:
停机问题: 是否存在一个能行过程，对任意的程序和输入，能判断对输入是否停机？
为了回答这一问题，我们首先要对程序输入与输出的概念做些处理. 程序通常有输入和输出，如果一个程序的输入是，那么经运行后的输出可表示为.运用编码技术，我们可以将程序的输入和输出用自然数表示，因此任何程序都可以视为自然数上的“函数”.
命题2.1. 停机问题是不可解的.即不存在能行过程，对任意的程序和输入，能判断对输入是否停机.
证明: 运用反证法：如果停机问题是可解的，那么就存在能行过程，对任意程序和输入, 当对输入停机时有；当对输入不停机时有，其中“”和“0”分别表示“停机”和“不停机”之意.
利用，我们定义计算过程满足: 对任意自然数，如果则；如果则.因为过程是能行的，所以过程也是能行可计算的, 因此计算的程序一定会在所有程序的枚举中出现. 设计算的程序编号（或编码）为，则可表示为，即对任意的均有. 接下来我们考察程序关于输入的停机情况: 如果程序关于输入停机，则有，此时有；如果程序关于输入不停机，则无定义，由却可以得到，这和是计算的能行过程矛盾. 此矛盾表明判定停机问题的能行过程是不存在的. ■
注意: 需要指出的是：计算过程是可以用“程序”来表述的，一个计算过程是否是能行在于相应 “程序”的运行是否能得到人们所需要的计算结果，所以“能行过程”的概念是针对“程序”的，即能行过程的考察对象是“程序”. 但是，“停机问题”是针对所有“程序”的，它的考察对象因该是所有“程序”的汇集. 据此我们认为，在一般意义下考虑的“能行过程”不能与所谓“停机问题”同“域”而论，否则引起矛盾就难以避免.
§3 可计算性概念的数学描述
在20世纪以前，人们普遍认为，所有的问题类都是有算法的，人们关于计算问题的研究就是找出解决各类问题的算法来. 随着时间的迁移，人们发现有许多问题虽然经过长期的研究仍然找不到算法，于是人们开始怀疑，是否对有些问题来说根本就不存在算法，即它们是不可计算的. 那么什么是可计算，什么又是不可计算的呢？要回答这一问题，最关键的就是要给出“可计算性”概念的精确的定义.
到了20世纪30年代，一些著名的数学家和逻辑学家从不同的角度分别给出了“可计算性”概念的确切定义，为计算科学的研究与发展奠定了重要基础. 随着计算机的出现和计算科学的发展，科学家们将“可计算性”概念与“程序设计”思想有机结合，从而使“可计算性”的能行过程更加明显，进一步促进了人们对“可计算性”概念理解和认识. 本节将选择其中的一些描述方法做简单的介绍.
因为计算问题均可通过自然数编码的方法用所谓“函数”的形式加以表示，所以我们可以通过对定义在自然数集上的“可计算性函数”的认识来理解“可计算性”的概念.
一、递归函数
递归函数是递归论这门学科中最基本的概念，其产生可以追溯到原始递归式的使用，如我们现在所熟知的数的加法与乘法. 现代计算机应用技术中，大量的计算过程都是运用递归的形式来描述的，可以说递归技术已经成为计算机科学与技术领域重要的方法工具之一. 递归函数最早的形式是“原始递归函数”（primitive recursive function）, 因此, 我们首先介绍原始递归函数的概念.
1. 原始递归函数
原始递归函数是定义在自然数集上的函数，其值域是自然数集的子集. 一般我们用表示函数在变量处的取值，并称为-元函数. 有时为书写之方便，我们可令，则函数值可表示为. 下面是原始递归函数的定义.
按下述规则产生的函数称为原始递归函
（I） 基本函数：下列基本函数是原始递归函数
（a）零函数，即对任意的；
（b）后继函数，即对任意的；
（c）投影函数，即对任意的.
（II）合成模式：设和是原始递归函数，其中. 则运用合成模式产生的函数是原始递归函数.
（III）递归模式：设和是原始递归函数，其中. 则运用递归模式产生的函数是原始递归函数.
1931年，哥德尔在证明其著名的不完全性定理时，给出了原始递归函数的描述，并以原始递归式为主要工具，运用编码技术把所有元数学的概念进行了算术化表示. 原始递归函数的重要性一直受到数学家和逻辑学家的关注和重视. 通常，人们把能够用“纸”和“笔”在有限步里可以计算的函数称为“直观可计算函数”或“可计算函数”. 显然，原始递归函数都是可计算的.
例3-1. 证明自然数加法是原始递归函数.
证明: 首先我们注意到自然数集上的恒等函数是原始递归函数，因为. 于是可以通过递归模式，定义. 所以是原始递归函数. ■

例3-2. 证明自然数乘法是原始递归函数.
证明: 我们已经证明了是原始递归的，在此基础上可以通过递归模式，定义. 所以是原始递归函数. ■
早在哥德尔给出不完备性定理之前，原始递归函数就已成为数学研究的重要内容. 在研究中人们发现，几乎所有的初等函数都是原始递归的，于是便开始猜测: 原始递归函数可能穷尽一切可计算的函数. 不幸的人们很快发现这一猜想是不成立的. 早在19世纪20年代，就有数学家构造出了可计算的但却不是原始递归函数，其中最著名的是德国著名数学家阿克曼（Ackermann）在1928年发表的函数—阿克曼函数（Ackermann function）.
通过下面等式定义的函数称为阿克曼函数.
(3.1)
首先阿克曼函数的定义是无二意的. 对任意的，如果，则；如果，则函数值可以通过其“前面”的函数值来计算，其中或并且. 由于这些“前面”的函数值是有穷的，所以我们总可以在有限步里计算出函数值. 例如: 和等. 然而我们却有下面命题.
命题3.1. 阿克曼函数不是原始递归函数.
阿克曼函数有一个很特别的性质，即对任何一个一元原始递归函数, 总可找出一数a使得对所有的均有. 这样函数便不可能是原始递归函数，否则将可找出一数e使得对所有的均有, 令, 即得，从而引起矛盾. 
当然，我们也可以通过其它方式证明存在可计算函数不是原始递归的. 例如运用原始递归函数最多只有可数无穷个这一断言，采用康拓对角线方法就可以形式化构造出可计算但却不是原始递归的函数. 问题是：除了原始递归函数以外，究竟还有哪些可计算函数呢？又如何给出一个能够穷尽所有可计算函数的数学定义呢？
2. 部分递归函数
1934年，哥德尔在法国逻辑学家赫尔布兰德（Herbrand）早期工作的启示之下，提出了一般递归函数的定义, 1936年，美国逻辑学家克林（Kleene）又将一般递归函数的概念加以具体化，最终形成了所谓Herbrand-Gödel-Kleene部分递归函数（partial recursive function）的概念. 其定义如下：
全体原始递归函数是部分递归函数；
（IV）无界搜索模式：如果是部分递归函数，其中，那么通过无界搜索模式定义的函数

是部分递归函数.
注意：“无界搜索模式”中的符号“”表示“最小”之意，称为“”，定义中出现的表示有定义；部分递归函数的定义是在原始递归函数的基础上通过引入“无界搜索模式”加以扩充给出的，因此所有原始递归函数都是部分递归函数；原始递归函数是全函数，即处处有定义，而部分递归函数则可能在有些地方没有定义，例如：当不存在使得或者存在某个使得时，就没有定义，这便是“部分”的真正含义;部分递归函数也称递归函数.
给出部分递归函数的定义后，我们可以证明 Cutland N. Computability-An introduction to recursive function theory [M]. London: Cambridge Uni. Press, 1980: 46-47.

命题3.2. 阿克曼函数是递归函数.
在数学与计算机科学中，“判定问题”与“计算问题”关系密切，两者在形式上常常可以相互转化. 例如：“给定，判定是否为的因子”就是一个判定问题，如果针对这一问题定义如下函数：

则判定问题便转化成了一个计算问题. 如果函数是可计算的，那么它对应的判定问题就是“可判定”的. 由于可判定问题通常是用“谓词”描述的，因而可建立“递归谓词”的概念.
设是关于自然数的谓词，其特征函数定义如下：

其中. 如果是递归函数，则称谓词是递归的.
二、图灵机与图灵可计算函数
虽然部分递归函数给出了可计算函数的严格数学定义，但是在具体计算过程的每个步骤中，选用什么样的初始函数和执行怎样的基本运算仍然是不明确的. 为消除这些不确定的因素，英国数学家图灵“以人为本”，全面分析了人在计算过程中的行为特点，把计算归结在了一些简单、明确的基本操作之上，并于1936年发表文章 Turing A M. On Computable Numbers, with an Application to the Entscheidungs problem. Proceedings of London Mathematical Society [J]. 1936-1937(45-46): 230-256, 544-546.
，给出了一种抽象的自动机计算模型. 该计算模型有自己的“指令系统”，每条“指令”代表一种基本操作，任何算法可计算函数都可通过由指令序列组成的“程序”的在自动机上完成计算．图灵的工作第一次把计算和自动机联系起来，对以后计算科学和人工智能的发展产生了巨大的影响. 这种“自动机”就是现在人们熟知的“图灵机”.
1. 图灵机
图灵的基本思想是用机器来模拟人们用纸和笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
★ 在纸上写上或擦除某个符号；
★ 把注意力从纸的一个位置移动到另一个位置.
在计算的每个阶段，人要决定下一步的动作（进入下一个状态）依赖于两个方面：
★ 此人当前所关注的纸上某个位置的符号；
★ 此人当前思维的状态.
对应于上述4个方面，一台图灵机应有以下四个部分组成：
（1）作为“纸”的一条两端无穷的“带子”，被分割成一个个小格，可以理解为“寄存器”，可以向“寄存器”中“写入”或“擦除”某个符号；
（2）有一个移动的装置，能够在“纸上”移动，从一个“寄存器”到另一个“寄存器”；
（3）在移动装置上有一个“读头”，能过“读出”和“改写”某个“寄存器”中的内容；
（4）有一个状态存储器，能够记录当前的状态.
将上述4个部分组装起来便是一台图灵机.图2.1是图灵机模型的示意图.

q
当前状态
移动读头
两端无穷的带子
可读写“寄存器”
图2.1. 图灵机
0
0
0
1
1
1
1
1
1
1
0
0

2. 图灵程序
同现代计算机一样，图灵机是通过“程序”的方法进行计算的. 因此，图灵机也有相应的“程序设计语言”、“指令系统”、“程序”等概念. 我们不妨分别称之为图灵机语言、图灵机指令与图灵程序.
（1）图灵机语言使用的基本符号
★ 状态符：用以表示计算过程中每一时刻图灵机的状态，其中专门用以表示停机状态；
★ 数字符：, 用以写入或修改“寄存器”的内容；
★ 移位符：，分别表示移动读头的“右移”和“左移”.
（2）图灵机指令
程序设计语言中指令通常表示机器所能执行的“基本运算”或“基本动作”，图灵机的指令是以“语句”的形式表示的，有2中基本类型
★ 读写指令： 其中表示状态. 其语义为：如果在状态读头读到的寄存器内容为，则把该寄存器的内容改成并进入状态.
★ 移位指令： 其中表示状态. 其语义为：如果在状态读头读到的寄存器内容为，则把移动读头右移（如果）或左移（如果）一格并进入状态.
注意：通常图灵机指令的表达形式为或而并无符号“”.我们引入符号“”的目的是为了帮助我们分析和理解图灵语句的含义.
在指令或中，位于符号“”左端的部分称为指令的前件，位于符号“”右端的部分或称为指令的后件. 指令的实际含义是：由前件的“判断”决定后件规定的“动作”.
（3）图灵程序
由图灵指令组成的有穷序列称为图灵程序.
例3-3.
(3.2)
便是一个图灵程序，其中是指令的编号，指令编号的目的是便于我们分析程序，通常可以不写.
既然是程序，就有输入和输出. 我们所关心的图灵程序通常针对自然数集上的函数，因此其输入和输出都是自然数. 我们用图灵机“带”上“1”的个数来表示其输入和输出，具体描述如下：
图灵程序的输入表示：如果某图灵程序在开始时的输入是 那么我们在图灵机“带”上分别用连续的“1”，，连续的“1”表示它们，输入的数与数之间用“0”隔开.
图灵程序的输出：图灵程序运行至停机状态，图灵机“带”上“1”的个数即为该图灵程序的输出.
初始状态约定：图灵程序运行之前图灵机的状态称为程序的初始状态. 图灵程序在初始状态时，其所有的输入数据都位于图灵机的“读头”的右端. 程序的初始状态一般用表示.
图灵程序的执行：图灵程序从初始状态开始运行，每执行完一条指令就会进入下一种状态，如，如果在状态“读头”读到的“寄存器”的内容为，那么程序执行的下一条指令一定是以为前件的指令，如果此时程序中没有以为前件的指令，则程序自动“停机”，否则程序将一直进行下去，直到进入停机状态终止.
接下来通过对例3-3中程序的分析，来理解和认识一个图灵程序的执行过程. 设该程序为P，开始的输入数据为6，则程序P的初始状态可由图2.2示意.

0
0
0
1
1
1
1
1
1
1
0
0

图2.2. 程序P初始状态示意图

程序的执行过程可以通过下列步骤序列进行描述：
步骤1. 程序从第一条指令开始执行，读头不断在“带”上右移，直到发现第一个不为0的单元格为止，执行指令并进入状态.
步骤2. 在状态，如果遇到1，则将其改为0进入状态，到步骤3执行；如果遇到0，则读头右移一格，进入状态，到步骤4执行. （不难看出，首次进入步骤2执行时，将“带上”的第一个1改成了0.）
步骤3. 在状态，如果遇到0，则右移一格，进入状态，到步骤4执行; 如果遇到1，则右移一格，进入状态，到步骤2执行.
步骤4. 在状态，如果遇到0，则停机；如果遇到1，则右移一格，进入状态，到步骤2执行.
分析：程序运行过程中，（1）在步骤2，如果遇到1则总是把它改为0，如果遇到0则右移一格进入步骤4，在此情况下如果继续遇到0，则运算终止. 也就是说该程序在进入真正计算时，如果遇到两个连续的0就结束. （2）在步骤3开始，总是遇到0（是步骤2刚刚修改的），所以右移一格，进入状态，在此情况下如果继续遇到0，则运算终止；否则，右移一格（跳过当前的1）进入步骤2，此时步骤2将与前面单元格右临单元格的1改为0.
经过