UNOCF の定義を試みる (1)

このブログ記事シリーズでは、UNOCF の定義を試みます。

簡単のため「UNOCF の定義を試みる」と書きましたが、UNOCF は記事に書いてある式に誤りがあり、無限ループが発生すると考えられることが指摘されています。なので、ここで定義を試みるのはより正確に述べると「私を含め多くのグーグロジストが UNOCF だと思い込んでいたもの」であり、記事の記述とは矛盾する箇所があることが想定されます。

UNOCF の定義の試みとしては Nayuta Ito 氏による NIECF が有名ですが、共終数や濃度に対応する Cough や Kurd などの関数を使用する NIECF 方式とは異なった方針で定義を進めていく予定です。ただし、NIECF から En、Cmp、<>[] など一部の記号/関数名を借りています。

今回は、\(\varepsilon_0\) に対応すると期待されている ψ(ψ(ψ(...))) までを定義します。

定義

以下、_ は添字を表します。波括弧は添字の範囲を明確にするためのみに使われ、削除しても構いません。

同じ関数/集合内で規則はより上にあるものを優先して適用します。

文字列の集合 En を以下のように定義する。
1. 0 は En の要素である。
2. 文字列 a が En の要素ならば、文字列 ψ(a) も En の要素である。
3. 0 でない文字列 a, b がともに En の要素ならば、文字列 a+b も En の要素である。
4. 上記 1.～3. のいずれにも該当しない文字列は En の要素でない。
En の部分集合 L, S を以下のように定義する。a を En の要素とする。
1. a=0 ならば、a は L の要素でも S の要素でもない。
2. a が En の要素 b を用いて a=ψ(b) と表されるならば、
  1. b=0 ならば、a は S の要素であり L の要素ではない。
  2. そうでないならば、a は L の要素であり S の要素ではない。
3. どちらでもないならば、a は En の要素 b, c を用いて a=b+ψ(c) と表せることが示せる。このとき、
  1. c=0 ならば、a は S の要素であり L の要素ではない。
  2. そうでないならば、a は L の要素であり S の要素ではない。
En の部分集合 P を以下のように定義する。
1. En の要素 a が En の要素 b を用いて a=ψ(b) と表せるとき、またそのときに限り、a は P の要素である。
P の要素 a に対して、N(a) を a の末尾に連続する閉じ括弧 ")" の最大個数とする。
P の要素 a と 1 以上 N(a) 以下の整数 n に対して、P の要素 S_{a,n} を以下のように再帰的に定義する。
1. n=1 ならば、S_{a,n}=a である。
2. そうでないならば、S_{a,n-1} は En の要素 b を用いて S_{a,n-1}=ψ(b) と表されることが示せる。このとき、
  1. b が P の要素ならば、S_{a,n}=b である。
  2. そうでないならば、b は En の要素 c と P の要素 d を用いて b=c+d と表されることが示せる。このとき、S_{a,n}=d である。
P の要素 a と 1 以上 N(a) 未満の整数 n と En の要素 x に対して、En の要素 F_{a,n}(x) を以下のように定義する。
1. S_{a,n} は En の要素 b を用いて S_{a,n}=ψ(b) と表されることが示せる。このとき、
  1. b が P の要素ならば、F_{a,n}(x)=ψ(x) である。
  2. そうでないならば、b は En の要素 c と P の要素 d を用いて b=c+d と表されることが示せる。このとき、
    1. x=0 ならば、F_{a,n}(x)=ψ(c) である。
    2. そうでないならば、F_{a,n}(x)=ψ(c+x) である。
L の要素 a と正の整数 n に対して、En の要素 <a>[n] を以下のように定義する。
1. a が P の要素ならば、<a>[n]=F_a(F_{a,1}(F_{a,2}(...(F_{a,N(a)-2}(F_{a,N(a)-1}(0)+F_{a,N(a)-1}(0)+...+F_{a,N(a)-1}(0)))...))) である。ただし、F_{a,N(a)-1}(0) は n 回繰り返す。
2. そうでないならば、a は En の要素 b と P の要素 c を用いて a=b+c と表せることが示せる。このとき、<a>[n]=b+<c>[n] である。
En の要素 a と正の整数 n に対して、整数 f_a(n) を以下のように定義する。
1. a=0 ならば、f_a(n)=n+1 である。
2. a が S の要素ならば、
  1. a=ψ(0) ならば、f_a(n)=f^n_0(n) である。
  2. そうでないならば、a は En の要素 b を用いて a=b+ψ(0) と表されることが示せる。このとき、f_a(n)=f^n_b(n) である。
3. そうでないならば、a は L の要素であることが示せる。このとき、f_a(n)=f_{<a>[n]}(n) である。

ψ(ψ(ψ(...))) までの定義には必要ないですが、将来必要となるので比較も定義しておきます。

En の要素 a,b について、整数 Cmp(a,b) を以下のように再帰的に定義する。
1. a=0 ならば、
  1. b=0 ならば、Cmp(a,b)=0 である。
  2. そうでないならば、Cmp(a,b)=1 である。
2. b=0 ならば、Cmp(a,b)=-1 である。
3. a が P の要素ならば、
  1. b が P の要素ならば、a, b は En の要素 c, d を用いて a=ψ(c)、b=ψ(d) とそれぞれ表されることが示せる。このとき、Cmp(a,b)=Cmp(c,d) である。
  2. そうでないならば、b は P の要素 c と En の要素 d を用いて b=c+d と表せることが示せる。このとき、
    1. Cmp(a,c)<=0 ならば、Cmp(a,b)=-1 である。
    2. そうでないならば、Cmp(a,b)=1 であるり
4. そうでないならば、a は P の要素 c と En の要素 d を用いて a=c+d と表されることが示せる。このとき、
  1. b が P の要素ならば、Cmp(a,b)=-Cmp(b,a) である。
  2. そうでないならば、b は P の要素 e と En の要素 f を用いて b=e+f と表されることが示せる。このとき、
    1. Cmp(c,e)≠0 ならば、Cmp(a,b)=Cmp(c,e) である。
    2. そうでないならば、Cmp(a,b)=Cmp(d,f) である。

計算例

a=ψ(ψ(ψ(ψ(ψ(0))))+ψ(ψ(ψ(0)+ψ(0))+ψ(0)))
- F_a(x)=x
- N(a)=3
- S_{a,1}=ψ(ψ(ψ(ψ(ψ(0))))+ψ(ψ(ψ(0)+ψ(0))+ψ(0)))
- S_{a,2}=ψ(ψ(ψ(0)+ψ(0))+ψ(0))
- S_{a,3}=ψ(0)
- F_{a,1}(x)=ψ(ψ(ψ(ψ(ψ(0))))+x)
- F_{a,2}(x)=ψ(ψ(ψ(0)+ψ(0))+x)
- <a>[1]=F_a(F_{a,1}(F_{a,2}(0)))=ψ(ψ(ψ(ψ(ψ(0))))+ψ(ψ(ψ(0)+ψ(0)))
- <a>[2]=F_a(F_{a,1}(F_{a,2}(0)+F_{a,2}(0)))=ψ(ψ(ψ(ψ(ψ(0))))+ψ(ψ(ψ(0)+ψ(0))+ψ(ψ(ψ(0)+ψ(0)))