日記 (2025 年 12 月 26 日)
前回までで、 原始再帰的な範囲内で可能な操作を一通り列挙した。
今回は、 その応用として、 素数に関するいくつかの関数とそれを用いた自然数列のコーディングについて考える。
なお今後は、 前回の最後にまとめた対象や操作が原始再帰的であることは、 該当する命題や定理を明示することなく使用する。
まずは準備として、 素数に関する関数や関係を定義しよう。
命題 5.1.
関係 Prime⊆ を
x∈Prime:⟺x は素数
で定めると、 これは原始再帰的である。
証明.
素数とは、 1 より大きくて自分自身未満の数の積で表せない数のことである。
したがって、
x∈Prime⟺x>1AND∀q<x∀r<x(x≠q·r)
であるが、 右辺は原始再帰的なものの組み合わせであるから、 Prime も原始再帰的である。
命題 5.2.
全域関数 pr:→ を
pr(x):=x 番目の素数
で定めると、 これは原始再帰的である。
ただし、 素数の番号は 0 から数えるものとする。
すなわち、 例えば pr(0)=2, pr(1)=3, ⋯ である。
証明.
pr を原始再帰の形で書くことを試みる。
pr(0)=2 であるから、 後は pr(x+1) を x と pr(x) の式で表せば良い。
pr(x+1) とは p:=pr(x) の次の素数のことだから、 有界最小化演算子を用いて探せば良い。
しかし、 そのためには探す上界を決める必要がある。
幸い、 p の次の素数は必ず p!+1 以下である。
なぜなら、 p!+1 は p 以下のどんな素数でもわり切れないため、 p!+1 の素因数は全て p より大きい。
すなわち、 p より大きく p!+1 以下の素数が存在することになるため、 p の次の素数は少なくともこの範囲内にある。
以上の考察から pr は、
pr(0) = 2 pr(x+1) = μt<pr(x)!+2.(t∈PrimeANDt>pr(x))
という原始再帰の形で書ける。
命題 5.1 によって Prime は原始再帰的であり、 それ以外の演算も原始再帰的であることが分かっているため、 この pr も原始再帰的である。
素因数分解の一意性を用いることで、 自然数の列を可逆な方式で 1 つの自然数にコーディングすることができる。
具体的には、 次のようにすれば良い。
命題 5.3.
全域関数 ⟨-⟩:k→ を
⟨x0,⋯,xk−1⟩:=pr(0)x0+1⋯pr(k−1)xk−1+1
で定めると、 これは原始再帰的である。
証明.
命題 5.2 によって pr は原始再帰的であり、 それ以外の演算も原始再帰的であることが分かっているため、 この関数も原始再帰的である。
例えば、 ⟨5,2⟩=26·33=1728 や ⟨4,1,0,3⟩=25·32·51·74=3457440 などとなる。
k=0 の場合は空配列のコーディングと見なすことができ、 ⟨⟩=1 となる。
とは言え、 具体的な数値に特に意味はなく、 原始再帰的な方法でコーディングが可能であるという点が重要である。
この列のコーディングでは指数に 1 をたしているが、 これはコーディングされた数からもとの列の長さを復元できるようにするためである。
この取得ももちろん原始再帰的に可能である。
命題 5.4.
全域関数 len:→ であって、 任意の数 x0,⋯,xk−1∈ に対し、
len(⟨x0,⋯,xk−1⟩)=k
を満たし、 さらに原始再帰的なものが存在する。
証明.
列のコーディングの定義から、 コーディングを素因数分解したときに、 指数が 0 になる最小の素数の番号がもともとの列の長さである。
ある素数の指数が 0 であるとはその素数でわり切れないということなので、 len は、
len(σ):=μt<σ.pr(t)∤σ
と定義すれば良い。
命題 5.2 によって pr は原始再帰的だから、 この関数も原始再帰的である。
蛇足だが、 列のコーディングは全射ではない。
定義により、 コーディングを素因数分解したときの指数は必ず正のものが並んだ後にずっと 0 が続くという形になるので、 例えば 22·30·51=20 はどんな列のコーディングにもならない。
しかし、 上で構成した len は全域関数なので、 列のコーディングにならないこのような数に対しても値は返され、 実際 len(20)=1 である。
この値に意味はないが、 かと言って今後の理論でこれが問題になることもないので、 特に気にしないでおく。
さて話を戻して、 列のコーディングから各要素を取得するのも原始再帰的にできる。
命題 5.5.
全域関数 @:2→ であって、 任意の数 x0,⋯,xk−1,y∈ に対し、 y<k ならば、
⟨x0,⋯,xk−1⟩@y=xy
を満たし、 さらに原始再帰的なものが存在する。
証明.
コーディングの定義から、 σ@y とは σ を素因数分解したときの pr(y) の指数から 1 をひいた数である。
σ における pr(y) の指数を得るには、 pr(y)1, pr(y)2, ⋯ が順に σ をわり切るか調べていけば良い。
したがって、 これを有界最小化として表現することを考えて、 @ を、
σ@y:=(μt<σ.pr(y)t+1∤σ)∸1
と定義すれば良い。
命題 5.2 によって pr は原始再帰的だから、 この関数も原始再帰的である。
さて以上により、 自然数の列を 1 つの自然数にコーディングしたり逆にデコードしたりする操作を原始再帰的に行えることが分かった。
そのため、 我々は最初から多価関数や多項関係を考えてきたが、 実は 1 価関数や 1 項関係だけを考えれば十分だったことになる。
この考察を定理の形でまとめておこう。
定理 5.6.
部分関数 f:k→ に対して、 部分関数 f:→ を
f(σ):=f(σ@0,⋯,σ@(k−1))
で定める。
すると、 f が原始再帰的であることと f が原始再帰的であることは同値である。
証明.
まず、 f が原始再帰的であると仮定する。
命題 5.5 により @ は原始再帰的であったから、 f の上記の定義から f が原始再帰的であることが分かる。
逆に、 f が原始再帰的であると仮定する。
すると、 f が
f(x0,⋯,xk−1)=f(⟨x0,⋯,xk−1⟩)
と書けることに注目すれば、 命題 5.3 により ⟨-⟩ は原始再帰的であったから、 f も原始再帰的であることが分かる。
これにより、 以降は 1 価関数や 1 項関係に対してだけ理論を構築することにして、 多価関数や多項関係を扱う必要が生じたときは上記の方法によって 1 価関数や 1 項関係に変換することにしてしまっても良い。
ただ、 関数や関係が多価であることによって議論が大幅に複雑になるわけでもないので、 今後も変わらず多価関数や多項関係を扱うことにする。
次回は、 原始再帰的にならない関数の例として Ackermann 関数を扱う予定である。
参考文献
- H. B. Enderton (2011) 『Computability Theory』 Academic Press