再帰バイナリ後継者と通常の後継者を相互に定義する

Peter Cloteの “Computation Models and Function
Algebras”で、多項式時間関数(PTime)のクラスを次の関数代数で定義できることを読むことができます。

$ [z、s_0、s_1、smash、 pi ^ n_k; C、BRN] $

ここで、セミコロンの前の関数は “頭文字”であり、後の演算子は終了演算子です。

前者はゼロ(z)であり、バイナリ後継$ s_0(n)= 2n $と$ s_1(n)= 2n + 1 $である。 n
right | left | m right |} $ where $ left | n right | left
| m right | $はバイナリの長さと投影$ pi ^ n_k $です。

後者は、構成(C)と表記上の束縛再帰(BRN)である。

begin{align*} f(z,vec m) &= g(vec m), \ f(s_in,vec m)
&= h_i(n,vec m,f(n,vec m)), & iin{0,1} end{align*}

プリミティブ再帰関数は関数代数として特徴付けることができます。

$ [z、s、 pi ^ n_k; C、R] $

前者はゼロ(z)であり、通常の後継$ s(n)= n + 1 $と投影$ pi ^ n_k $です。

後者は、構成(C)と原始再帰(R)です。

begin{align*} f(z,vec m) &= g(vec m), \ f(sn,vec m)
&= h(n,vec m,f(n,vec m)) end{align*}

私の質問は、後継関数に関するもので、次のようなスキームを利用して相互に定義することができます。

– $ s $は$ s_0 $と$ s_1 $から定義できます:

begin{align*} s(z) &= s_1(z), \ s(s_0n) &= s_1(n) \
s(s_1n) &= s_0(s(n)) end{align*}

– $ s_0 $と$ s_1 $はどちらも$ s $から定義できます:

begin{align*} s_0(z) &= z \ s_0(sn) &= ss(s_0n)
end{align*}

begin{align*} s_1(z) &= sz \ s_1(sn) &= ss(s_1n)
end{align*}

それぞれ、

私の質問は次のとおりです.PBimeの定義でバイナリの後継者を使用する理由は何ですか(BRNスキームには2つの$ h_i
$関数が必要です)。 $ s_0 $と$ s_1 $の両方を初期値として使用するPrimitive
Recursive関数を定義しています。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です