5 函数可计算性

原始递归函数

基本函数

合成方法

• 函数的复合
• 递归定义 \(f(n_1\dots n_k,0)=g(n_1\dots n_k)\) \(f(n_1\dots n_k,m+1)=h(n_1\dots n_k,f(n_1\dots n_k,m)\) (通俗解释,f(n,m+1)由f(n,m)和n决定)

原始递归函数

原始递归函数由基本函数的复合/递归得到的函数全体

\(plus(n,m)=n+m\)

• 用递归 \(plus(n,0)=n,plus(n,m+1)=succ(plus(n,m+1))\)

\(mult(n,m)=mn\) 对\(plus(n,m)\)递归

前驱函数\(succ(0)=0,succ(n+1)=n\)

• \(succ(0)=0\)
• \(pred(n+1)=n=id_{2,1}(n,pred(n))\)

\(m\sim n=\max \{m-n,0\}\)

• \(m\sim 0=m\)
• \(m\sim(n+1)=succ(m\sim n)\) 利用succ(0)=0

\(iszero(n): iszero(0)=1,iszero(n)=0\)

分段函数 \(p,q\)只能取0或1

• \(f=p \cdot g+(1\sim p)\cdot h\)

\(digit(m,n,p)=div(rem(n,p^m),p^{m\sim 1}))\)

原始递归函数都是可计算的

证明: 假设C可判定, 那么C'=一元可计算函数也是可判定的

C' is lexicographically Turing enumerable (根据recursive language 的性质)

构造一台TM M：

• 给定自然数n, 枚举\(g_1,g_2\dots g_n\)
• 得到了函数\(g_n\)之后, 计算\(g_n(n)\)
• 返回\(g_n(n)+1\) 设这个图灵机计算的函数为\(g*\). 那么\(g^*(n)\) 跟C‘中任意一个函数都不同

本质还是diagonization argument n= 1 2 3 g1 a b a g2 a c a g3 c a b g* a+1 c+1 b+1 跟每一行比, 都至少有一个元素不同。

μ-递归

判断一个可计算函数 g 是否是 minimalizable 的是不可判定的（停机问题）

μ-递归函数：原始递归函数+ 复合/递归定义/最小化

数值函数是μ-递归的当且仅当它可计算

Comments