图灵秘辛
0.图灵计算=递归函数计算
人工智能之父是图灵，图灵的价值在于图灵机。图灵机是计算机的理论模型，而递归函数是图灵机的数学模型。递归函数是离散数学构造的普适性的计算模型。可以说，递归函数就是图灵计算、人工智能的秘辛！
1 . 递归函数的诀窍：分解计算、逐步计算对于各种各样的数学问题，递归函数采取的朴素而有效的立意是通过分解计算、逐步计算解决问题。对于求解x+y=z这类问题，先求x，y，再求z，这就是分解计算，即将方程的参数分别求取。而x或y可能不能一下子直接求取，就先通过另外一个函数，求取x的初值，再一步一步求取当前所需的x值，这就是逐步计算。分解计算和逐步计算就是递归函数的核心观念。
递归函数是通过原始函数，或称基本函数合成的。举例而言，原始函数是砖，经过合成后形成的递归函数是楼房。
2.原始函数原始函数有三种：后继函数、零函数和投影函数。常值函数（将定义域内某元素映射为一个常值）；后继函数（将定义域内某元素映射为它的下一个数）；
投影函数（将定义域内某元素映射为一个变量）。原始函数是数学里随处可见的函数类型。正因如此，递归函数蔡具有广泛的普适性。原始函数经过以下两种方式构造递归函数：
3.递归函数的构造方法由上述3个原始函数（后继函数、零函数和投影函数）构造更为复杂的函数-------递归函数的方法有两种：复合方法、递归方法。
复合方法
定义1 已知函数h（y 1，…，y k） ，g1（x1，…，xn），g2（x1，…，xn），…，gk（x1，…，xn），那么，复合函数是 f（x1，…，xn）= h（g1（x1，…，xn），g2（x1，…，xn），…，gk（x1，…，xn）） 即f是通过h和g的复合得到的，写作f =h￮g。直观的说，复合就是把n个g系列的原始函数，代入另一个原始函数h里的k个自变量之中：
在这种情况下，就说函数h和函数g被复合了；或者说，通过两个原始函数h和g复合，构造了一个函数h。
递归方法定义2已知函数g（x1，…, xn），h（x1，…，xn , y, z），则递归函数 f（x1，…，xn，0）= g（x1，…，xn） （1）f（x1，…，xn，y+1）= h（x1，…，xn , y, f（x1，…，xn，y））（2） 是由h和g经过递归得到的。 “递归”，在本意上和字面上理解，就是“一步一步地回去”。“递”也就是“分步骤地”，可以想象一个递次就是梯子的一个格；“归”就是“回去”。------什么东西回到哪里去？是目标函数值回到这个函数自身的自变量里去了！这似乎很奇怪：我们目标是求一个函数的值，既然得到了，为什么又作为自变量输入到它自身的一个自变量里去？原因就是在“递次”里面：在前一个递次，函数值得到了，但是下一个递次的函数值我们不知道；不仅函数值我们不知道，函数值里面的变量也不知道，于是我们用本递次的函数值嵌入到这个函数之中，作为变量之一，去求解下一递次的函数值。考察（1）和（2）的形成过程。
在第一个步骤，也就是初始步骤。将初始值的f表达式带入函数h的最末一个参数（使用了复合方法），同时，函数f的值作为 h的参数被写入 h，得到了f（x1，…，xn，y+1）见图2。
在第二个步骤，也就是f往返过程。通过f(y+1，…)向h的回归的得到的f(y+2，…)，f(y+2，…)向h的回归将得到f(y+3，…)等等，直至达到预期的步骤和结果。每一个循环就是一个递次的回归，见图3。
我们有了用于构造递归函数的原料（原始函数）和方法（递归函数的构造方法），现在我们考虑构造什么样的递归函数。构造递归函数的过程有一个发展过程。这一过程表现了递归函数又简单的递归函数发展为表现力强的递归函数，最后形成了一个递归函数家族。现在我们按照逻辑发展脉络介绍递归函数家族的形成过程。定义3 （原始递归函数）. 原始函数或者原始函数经过复合或递归得到的函数称为原始递归函数。 “原始递归函数”是数学家构造的首个递归函数。之所所称为“原始的”，因为构造它所使用的函数是“原始函数”。作为名词，“原始递归函数”的概念是哥德尔1931年提出的。但是这一函数形式本身是斯克伦于1923年提出的。原始递归函数是实现通过函数构造递归函数进而求解递归函数的最初的尝试。 例1自然数的加法是原始递归函数。证明： x+0=xx+(y+1)=(x+y)+1通用的自然数加法函数可以写为add (x,0)=P11(x) add (x,y+1)=S (P13(x,y,add(x,y))) 其中：S是后继函数；P是投影函数；add 是加法函数。
在此例中，S，P是原始函数，我们假设是我们已经知晓的；add函数是我们要求得的。我们虽然暂时不知道它，但是通过S，P得知了add 的初始值，并通过S，P和add 递次回归，就得出了add 的目标值。把add函数通过递归的方式构造，似乎觉得多此一举，因为我们有关于所有自变量和因变量的映射规则，那为什么要递归呢？要知道递归函数的目的是逐步获得目标函数f的值。因为我们假设对于函数add除初值外的任意数的运算法则我们是不知道的，才对add进行递归运算，以递次地求得加数并进行add运算。 例2证明乘法函数是递归函数。证明：x×0=0x×(y+1)=x+(x×y)Mul (x,0)=P11(x)Mul (x,y+1)=add(x,Mul(x,y)) 通过递归进行计算的基本目的是使计算更具有普适性，即能够计算更多的数和函数，进而可求解更为广泛的问题。对于像z=x+y等许多简单的初等函数，给定x和y的常元赋值，函数就通过直接的计算得到了。这里，“直接的计算”是指不再需要其他的函数。但是，在许多情况下，x和y是不能或不容易显式得到的，也需要函数计算，甚至逐次计算，在这种情况下，函数值z就不是直接计算了，而是通过其他函数得到x和y的一次赋值，再进行针对这次赋值的z值的计算。因此，z不是通过一个函数计算出来的，并且不是一次计算得出的。简单地说，这种分函数、分步计算，即通过逐次计算子函数将其结果输入变元再逐次计算函数的办法就是原始递归的办法。
例1和例2展示了自然数（含0）加法和乘法的递归性，那么，它们的逆运算如何呢？显然，自然数逆运算可能涉及两个难题，一个难题是可能产生负数和小数，即逆运算的结果可能不封闭于定义域，也就是说，计算的结果跑出了自然数的范围。这样，如果要求定义域和像（值域）是重合的，就必须扩大定义域的范围，使得反函数（逆运算）有定义，由此必须应用部分函数的概念定义递归函数，使得函数的定义域从处处有定义的全函数的定义域，扩大到原来没进行定义的数域，以满足反函数处处有定义（使反函数至少是全函数）。为此定义了“部分递归函数”。另外一个难题是逆运算可能产生无限循环，如何机械地计算一个无限循环的值？图灵给出的解决方法是算出一个近似值替代无限循环的值本身，例如，将0.333和0.414作为1/3，的（近似）计算结果。这样，计算的结果会因位数的长短不同而有很多。如果确定一个极小的误差（上确界）e，就可以确定一个最近似的值，例如，对于e1＜0.1，可以得到1/3的一个近似值0.3；e2＜0.01，可以得到0.33；等等。
此外，不只无限循环要求无穷步骤的计算，还有一些情况如无穷变元计算也可能导致无穷计算，如三角函数的反函数arcsinq，原函数sinq的定义域q也可以是无穷的。这样也需要极小值的函数以确定一个极小的q，以此为起点枚举良序中逐步大的q。 定义4（极小值函数；最小值函数；m-算符操作，简称m-算符，m-算子） 设g(t，x1，…，xn)是一个全函数，定义f（x1，…，xn）如下： f（x1，…，xn）=mt=min{t| g(t，x1，…，xn)=0} 称f（x1，…，xn）是g(t，x1，…，xn)通过对t取极小值运算得到的函数，即t有多个值，其中的极小值mt即f（x1，…，xn）的取值（记作mt，也就是满足特征方程g(t，x1，…，xn)=0的多个t中的最小的t。因此可以将mt理解为在h(x1，…，xn)=t中搜索极小的t的操作（h的特征方程是g）。
对于反函数的运算，可将g理解为计算f的反函数（逆运算函数）f – （或者递归得到f –的原始函数）的特征函数。
m算符更为直观的解释定义是 f（x1，…，xn）=最小的t 满足g(t，x1，…，xn)=0 如果存在最小值tg(t，x1，…，xn)=1 如果不存在最小值t 这样就可以定义两个函数T1和T2，当T1 运算f 并找到一个最小的t，即mt，使得f – 的特征函数g=0，在此状态下，T2计算f –(t)。 定义5（m-递归函数、m-部分递归函数） 原始函数或者原始函数经过复合或递归，或通过取极小值得到的函数，称为m-递归全函数（如果是指处处有定义的递归函数）；如果函数取值不加限制（可以不必是完全的），那么，就得到m-部分递归函数。
可见，m-递归函数由于定义了逆运算的定义域以及在无穷计算中的有穷近似值，因此使得递归函数的定义域扩大到了实数域。
因此它们的合成是可计算的。由此可见，可计算函数是超出原始递归函数的范畴的。
4.递归函数的家族当使用“递归函数”这一概念时，应该意识到它是一个历史概念，同时也是一个概括性的概念而被指称为一个递归函数族，相当于定义6的“广义递归函数”。定义6广义递归函数（一般递归函数，General Recursion Function，GRF）是由表1所示的递归函数构成。表1的分类主要参照文献的定义，但是与某些文献有所不同。在一些文献中，“一般递归函数”被解释为m-全递归函数，这一解释将一般递归函数解释为m-部分递归函数的子类，这与“一般”这一意义不符（“一般”的要比“全”的函数范围更大），也与这一概念的提出者的本意不符，是不妥当的。“一般递归函数”或“广义递归函数”这一称呼源自哥德尔（1934年），他用此概念应该是表示除原始递归函数外的更为广泛的递归函数。他针对海伯伦于1931年提出的超出原始递归的递归函数的定义提出了“一般递归函数”。海伯伦提出的递归函数的概念与邱奇递归函数后来提出的概念基本一致，因此应指包括阿克曼递归函数等在内的更广泛的递归函数。
总而言之，“一般递归函数”就是所说的“递归函数”，也就是部分递归函数，而不是部分递归函数的子类-----m-全递归函数。“一般递归函数”翻译为“广义递归函数”（类似于将“general relativity”翻译为“广义相对论”）更能反映其本质特征，即一般递归函数或广义递归函是当前已经发现的递归函数类中最为广义的递归函数，递归全函数是其子类。
5.递归函数的通俗解释参见例1和2。加法函数和乘法函数都是原始递归函数。但是，我们不用递归的方法计算加法函数和乘法函数，这是为什么呢？换言之
即为算出4+6，要逐次通过4+0算出4+1；通过4+1算出4+2；……算出4+6，即算下一步要通过得到前一步的结果来实现。而加法的通常的计算无需从4+0算到4+5再计算5+6在计算5+6。这就是递归计算的本质。用通俗说法描述这一过程是，用前一个匣子里的钥匙开后一把锁。这一使得，当我们没有所有自变量取值的运算结果清单（没有所有自变量映射其函数值的“映射法则”，也就是说不会有类似于x=4，y=1,2,3,4,5,6时的全函数的加法器，只有类似于加1，即实现一个步长函数运算的加法器）时可以逐一分部获得前步计算结果逼近并实现最终的计算。也可以把递归函数比作上楼梯。在不能一下子上到楼层顶上的情况下，就每次登一阶楼梯台阶，在这个台阶基础上，再登下一阶台阶，每个台阶都以前一台阶为基础……最后登顶。
参考文献
Kurt Godel.On Formally Undecidable Propositions of Principia Mathematica and Related System I.From Frege to Godel, Harvard University Press,pp.592-.617.
科特·哥德尔 《论〈数学原理〉及其相关系统的形式不可判定命题（I）》（汉语译文），张寅生 证明方法与理论，2015年。
Thoralf Skolem.The foundation of elementary arithmetic established by means of the recursion mode of thought,without the use of apparent variables ranging over infinite domains./From Frege to Godel//A Source Book in Mathematical Logic,1879~1931.Havard University Press,1977:302~333.
Stephen Kleene（1952）Introduction to Metamathematics. Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971); Tenth impression 1991.
Wilhelm Ackermann, On Hilbert’s construction of the real numbers./From Frege to Godel//A Source Book in Mathematical Logic,1879~1931.Havard University Press,1977:493-507
Bobert Soar. Computebility and Recursion,Bulletin of Symbolic Logic,Vol.2,Num.3,1996:284-321.
莫绍揆.递归函数/中国大百科全书/数.北京、上海：中国大百科全书出版社，1988：123-124.
丁德成.递归函数/数学大辞典.北京：科学出版社，2010：41.
宋方敏编著.计算模型导引，北京：高等教育出版社，2012：46. 附录：《计算理论解析》重要信息： 一个从新视角、新高度阐述计算理论与计算模型的著作，它透露图灵秘辛给你： 张寅生著《计算理论解析》，ISBN 978-7-302-43791-8，清华大学出版社，2016. 《计算理论解析》内容简介 本书介绍计算模型理论，包括计算的对象、本质、定义、分类、表达、逻辑和机械实现方法，以及计算模型的典型应用。
本书是计算理论（计算模型、形式语言与自动机）、计算机科学技术史、逻辑学、语言学（生成转换语言学）、数学哲学的交叉研究，也是通过浅显易懂的讲解方式进行计算机核心理论教学的尝试。作者力图为计算机相关人员提供一个计算的本质特征的“灵魂”描述及其通俗解释，以使得计算机软硬件的所有任务、过程特别是软件的表达与执行归结为数学原理和逻辑本质。本书适合作高等院校计算机、通信、自动化、软件工程、信息管理、数理逻辑与数学基础、生成转换语言学等等专业本科生和研究生的教材，同时，由于它深入浅出的努力，也使得它能够被具有基本数学能力的人所读懂，因此可供对计算机理论感兴趣的广大科技工作者参考。 《计算理论解析》目录第1章计算的对象和本质第2章可计算函数------递归函数2.0预备知识2.1分解计算、逐步计算的思想2.2原始函数2.3递归函数的构造方法2.3.1复合方法2.3.2递归方法2.4递归函数的家族2.5递归函数的通俗解释 第3章计算机的数学原理3.1数学运算的基础3.2希尔伯特第十问题及其自动化解决思想3.3图灵机原理3.4图灵机的局部改进和变形3.4.1多带图灵机3.4.2图灵机的复合3.4.3图灵机参数的限定 第4章语言的计算4.1图灵计算的分类4.2语言的可计算性4.3作为枚举器的图灵机4.4作为语言识别器（接受器）的图灵机4.5图灵机和短语语法4.6线性有界自动机与上下文有关语法4.7下推自动机与上下文无关语法4.8确定型有穷自动机与正则语法4.9不确定型有穷自动机与正则语法4.10自动机接受的语言 第5章判定问题的可计算性5.1基本概念5.2不可判定性问题实例5.2.1丢番图方程整数解问题5.2.2对角线函数5.2.3停机问题5.2.4逻辑蕴含5.2.4哥德尔语句G第6章计算模型的应用6.1计算机模拟图灵机6.2语言识别和语法验证6.3逻辑推理6.4计算复杂性分析
作者简介：张寅生, 中国科学技术信息研究所研究员，中国计算机学会高级会员，中国人工智能学会高级会员，中国数学会会员，美国计算机学会会员，中国创新设计产业战略联盟大数据工作委员会副主任委员(IDAC)。中国人民大学博士，清华大学心理与认知科学研究中心自动演绎推理课题博士后。研究领域: 认知科学,数理逻辑,计算理论,知识工程.主要著作：数学专著《扩展的三段论及自动推理》（科学技术文献出版社，2009），数学专著《证明方法与理论》（国防工业出版社，2015），语言学专著（合著）《语言学中的科学》（人民出版社，2015），数学专著《计算理论解析》，清华大学出版社，2016年。主持和参加国家级项目、中港合作项目多个，包括：国家科技基础条件平台计划项目“网络科技资源监测分析评估体系建设”；国家社科基金重大项目“语言、思维、文化层级的高阶认知研究”；国家科技重大专项“高可信并发实时系统的质量保障方法、工具及应用研究”课题“软件潜故障模型建模及其测试工具开发”。
页:
[1]