くまヒドラ関数

概要

くまヒドラ関数を定義します。まずは一番簡単な$1$変数くまヒドラ関数を定義します。

定義を作るにあたって以下のページを参考にしています。ただし、三関数そのものとくまヒドラ関数に関連はありません。

https://googology.wikia.org/ja/wiki/%E3%83%A6%E3%83%BC%E3%82%B6%E3%83%BC%E3%83%96%E3%83%AD%E3%82%B0:P%E9%80%B2%E5%A4%A7%E5%A5%BD%E3%81%8Dbot/%E3%83%B4%E3%82%A7%E3%83%96%E3%83%AC%E3%83%B3%E9%96%A2%E6%95%B0%E2%86%92%E3%83%96%E3%83%BC%E3%83%95%E3%83%9B%E3%83%AB%E3%83%84%E3%81%AE%CF%88%E9%96%A2%E6%95%B0%E2%86%92%EF%BC%9F

表記

ここでは、表記に用いる文字列について定義する。

$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\})$が存在するとする。
1. $t = c+d$を満たす$(c,d) \in PT \times (T \setminus \{0\})$が存在するならば、$s < t$は以下のいずれかが成り立つことと同値である:
  1. $a < c$である。
  2. $a = c$かつ$b < d$である。
2. $t = o(c)$を満たす$c \in T$が存在するならば、$s < t$は$a < t$と同値である。
$t \neq 0$かつ$s = o(a)$を満たす$a \in T$が存在するとする。
1. $t = c+d$を満たす$(c,d) \in PT \times (T \setminus \{0\})$が存在するならば、$s < t$は$s \leq c$と同値である。
2. $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\})$が存在するとする。
1. $\textrm{dom}(b) \in \{$1,$\omega\}$ならば、$\textrm{dom}(s) := \textrm{dom}(b)$である。
2. $\textrm{dom}(b) \notin \{$1,$\omega\}$とする。
  1. $\textrm{dom}(b) < s$ならば、$\textrm{dom}(s) := \textrm{dom}(b)$である。
  2. そうでないならば、$\textrm{dom}(s) := $\omega$である。
$s = o(a)$を満たす$a \in T$が存在するとする。
1. $\textrm{dom}(a) \in \{0,$1\}$ならば、$\textrm{dom}(s) := s$である。
2. $\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]$と置く。
1. $b' = 0$ならば、$s[t] := a$である。
2. $b' \neq 0$ならば、$s[t] := a + b'$である。

$s = o(a)$を満たす$a \in T$が存在するとする。
1.

ここで$X = \langle X_1, X_2 \rangle $を満たす$X_1,X_2 \in T$が存在するとする。
1. ここで$\textrm{dom}(X_2) = \underline{0}$とする。
  1. もし$\textrm{dom}(X_1) = \underline{0}$ならば、$\textrm{dom}(X) = X$かつ$X[Y] = \underline{0}$である。
  2. もし$\textrm{dom}(X_1) = \underline{1}$ならば、$\textrm{dom}(X) = X$かつ$X[Y]=Y$である。
  3. もし$\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$である。
2. もし$\textrm{dom}(X_2) = \underline{1}$ならば、$\textrm{dom}(X) = \underline{\omega}$である。
  1. もし$Y = \underline{1}$ならば、$X[Y] = \langle X_1, X_2[\underline{0}] \rangle$である。
  2. もし$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})$である。
  3. そうでないならば、$X[Y] = \underline{0}$である。
3. もし$\textrm{dom}(X_2) = \underline{\omega}$ならば、$\textrm{dom}(X) = \underline{\omega}$かつ$X[Y] = \langle X_1 , X_2[Y] \rangle $である。
4. ここで$\textrm{dom}(X_2) \notin \{\underline{0},\underline{1},\underline{\omega}\}$とする。
  1. もし$\textrm{dom}(X_2) < X$ならば、$\textrm{dom}(X) = \textrm{dom}(X_2) $かつ$X[Y] = \langle X_1 , X_2[Y] \rangle $である。
  2. そうでないならば、$\textrm{dom}(X) = \underline{\omega}$である。
    1. $\textrm{dom}(X_2) = \langle Z, 0 \rangle$と置く。
    2. もし$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$である。
    3. そうでないならば、$X[Y] = \langle X_1, X_2[\langle Z[\underline{0}], \underline{0} \rangle] \rangle$である。

急増加関数

ここでは、表記を急増加関数階層とみなす急増加関数を定義する。

計算可能部分写像 \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$とする。
1. $s = 0$ならば、$f_s^m(n) := n+1$である。
2. $s \neq 0$とする。
  1. $\textrm{dom}(s) = $1$ならば、$f_s^m(n) := f_{s[0]}^n(n)$である。
  2. そうでないならば、$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)と名付ける。