概要
くまヒドラ関数を定義します。まずは一番簡単な\(1\)変数くまヒドラ関数を定義します。
定義を作るにあたって以下のページを参考にしています。ただし、三関数そのものとくまヒドラ関数に関連はありません。
表記
ここでは、表記に用いる文字列について定義する。
\(0\)と\(+\)と\(o\)と\((\)と\()\)のみからなる文字列の集合\(T\)と\(PT\)を以下のように同時に再帰的に定める:
- \(0 \in T\)である。
- いかなる\((a,b) \in PT \times (T \setminus \{0\})\)に対しても、\(a+b \in T\)である。
- いかなる\(a \in T\)に対しても、\(o(a) \in PT \cap T\)である。
略記
\(o(0)\)を\($1\)と略記し、\(n \in \mathbb{N} \land n \gt 1\)に対し\(\underbrace{$1+ \dots +$1}_{$1がn個}\)を\($n\)と略記し、\(o(0)+o($1)\)を\($\omega\)と略記する。
順序
ここでは、表記における辞書式順序の大小関係を定める。
\(T\)上の\(2\)項関係\(s \leq t\)と\(s < t\)を以下のように同時に再帰的に定める:
- \(s \leq t\)の定義
- \(s = t\)ならば、\(s \leq t\)は真である。
- \(s \neq t\)ならば、\(s \leq t\)は\(s < t\)と同値である。
- \(s < t\)の定義
- \(t = 0\)ならば、\(s < t\)は偽である。
- \(t \neq 0\)かつ\(s = 0\)ならば、\(s < t\)は真である。
- \(t \neq 0\)かつ\(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するとする。
- \(t = c+d\)を満たす\((c,d) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s < t\)は以下のいずれかが成り立つことと同値である:
- \(a < c\)である。
- \(a = c\)かつ\(b < d\)である。
- \(t = o(c)\)を満たす\(c \in T\)が存在するならば、\(s < t\)は\(a < t\)と同値である。
- \(t = c+d\)を満たす\((c,d) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s < t\)は以下のいずれかが成り立つことと同値である:
- \(t \neq 0\)かつ\(s = o(a)\)を満たす\(a \in T\)が存在するとする。
- \(t = c+d\)を満たす\((c,d) \in PT \times (T \setminus \{0\})\)が存在するならば、\(s < t\)は\(s \leq c\)と同値である。
- \(t = o(c)\)を満たす\(c \in T\)が存在するならば、\(s < t\)は\(a < c\)と同値である。
共終数
ここでは、表記における共終数を定義する。
計算可能全域写像 \begin{eqnarray*} \textrm{dom} \colon T & \to & T \\ s & \mapsto & \textrm{dom}(s) \end{eqnarray*} を以下のように再帰的に定める:
- \(s = 0\)ならば、\(\textrm{dom}(s) := 0\)である。
- \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するとする。
- \(\textrm{dom}(b) \in \{$1,$\omega\}\)ならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
- \(\textrm{dom}(b) \notin \{$1,$\omega\}\)とする。
- \(\textrm{dom}(b) < s\)ならば、\(\textrm{dom}(s) := \textrm{dom}(b)\)である。
- そうでないならば、\(\textrm{dom}(s) := $\omega\)である。
- \(s = o(a)\)を満たす\(a \in T\)が存在するとする。
- \(\textrm{dom}(a) \in \{0,$1\}\)ならば、\(\textrm{dom}(s) := s\)である。
- \(\textrm{dom}(a) \notin \{0,$1\}\)ならば、\(\textrm{dom}(s) := $\omega\)である。
基本列
計算可能全域写像 \begin{eqnarray*} [ \ ] \colon T^2 & \to & T \\ (s,t) & \mapsto & s[t] \end{eqnarray*} を以下のように再帰的に定める:
- \(s = 0\)ならば、\(s[t] := 0\)である。
- \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するとし、\(b' := b[t]\)と置く。
- \(b' = 0\)ならば、\(s[t] := a\)である。
- \(b' \neq 0\)ならば、\(s[t] := a + b'\)である。
- \(s = o(a)\)を満たす\(a \in T\)が存在するとする。
- \(\)
- ここで\(\textrm{dom}(X_2) = \underline{0}\)とする。
- もし\(\textrm{dom}(X_1) = \underline{0}\)ならば、\(X[Y] = \underline{0}\)である。
- もし\(\textrm{dom}(X_1) = \underline{1}\)ならば、\(X[Y]=Y\)である。
- もし\(\textrm{dom}(X_1) \notin \{\underline{0},\underline{1}\}\)ならば、\(\textrm{dom}(X) = \textrm{dom}(X_1)\)かつ\(X[Y] = \langle X_1[Y] , \underline{0} \rangle\)である。
- もし\(\textrm{dom}(X_2) = \underline{1}\)ならば、\(\textrm{dom}(X) = \underline{\omega}\)である。
- もし\(Y = \underline{1}\)ならば、\(X[Y] = \langle X_1, X_2[\underline{0}] \rangle\)である。
- もし\(Y = \underline{k}\) (\(2 \leq k < \infty\))ならば、\(X[Y]=(\underbrace{\langle X_1, X_2[\underline{0}] \rangle, \ldots, \langle X_1, X_2[\underline{0}] \rangle}_{k})\)である。
- そうでないならば、\(X[Y] = \underline{0}\)である。
- もし\(\textrm{dom}(X_2) = \underline{\omega}\)ならば、\(\textrm{dom}(X) = \underline{\omega}\)かつ\(X[Y] = \langle X_1 , X_2[Y] \rangle \)である。
- ここで\(\textrm{dom}(X_2) \notin \{\underline{0},\underline{1},\underline{\omega}\}\)とする。
- もし\(\textrm{dom}(X_2) < X\)ならば、\(\textrm{dom}(X) = \textrm{dom}(X_2) \)かつ\(X[Y] = \langle X_1 , X_2[Y] \rangle \)である。
- そうでないならば、\(\textrm{dom}(X) = \underline{\omega}\)である。
- \(\textrm{dom}(X_2) = \langle Z, 0 \rangle\)と置く。
- もし\(Y = \underline{h}\) (\(1 \leq h < \infty\))かつ\(X[Y[\underline{0}]] = \langle X_1, \Gamma \rangle\)を満たす\(\Gamma \in T\)が存在するならば、\(X[Y]= \langle X_1, X_2[\langle Z[\underline{0}], \Gamma \rangle] \rangle\)である。
- そうでないならば、\(X[Y] = \langle X_1, X_2[\langle Z[\underline{0}], \underline{0} \rangle] \rangle\)である。
- ここで\(\textrm{dom}(X_2) = \underline{0}\)とする。
- もし\(X = (X_1, \ldots,X_m)\)を満たす\(X_1,\ldots,X_m \in PT\) (\(2 \leq m < \infty\))が存在するならば、\(\textrm{dom}(X)=\textrm{dom}(X_m)\)である。
- もし\(X_m[Y] = \underline{0}\)かつ\(m = 2\)ならば、\(X[Y]=X_1\)である。
- もし\(X_m[Y] = \underline{0}\)かつ\(m > 2\)ならば、\(X[Y]=(X_1, \ldots, X_{m-1})\)である。
- もし\(X_m[Y] \in PT\)ならば、\(X[Y]=(X_1, \ldots, X_{m-1},X_m[Y])\)である。
- \(X_m[Y] = (Z_1, \ldots, Z_{m'})\)を満たす\(Z_1, \ldots, Z_{m'} \in PT\) (\(2 \leq m' < \infty\))が存在するならば、\(X[Y]=(X_1, \ldots, X_{m-1}, Z_1, \ldots, Z_{m'})\)である。
急増加関数
ここでは、表記を急増加関数階層とみなす急増加関数を定義する。
計算可能部分写像 \begin{eqnarray*} f \colon T \times \mathbb{N} \times \mathbb{N} & \to & \mathbb{N} \\ (s,m,n) & \mapsto & f_s^m(n) \end{eqnarray*} を以下のように再帰的に定める:
- \(m = 0\)ならば、\(f_s^m(n) := n\)である。
- \(m = 1\)とする。
- \(s = 0\)ならば、\(f_s^m(n) := n+1\)である。
- \(s \neq 0\)とする。
- \(\textrm{dom}(s) = $1\)ならば、\(f_s^m(n) := f_{s[0]}^n(n)\)である。
- そうでないならば、\(f_s^m(n) := f_{s[$n]}^1(n)\)である。
- \(m \notin \{0,1\}\)ならば、\(f_s^m(n) := f_s^1(f_s^{m-1}(n))\)である。
限界関数
ここでは、表記の限界を定める。
計算可能全域写像 \begin{eqnarray*} \Lambda \colon \mathbb{N} & \to & T \\ n & \mapsto & \Lambda(n) \end{eqnarray*} を以下のように再帰的に定める:
- \(n = 0\)ならば、\(\Lambda(n) := o(0)\)である。
- \(n \neq 0\)ならば、\(\Lambda(n) := o(\Lambda(n-1))\)である。
計算可能全域写像 \begin{eqnarray*} F \colon \mathbb{N} & \to & \mathbb{N} \\ n & \mapsto & F(n) \end{eqnarray*} を\(F(n) = f_{o(0)+\Lambda(n)}^n(n)\)と定める。
命名
\(F(10^{100})\)を「1変数くまヒドラ数」と名付ける。
表記の限界に対応する順序数を「1-Kuma Hydra ordinal」(1-KHO)と名付ける。