学步园

递归函数

计算机只能计算递归函数

递归：定义对象类的一种方法

基本递归函数类

原始递归函数类

部分递归函数类

    全函数（Total Functions）：在自然数集合上处处有定义的函数
    部分函数                       ：在自然数某子集上有定义的函数
F是集合A，B上的一个二元关系，对每一个a E A, b E B，均有（a, b）E F,则称：F是A到B的一个全函数，否则则称为部分函数

递归需要：

• 原始对象  ：三个基本+基本递归函数类+原始递归函数类
• 方法或规则：极小化运算

极小化运算：

1. 存在一个全函数f(y, x1, x2, ..., xn)=0
2. 引入一个新函数h(x1, x2, ..., xn)=0
3. 使得f(y, x1, ..., xn)=0时，y有最小值

三个基本运算：

1. 复合运算
2. 原始递归运算
3. 极小化运算

递归函数是一个计算模型，规定了计算机所能计算的对象。递归函数是一步一步构造出来的，属于构造数学。递归函数的定义上一个构造过程，具有典型的过程性。其求解过程是定义过程的逆向运算，得到一个构造解。因此，递归函数是产生过程性程序设计风格的数学基础。

goto -> branch(模块内) + jump(模块间)

结构化程序设计

• 1966，Giusepe Jascopini，证明了对任一单入口，但出口的程序，只需要三种结构（顺序，循环，分支）就可以实现
• 1968，E.W.Dijkstra，"Goto有害"
• 1971，Niklaus Wirth，“Algorithsm + data = program”

算法

    算法是求解数学问题步骤的形式化描述

程序设计步骤：

1. 将程序分解为算法段
2. 各算法段单入口，单出口
3. 算法段内(512)branch跳转，段间jump跳转

常用的编译技术

• 剪枝法
• 逆波兰法
• 递归编译

图灵机

机器模型

    经数学推演所得到的结果与机器运行的结果一致，这种数学结构就可称为机器模型

机器

    一类结构相似的抽象设备，通常可用集合论术语表示成数学对象，我们就称之为机器。

图灵机是面向机器的计算模型，具有典型的过程性
递归函数是面向数学的计算模型，具有典型的过程性，构造性

图灵机

• 给能行可计算函数提出了一个形式定义
• 证明了莱布尼兹的猜想：“一切事物都可以用符号表示，一切推理都可以表示为对符号的操作”

但是，所有的机器都只是能处理语法问题，而不能处理语义问题。（真正意义的人工智能无出路）

通用图灵机
    通用图灵机是这样一种图灵机，它可以模拟其它所有的图灵机

图灵机的非形式定义
    一台图灵机由一条无限长的，可左右移动的袋子和一个读写头组成，带子上刻有很多方格，读写头每次只能读写一个方格，读完一个方格后，用下一个方格的内容来代替当前方格。

衡量计算规模的大小
    使用输入长度来衡量，即输入转换为二进制数的长度

若一个问题在计算机上处理，处理的时间是问题规模的多项式函数，则该问题可称为多项式时间问题。

形式语言
    给一台已经定义好了的图灵机输入字母表，若图灵机能停机，则称图灵机接受了这个语言

图灵机的停机问题

问题：
    能否定义一台这样的图灵机，它以任何一个图灵机Z以及在Z上工作的语言作为输入，这台图灵机能否断定图灵机Z是否能停机。

答案：
    1967，M.L.Minsky，不能

推论：
    不存在任一程序，能证明其它程序的可靠性，即程序行为具有不可判定性

对软件领域的两点启示

• 经测试的软件是可靠的当且仅当是在测试环境下
• 在信息安全领域中医科特征码的实现是无效的

基本递归函数类 < 原始递归函数类 < 部分递归函数类 < 确切定义函数类 < 全体函数类

一阶谓词演算系统

谓词：操作目标的成分
一阶：谓词仅能操作目标
高阶：谓词技能操作目标，又可以操作谓词

数理逻辑：用数学的手段来研究逻辑问题

四大论：递归论，模型论，证明论，公理集合论

70年代时计算机仅用于数值计算，后来才进入非数值计算领域。

三大程序设计风格

• 过程型程序设计     图灵机模型，递归函数
• 逻辑型程序设计     谓词演算系统
• 函数型程序设计     Lisp语言

数据

• 数据类型：规定了对数据所能进行的操作
• 数据结构：规定了数据各元素见的关系（顺序，层次...）
• 抽象数据类型：Smalltalk， Simula
• C = compile + Smalltalk

如何定义一个形式系统

1. 定义该形式系统中的基础成分及其符号表示（一阶谓词演算系统的成分如下）
   1. 命题常量：可判断命题真假的陈述
   2. 个体变元：谓词逻辑中所讨论对象的载体，被变元取值的全体对象叫论域，变元即其中某一类
   3. 常元     ：表示常量的个体变元的符号
   4. 常函数  ：若存在A,B 若任取a属于A, 都有b0（固定）属于B，则F（a）为常函数
2. 定义一些规则
   1. 在一阶谓词演算系统中，这些规则被称为逻辑结构（真，假，非，合取，析取，蕴含，等价）
      1. 等价：自反，对称，传递
   2. WFF（何氏公式）
3. 项
   1. 一切形式变量，一切形式常量
   2. 若t1, t2, t3, ... ,tn是项，则f(t1, t2, t3, ... , tn)也是一个项
   3. 经过所有基本一阶谓词演算得到的命题，公式也是项
   4. 若对于t1, t2, t3, ... ,tn，给定一个谓词函数P(t1, t2, t3, ... ,tn)也是项

一阶谓词演算是怎样变为计算模型的？

• 1972年，Kowalski发现一阶谓词演算系统，将逻辑子句看做程序语言的子句，而定理证明过程就是对子句的消解，因此逻辑本身可作一种程序设计语言，归结算法是对语言的解释。
• 1960年，Davis Patlam 所有一阶谓词系统中的何氏公式，都可表示为逻辑子句
• 1965年，Robinson提出归结算法

回顾

近代数学的基础：朴素集合论