澳门永利最老登录入口

書名：信息、算法與編碼
作者名：陸宏
本章字數： 2866字
更新時間： 2020-09-11 16:53:12

第二章　生成可計算性函數

§2.1　生成可計算性函數

如何用已知的簡單的可計算性函數生成其他可計算性函數？是否所有可計算性函數均可由簡單的可計算性函數生成？

1．處處有定義的函數叫作全函數，否則叫作半函數或部分函數.最簡單、最基本的函數有三個，即

（1）零函數，O（x）=0，其值恒為0；

（2）廣義幺函數或射影函數；

（3）后繼函數，S（x）=x+1.

這三個函數的合稱就叫作本原函數.本原函數是可計算性函數.事實上，這三個函數的程序分別為Z（1），T（i，1）和S（1）.

2．如何合并程序？設P、Q為兩個程序，如何編寫一個新程序，使它具有功能：先做P后做Q.這涉及一些技術問題.第一個問題：設P=I1，I2，…，Is.我們將P標準化，即將P中的所有躍指令J（m，n，q）中q限制為q≤s+1.

第二個問題就是考慮Q中的所有躍指令.Q中的躍指令J（m，n，q）可能要求跳回去執行Q中的第q條指令，顯然這應該是復合程序中的第s+q條指令，因此須變為J（m，n，s+q）.

因此P、Q合并程序應該通過以下的方式合并：先將P，Q標準化；將它們合并在一起，記為PQ，同時將Q中的所有躍指令轉變為J（m，n，s+q）.

3．如何編寫一個程序Q使得它可以調用子程序P.關鍵在于找到一些存儲單元，使得在程序P運行的過程中存儲單元是不受計算影響的.因為P有窮，故存在一個最小的數u，使得u以后的存儲單元在P中未被敘述過，從而不被程序P的計算影響.記u為ρ（P）.

我們記P[l1，l2，…，ln→l]為下面的程序：

T（l1，1）；T（l2，2）；…；T（ln，n）；Z（n+1）；…；Z（ρ（P））；P；T（1，l）.

其意圖為：任何一個程序在開始運算時，變元x=（x1，x2，…，xn）中的數依次放在存儲單元中，由于其他子程序在運算中可能會改變前n個存儲單元中的數字，故我們首先得將x=（x1，x2，…，xn）從受保護的存儲單元中的中傳遞到R1，…，Rn中，再將Rn+1，…，Rρ（P）清零；其次用程序P計算f（x），并將結果放在R1中；最后再將R1放在Rl中并停機.

定理2.1.1　（替換可計算定理）設f（y1，…，yk），g1（x），…，gk（x）為可計算函數，其中x=（x1，x2，…，xn），則h（x）=f（g1（x），g2（x），…，gk（x））可計算.

證明：設F，G1，…，Gk分別為計算f，g1，…，gk的標準程序.現編寫用于計算h的自然程序H.

令m=max｛n，k，ρ（F），ρ（G1），ρ（G2），…，ρ（Gk）｝.存儲x于Rm+1，…，Rm+n.另外將Rm+n+1，…，Rm+n+k用于存儲g1（x），g2（x），…，gk（x）.

程序H為

T（1，m+1）；…；T（n，m+n）；

G1[m+1，m+2，…，m+n→m+n+1]；

Gk[m+1，m+2，…，m+n→m+n+k]；

F[m+n+1，…，m+n+k→1]　　□

例2.1.1　f（x，y）=（x+y）2可計算.事實上，由例題1.3.1、1.3.4知加法x+y、乘法xy可計算，故由替換定理知f（x，y）=（x+y）（x+y）可計算.

下面我們來定義原始遞歸函數.

定義2.1.1　已知函數f（x1，x2，…，xn），g（x1，x2，…，xn），下式

定義的函數h稱為由f，g原始遞歸而得.這種模式稱為原始遞歸模式.原始遞歸模式不要求f，g是全函數，只要求：

（1）（x1，x2，…，xn）∈dom（h）?（x1，x2，…，xn）∈dom（f）；

（2）（x1，x2，…，xn，y+1）∈dom（h）?（x1，x2，…，xn）∈dom（f）；

（3）且（x1，x2，…，xn，y，h（x1，x2，…，xn，y））∈dom（g）.

例2.1.2　令f（x，y）=x+y，則f（x，y）=x+y可定義為

例2.1.3　令g（x，y）=xy，則g（x，y）=xy可定義為

定理2.1.2　（遞歸函數可計算定理）設f（x），g（x，y，z）為可計算函數，其中x=（x1，x2，…，xn）.則由f，g生成的遞歸函數 h（x，y）可計算.其中

證明：設F，G分別為用于計算f，g的具有標準形式的程序.現編寫用于計算h的自然程序H.令m=max（n+2，k，ρ（F），ρ（G））.存儲x，y于Rm+1，…，Rm+n+1.它們之后的兩個存儲單元用于存儲k和h（x，k），k起記數作用，k=1，2，…，y.令t=m+n.程序H為

T（1，m+1）；…；T（n+1，m+n+1）；

F[1，2，…，n→t+3]；

Iq：J（t+2，t+1，p）；

G[m+1，m+2，…，m+n，t+2，t+3→t+3]；

S（t+2）；

J（1，1，q）；

Ip：T（t+3，1）.

遞歸函數特點是：只有依次計算完h（u，0），h（u，1），h（u，2）…之后，才能把任何一個 h（u，x）的值都算出來.

例2.1.4　證明：x！+（x+y）可計算.

證明：

定理2.1.3　下列函數是可計算的.（1）x+y；（2）xy；（3）xy；（4）x?1；（5）x?y；（6）sg（x）；（7）|x-y|；（8）x！；（9）min（x，y）；（10）max（x，y）；（11）rm（x，y）=y除以x的余數（為方便起見，我們規定rm（0，y）=y）；（12）qt（x，y）=y除以x的商（為方便起見，我們規定qt（0，y）=y）；

（為方便起見，我們規定0|0，但是0不整除y，如果y≠0）.

證明：（4）

（6）

（7）|x-y|=（x?y）+（y?x）

（9）min（x，y）=x?（x?y）

（10）max（x，y）=x+（y?x）

（11）我們想證明rm（x，y）=y除以x時的余數可計算，我們有

這就給出了下面的遞歸定義：

第二個等式可以寫成

rm（x，y+1）=g（x，rm（x，y））

其中g（x，z）=（z+1）sg（|x-（z+1）|）且g是一個多次用替換運算計算的可計算函數.

（12）我們想證明qt（x，y）=y除以x時的商可計算，因為

我們有下面的遞歸表達式

（13）

可計算，因為div（x，y）=（rm（x，y））.　　□

例2.1.5　令π（x，y）=2x×3y，證明π為可計算的雙射，且函數π1，π2滿足π（π1（z），π2（z））=z是可計算的.

證明：F，G，H，I分別為用于計算qt，div，乘方，?運算的標準程序.現編寫用于計算π1，π2的程序，即?z要找到π1（z），π2（z）使得π（π1（z），π2（z））=z.令m=max（n+2，k，ρ（F），ρ（G），ρ（H），ρ（I））.存儲z，k，2，2k，z/2k，l，3，3l，（z/2k）/3l，1分別于Rm+1，…，Rm+10.其中用于存儲k和l的兩個存儲單元起記數作用．程序為