1.18

设 k∈N+k \in \mathbb{N}^+，函数 f:Nk→Nf: \mathbb{N}^ k\rightarrow \mathbb{N} 和 g:Nk→Ng: \mathbb{N}^k \rightarrow \mathbb{N} 尽在有穷个点取不同值，证明：ff 为递归函数当且仅当 gg 为递归函数。

证明

设 ff 与 gg 在有穷个点取不同值，从而有 k∈Nk \in \mathbb{N}，使当 x>kx > k 时，f(x)=g(x)f(x) =g(x) ，从而， f(x)={f(x),if x≤kg(x),if x>k f(x) = \left\{\begin{array}{rl} f(x), & \text{if } x \leq k\\ g(x), & \text{if } x >k\end{array}\right. 令 f′(x)={f(x),if x≤k0,if x>k f^\prime(x) = \left\{\begin{array}{ll} f(x), & \text{if }x \leq k\\ 0, &\text{if }x > k \end{array}\right. 易见，f′∈PRFf^\prime \in \mathcal{PRF}

f(x)=f′(x)N(x−˙k)+g(x)N2(x−˙k)f(x) = f^\prime(x)N(x\dot{-}k) + g(x)N^2(x\dot{-}k)

易见，g∈PRF⇒f∈PRFg \in \mathcal{PRF} \Rightarrow f \in \mathcal{PRF}

同理，f∈PRF⇒g∈PRFf \in \mathcal{PRF} \Rightarrow g\in \mathcal{PRF}