第二章　生成可計(jì)算性函數(shù)

§2.1　生成可計(jì)算性函數(shù)

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

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

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

（2）廣義幺函數(shù)或射影函數(shù)；

（3）后繼函數(shù)，S（x）=x+1.

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

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

第二個(gè)問題就是考慮Q中的所有躍指令.Q中的躍指令J（m，n，q）可能要求跳回去執(zhí)行Q中的第q條指令，顯然這應(yīng)該是復(fù)合程序中的第s+q條指令，因此須變?yōu)镴（m，n，s+q）.

因此P、Q合并程序應(yīng)該通過以下的方式合并：先將P，Q標(biāo)準(zhǔn)化；將它們合并在一起，記為PQ，同時(shí)將Q中的所有躍指令轉(zhuǎn)變?yōu)镴（m，n，s+q）.

3．如何編寫一個(gè)程序Q使得它可以調(diào)用子程序P.關(guān)鍵在于找到一些存儲單元，使得在程序P運(yùn)行的過程中存儲單元是不受計(jì)算影響的.因?yàn)镻有窮，故存在一個(gè)最小的數(shù)u，使得u以后的存儲單元在P中未被敘述過，從而不被程序P的計(jì)算影響.記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）.

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

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

證明：設(shè)F，G1，…，Gk分別為計(jì)算f，g1，…，gk的標(biāo)準(zhǔn)程序.現(xiàn)編寫用于計(jì)算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可計(jì)算.事實(shí)上，由例題1.3.1、1.3.4知加法x+y、乘法xy可計(jì)算，故由替換定理知f（x，y）=（x+y）（x+y）可計(jì)算.

下面我們來定義原始遞歸函數(shù).

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

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

（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　（遞歸函數(shù)可計(jì)算定理）設(shè)f（x），g（x，y，z）為可計(jì)算函數(shù)，其中x=（x1，x2，…，xn）.則由f，g生成的遞歸函數(shù) h（x，y）可計(jì)算.其中

證明：設(shè)F，G分別為用于計(jì)算f，g的具有標(biāo)準(zhǔn)形式的程序.現(xiàn)編寫用于計(jì)算h的自然程序H.令m=max（n+2，k，ρ（F），ρ（G））.存儲x，y于Rm+1，…，Rm+n+1.它們之后的兩個(gè)存儲單元用于存儲k和h（x，k），k起記數(shù)作用，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）.

遞歸函數(shù)特點(diǎn)是：只有依次計(jì)算完h（u，0），h（u，1），h（u，2）…之后，才能把任何一個(gè) h（u，x）的值都算出來.

例2.1.4　證明：x！+（x+y）可計(jì)算.

證明：

定理2.1.3　下列函數(shù)是可計(jì)算的.（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的余數(shù)（為方便起見，我們規(guī)定rm（0，y）=y）；（12）qt（x，y）=y除以x的商（為方便起見，我們規(guī)定qt（0，y）=y）；

（為方便起見，我們規(guī)定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時(shí)的余數(shù)可計(jì)算，我們有

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

第二個(gè)等式可以寫成

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

其中g(shù)（x，z）=（z+1）sg（|x-（z+1）|）且g是一個(gè)多次用替換運(yùn)算計(jì)算的可計(jì)算函數(shù).

（12）我們想證明qt（x，y）=y除以x時(shí)的商可計(jì)算，因?yàn)?/p>

我們有下面的遞歸表達(dá)式

（13）

可計(jì)算，因?yàn)閐iv（x，y）=（rm（x，y））.　　□

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

證明：F，G，H，I分別為用于計(jì)算qt，div，乘方，?運(yùn)算的標(biāo)準(zhǔn)程序.現(xiàn)編寫用于計(jì)算π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的兩個(gè)存儲單元起記數(shù)作用．程序?yàn)?/p>

例2.1.6　令f（x）定義如下：

｛f（n）｝n∈N為Fibonacci序列，而且它是可計(jì)算.

證明：令g（x）=2f（x）3f（x+1），顯然g（0）=2f（0）3f（1）=2132=18=π（π1（18），π2（18））且g（x+1）=.故它是可計(jì)算的.　　□

定理2.1.4　設(shè)f1（x），…，fk（x）是可計(jì)算函數(shù)，M1（x），…，Mk（x）可判定，而且?x M1（x），…，Mk（x）恰好其中之一成立，則下面的g可計(jì)算.

定理2.1.5　設(shè)M（x），Q（x）可判定，則“not M（x）”“M（x）and Q（x）”“M（x）or Q（x）”可判定.

4．受囿算子

我們記μz＜y（…）表示“y的z滿足…”.我們定義

算子μz＜y（…）稱為受囿的極小化算子或受囿的μ算子.

定理2.1.6　設(shè)f（x，y）是全可計(jì)算的，則g（x，y）=μz＜y（f（x，z）=0）也是.

5．極小化算子μy（…）

定理2.1.7　設(shè)f（x，y）為全可計(jì)算函數(shù)，則g（x）=μy（f（x，y）=0）也是.

證明：設(shè)F為用于計(jì)算f的具有標(biāo)準(zhǔn)形式的程序.現(xiàn)編寫用于計(jì)算g的自然程序G.令m=max（n+1，ρ（F））.我們存儲x，k于Rm+1，…，Rm+n+1.程序G為

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

Ip：F[m+1，m+2，…，m+n+1→1]；

J（1，m+n+2，q）；

S（m+n+1）；

J（1，1，p）；

Iq：T（m+n+1，1）.　　□

例2.1.7　如果f（x）是單的全可計(jì)算函數(shù)，則f-1（y）可計(jì)算.

證明：f（x）是單的、全的，故f-1（y）=μx（|f（x）-y|=0）.　　□