数值函数 Numerical Function

A TM $M$ computes $f:{\mathcal{N}}^k\to \mathcal{N}$ if for any $M(bin(n_1),\dots bin(n_k))=bin(f(n_1\dots n_k))$

基本函数 Basic functions

• zero function $zero(n_1,n_2,...n_k)=0$
• identity function: $i{d}_{k,j}(n_1,n_2,...n_k)=n_j$
• successor function: $succ(n)=n+1$

原始递归函数 primitive recursive function

• primitive recursive function = basic func + composition + recursive definition
  • composition: $g(h(x))$
  • recursive definition: $\{\begin{array}{l}f(n_1,\dots ,n_k,0)=g(n_1,\dots ,n_k)\\ f(n_1,\dots ,n_k,t+1)=h(n_1,\dots ,n_k,t,f(n_1,\dots ,n_k,t))\end{array}$
• Lemma: Every primitive recursive function is computable and decidable
• $PR$ = { "$f$": $f$ is a primitive recursive function.}
• e.g.
  • $\mathrm{p}\mathrm{l}\mathrm{u}\mathrm{s}(n,m)=n+m$
  • $\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}(n,m)=n\times m$
  • $\mathrm{s}\mathrm{u}\mathrm{b}(n,m)=n-m$
  • $\mathrm{s}\mathrm{g}\mathrm{n}(n)=\{\begin{array}{ll}1& n>0\\ 0& n=0\end{array}$
  • $\mathrm{d}\mathrm{i}\mathrm{v}(m,n)=\lfloor m/n\rfloor$

原始递归谓词 primitive recursive predicate

• 原始递归谓词是只取值 0 和 1 的原始递归函数
• e.g.
  • $\mathrm{i}\mathrm{s}\mathrm{z}\mathrm{e}\mathrm{r}\mathrm{o}(m)$
  • $\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{l}\mathrm{s}(m,n)$
  • $\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}(m)$

computable numerical function

• $C$ = {"$f$": $f$ is a computable numerical function.}
• $PR\subseteq C$
• primitive recursive function + $\mu$-recurisve function = computable numerical funcition

$\mu$-recursive

• $\mu$-recursive function = basic func + recursive definition + minimalization
  • minimalization $f(n_1,\dots ,n_k)=\{\begin{array}{ll}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{u}\mathrm{m}\mathrm{o}\mathrm{f}\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{m}& \mathrm{i}\mathrm{f}\mathrm{\exists }m,g(n_1,\dots ,n_k,m)=1;\\ 0& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}$
• A function is $\mu$-recursive if and only if it is computable(recursive).
• e.g.
  • $\log (m,n)=\lceil {\log }_{m+2}n+1\rceil =\mu p[geq((m+2{)}^p,n+1)=1]$