部分数论函数
二元关系
集合和，
的元素称为有序对，
的子集称为从到的二元关系，
从到的二元关系，称为上的二元关系。
定义域和值域
设是从到的二元关系，
则称的定义域为，
的值域为。
象
，则称在下的象为，
，
特别的，如果，那么把在下的象简记为在下的象，记为。
即，
部分函数
如果是从到的二元关系，且，或，
则称是从到的部分函数，或上的部分函数。
若，则称有定义，记为，
称为在点的函数值，记为，
若，则称无定义，记为。
全函数
如果都有，即，则称是上的全函数，
此时，可以记为。
元部分函数
设是笛卡尔积上的部分函数，
则通常把，简记为。
集合上的部分函数，称为上的元部分函数。
自然数集，从到的部分函数，称为元部分数论函数。
下文中提到的函数，默认为数论函数。
字函数
字母表是一个非空有穷集合，
设是一个字母表，中元素的有穷序列称为上的字符串或字，
简记为。
中符号的个数，称为字符串的长度，记为。
我们用表示空串，它不包含任何符号，是唯一的长度为的字符串。
上字符串的全体，记为。
设，把连接在后面得到的字符串记为。
设，规定，，，
当时，等于个连接在一起。
到的部分函数，称为上的元部分字函数。
程序设计语言
变量
语言使用三种变量，
输入变量，输出变量，中间变量，
变量可以取任何自然数值。
语言还可以使用标号。
当下标为时，可以略去。例如，和表示同一个变量。
语句
语言有三种类型的语句，
（1）增量语句，表示变量V的值加
（2）减量语句，若变量的当前值为，则的值保持不变，否则的值减。
（3）条件转移语句，如果变量的值不等于，则下一步执行带标号的指令，否则顺序执行下一条指令。
执行
开始执行程序时，中间变量和输出变量的值都为，
从第一条指令开始，一条一条的顺序执行，除非遇到条件转移语句，
当程序没有指令可执行时，计算结束，
此时的值为程序的输出值。
例如，
这里是第一条指令的标号，我们可以看到，这个程序计算的函数是，
状态
设是形如等式的有穷集合，其中是一个变量，是一个数。
如果，
（1）对于每一个变量，中至多含有一个等式
（2）如果在程序中出现变量，则中必含有等式
那么，称是程序的一个状态。
状态描述程序在执行的某一步各个变量的值，
我们约定，如果中不含关于的等式，则变量的值自动取。
快相
程序的一个快相，是一个有序对，
表示程序的当前状态为，即将执行第条指令。
，其中，是程序的长度，
如果，就表示程序结束，称为程序的终点快相。
除了输入变量外，所有变量值为0的状态称为初始状态，
如果是初始状态，则称是初始快相。
程序的计算
设是程序的一个快相序列，长度为，
如果，
（1）是初始快相
（2）对于每一个，是的后继
（3）当时，是终点快相
则称该序列是的一个计算。
函数的可计算性
程序计算的函数
设是语言的一个程序，是一个正整数，
称函数为程序计算的元部分函数，
如果，是初始快相，其中输入变量为，输出变量为，
（1）从开始的计算是有穷序列，则等于在中的值
（2）从开始的计算是无穷序列，则
部分可计算性与可计算性
设是一个部分函数，如果存在程序计算，
则称是部分可计算的。
如果一个函数，既是部分可计算的，又是全函数，则称这个函数是可计算的。
谓词的可计算性
我们可以把谓词看作取值为或的全函数，
并把真值等同于，假值等同于。
如果谓词作为一个全函数是可计算的，
则称该谓词是可计算的。
函数的递归性
合成运算
设是元部分函数，是个元部分递归函数，
则称是由和，经过合成运算得到的。
可证，如果是由（部分）可计算函数和合成得到的，
则也是（部分）可计算函数。
原始递归运算
设是一个元全函数，是一个常数，
则称是由经过原始递归运算得到的。
可证，如果是可计算的，则是可计算的。
设是一个元全函数，是元全函数，
则称是由和经过原始递归运算得到的。
可证，如果和都是可计算的，则是可计算的。
原始递归函数类
设初始函数包括，
（1）零函数
（2）后继函数
（3）投影函数，
则，由初始函数经过有限次合成运算和原始递归运算得到的函数，称为原始递归函数。
可证，由原始递归函数经过合成运算或原始递归运算，得到的函数仍为原始递归函数。
每一个原始递归函数都是可计算的。
常用原始递归函数举例，
常数，，，，，，前驱函数，
原始递归谓词
如果一个谓词看作取值为或的全函数是原始递归的，则称该谓词是原始递归的。
可证，如果和是原始递归谓词，则，和也是原始递归谓词。
极小化运算
设是一个谓词，
，
的值，或者是使为真的的最小值，
或者无定义，如果不存在使得为真。
其中，为极小化运算，
也称部分函数，是由谓词经过极小化运算得到的。
设是一个元全函数，
，
则称是由函数经过极小化运算得到的。
递归函数类
由初始函数经过有限次合成运算，原始递归运算和极小化运算，得到的函数称为部分递归函数，
部分递归的全函数称为递归函数。
如果一个谓词看作取值为或的全函数是递归的，则称该谓词是递归的。
递归性与可计算性
可证，部分递归函数是部分可计算函数。
递归函数是可计算函数，递归谓词是可计算谓词。
可证，原始递归函数类是可计算函数类的真子集。
因为，至少存在一个Ackermann函数是可计算的，但不是原始递归的。
集合和语言的递归性
集合识别问题
所谓集合识别问题，是指对于给定的集合，任给一个元素，问这个元素是否属于该集合，
也称为集合的成员资格问题。
集合特征函数
设，的特征函数是一个谓词，定义为，
，
集合可以用它的特征函数表示为，。
如果特征函数是可计算的，则称集合是递归的。
如果存在部分可计算函数使得，
则称集合是递归可枚举的。
可证，如果集合和都是递归的，则集合，和都是递归的。
递归集一定是递归可枚举的。
集合是递归的，当且仅当和都是递归可枚举的。
如果集合和是递归可枚举的，则集合和也是递归可枚举的。
语言识别问题
设字母表，的任何子集称为上的语言。
上集合的识别问题，有称为上的语言识别问题。
语言的特征函数定义为，，
如果语言的特征函数是可计算的，则称语言是递归的。
如果存在上的部分可计算函数使得，，
则称语言是递归可枚举的。
递归可枚举集
设，且是递归可枚举的，
则存在原始递归谓词使得，
设是一个非空递归可枚举集，则存在原始递归函数使得，
集合是递归可枚举的，当且仅当存在部分可计算函数，使得，
总之，如果非空，则以下命题是等价的，
（1）是递归可枚举的，即是一个部分可计算函数的定义域，
（2）是第一个原始递归函数的值域，
（3）是一个可计算函数的值域，
（4）是一个部分可计算函数的值域。
可判定性与半可判定性
程序设计语言，递归函数，Turing机，文法等计算模型，
可以证明它们是等价的，即计算相同的函数类——部分可计算函数。
它们可以识别相同的语言类，递归可枚举语言。
如果语言是递归的，那么存在一台总停机的DTM（确定型图灵机）识别，
任给一个字符串，总能在有限步内回答还是，
因而，我们说为可判定的。
如果的递归可枚举的，情况就不同了，识别的DTM可能永不停机，
只有当时，才能保证一定能在有限步内停机并接受，
而当时，可能永不停机，
在这种情况下，我们不知道是暂时没有停机，还是永不停机，
这时，我们说是半可判定的。
因此，递归语言是可判定的，而递归可枚举语言是半可判定的，
同样的，直观可计算函数是可计算函数，而部分可计算函数是半可计算的，
可计算谓词是可判定的，它定义的集合是递归的，
如果谓词定义的集合是递归可枚举的，则该谓词是半可判定的。