可计算性和计算复杂度（吉林大学教材-李占山）

简介：
可计算性与计算复杂性本章主要介绍可计算函数的定义、性质及其在计算机科学中的应用。首先，我们定义了一个函数f:N→N为可计算函数的前提是存在一个确定性的图灵机能够在有限步内完成其运算过程。其次，通过引入递归的概念，我们将可计算函数划分为两类：原始递归函数和μ-递归函数。这些分类有助于理解不同类别的计算能力及其局限性。最后，我们探讨了可计算函数在算法设计和程序实现中的实际意义，并给出了几个典型示例来说明其应用范围。 在数学分析中，我们经常使用以下公式进行计算：$y = x^2$；为了进一步推导，我们需要对上式进行求导运算：$\frac{dy}{dx} = 2x$；通过链式法则，我们能够得到最终结果：${\rm d}y = 2x \cdot {\rm d}x$。 - **变量定义**：书中所涉及的所有变量皆为非负整数。 - **基本指令**： - `X = X + 1`：将X的值递增。 - `若当前X不小于零，则将其减一；特别地，当X等于零时，操作后结果仍为零。` - `若当前X的值非零，则执行跳转指令至标签A位置。` - `无条件地转移至标签A指定的位置。` - `令Y等于当前X的值。` - **宏指令**： - `$Y = X1 + X2$`：该公式用于求得变量Y，其值为X1和X2之和。 - `$Y = X1 \cdot X2$`：该公式用于求取变量Y，其值等于X1与X2的乘积。 在计算机科学和数学理论中，可计算函数被视为基础概念，在算法设计与分析中具有核心地位。 **可计算函数的定义**：如果存在一个程序P，在给定输入X₁,X₂,...,Xₙ下，能够输出结果f(X₁,X₂,...,Xₙ)，则称该函数为部分可计算函数。其中等式成立的条件是两边要么均未定义，要么具有相同的函数值。 **全可计算函数（可计算函数）**：如果一个部分可计算的函数在所有可能的输入组合上都存在明确且确定的结果，则我们称其为全可计算函数，即该函数是一个完全定义域上的有效算法映射。 **常用基础函数**： - **减法运算**X₁ - X₂：只有当X₁大于等于X₂时才有定义。这种情况下，结果是两个数之差的非负值；否则，操作未被允许。 - **乘法运算**X₁×X₂：对于所有可能的输入组合（X₁, X₂），该函数都有明确且确定的结果。 #### 学习任务 **分析以下函数的可计算性** - **函数 f(X₁,X₂) = min{X₁,X₂}：** 可通过对比 X₁与 X₂ 的数值来确定两者的较小者。 - **函数 f(X) = α(X₃)：** 对于给定输入值 X₃=0 的情况，则 α(X₃)=1；而对于其他情况则有 α(X₃)=0。 - **函数 f(X) = X₁X₂：** 该函数可通过将输入的两个数值进行乘法运算直接实现。 - **函数 f(X) = [X₁X₂]（[ ]表示向下取整）：** 对于表达式 [X₁X₂] 而言，则需通过减去余数并执行除法操作来完成相应的处理。 - **其他复杂函数的分析：** 这些函数均可通过组合运用基本算术运算和预设的指令序列来进行计算，具体实现方式请参考后续详细说明。 本章系统阐述了递归函数的理论基础及其应用方法。首先定义了一个基本递归模式，该模式通过自调用机制实现复杂问题的分层求解。随后探讨了几种典型递归算法的设计原则，包括迭代优化和终止条件设定等关键要素。最后分析了一些实际案例，展示了递归函数在解决特定类型数学模型中的有效性运算器 - **复合算子**：当存在一个函数$y = f(z_1,z_2,...,z_m)$以及一组函数$z_i = g_i(x_1,x_2,...,x_n)$（其中$i=1,2,...,m$），则通过复合算子对这些函数施加运算后的结果为： $$ y = f(z_1,z_2,...,z_m) = f(g_1(x_1,x_2,...,x_n),g_2(x_1,x_2,...,x_n),...,g_m(x_1,x_2,...,x_n)) $$ - **递归算子**：在两个完全的函数$m(x_1,x_2,...,x_n)$和$\phi(x_1,x_2,...,x_n,y)$的基础上，定义$h$为： $$ h(x_1,x_2,...,x_n,0) = m(x_1,x_2,...,x_n) $$ 当$t+1$时， $$ h(x_1,x_2,...,x_n,t+1) = \phi(x_1,x_2,...,x_n,h(x_1,x_2,...,x_n,t),t) $$ 这种情况下，函数$h$就是递归算子作用于$m$和$\phi$的结果，并且$h$是一个完全的函数。 - **取极小算子**：对于一个全函数$f(x_1,x_2,...,x_n,z)$，定义： $$ h(x_1,x_2,...,x_n) = \min\{z | f(x_1,x_2,...,x_n,z) = 0\} $$ 这种$h$就是取极小算子作用于$f$的结果。如果$f$是一个正规函数，则$h$也是一个完全的函数。 原始递归函数是数理逻辑中一类重要的基本概念，在计算理论中具有基础地位。这些函数通过有限次使用后继运算、零元素定义以及复合操作构建而成，其特点是可以通过明确步骤在有限时间内完成计算任务。从初始函数$S(x) = x + 1$、$n(x) = 0$以及$I_i^n(x_1, x_2, \dots, x_n)$出发，通过合成运算符与递归运算符所构造出的函数统称为原始递归函数。这一类函数均为全函数。以下列举了若干典型示例： 加法定义为 $$add(x, y) = x + y$$ 乘法定义为 $$mul(x, y) = xy$$ 阶乘定义为 $$fac(x) = x!$$ 指数运算定义为 $$exp(x, y) = x^y$$ 减法运算则仅在$x \geqslant y$时有定义；其他情况下未定义。 选择函数$p(x)$的定义如下： 当$x=0$时，$p(x)=1$； 否则，$p(x)=x$。 特殊函数$\alpha(x)$的定义为： 当$x=0$时，$\alpha(x)=1$； 否则，$\alpha(x)=0$。本节主要讨论原始递归谓词的概念及其在形式语言中的应用，这些谓词通过有限次的应用规则表达式来定义，并且其计算复杂度较低 **特征函数**：称谓词P(x1,x2,...,xn)为真时取值为1，在其他情况下取值为0。这种函数称为谓词P的特征函数。 **原始递归谓词**：如果一个谓词P的特征函数是原始递归函数，则我们称P是一个原始递归谓词。 **定理**：若函数f(x1,x2,...,xn,y)是原始递归的，那么其前驱函数和后继函数[图片]、[图片]也是原始递归函数。 **其他定理**：关于构造和性质的其他定理，如逻辑运算、量词操作等，往往都是基于对原始递归函数特性的深入分析而建立起来的。 在研习上述各章内容后，我们能够掌握可计算性和计算复杂性领域的基本概念及其分类方法，尤其是对函数计算能力和其复杂度进行分类和深入理解。这些理论不仅对我们深入认识计算的本质有所帮助，同时也为我们后续开展计算模型研究提供了坚实的基础。