概要

くまヒドラ関数を定義します。まずは一番簡単な$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{succ} \colon T & \to & T \\ a & \mapsto & \textrm{succ}(s) \end{eqnarray*} を以下のように再帰的に定める:

$s = 0$ならば、$\textrm{succ}(s) := $1$である。
$s \neq 0$ならば、$\textrm{succ}(s) := s+$1$である。

共終数

ここでは、表記における共終数を定義する。

計算可能全域写像 \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) = 0$とする。
  1. $\textrm{dom}(a) = 0,$1$ならば、$\textrm{dom}(s) := s$である。
  2. $\textrm{dom}(a) \notin \{0,$1\}$ならば、$\textrm{dom}(s) := \textrm{dom}(a)$である。
2. $\textrm{dom}(b) \in \{$1,$\omega\}$ならば、$\textrm{dom}(s) := $\omega$である。
3. $\textrm{dom}(b) \notin \{0,$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) = 0$ならば、$\textrm{dom}(s) := s$である。
2. $\textrm{dom}(a) \neq 0$ならば、$\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 = \textrm{三}_a(b)$を満たす$(a,b) \in T^2$が存在するとする。
1. $\textrm{dom}(b) = 0$とする。
  1. $\textrm{dom}(c) \in \{0,\overline{1}\}$ならば、$s[t] := t$である。
  2. $\textrm{dom}(c) \notin \{0,\overline{1}\}$ならば、$s[t] := \textrm{三}_{c[t]}(0)$である。
2. $\textrm{dom}(b) = \overline{1}$とする。
  1. $t = \overline{1}$ならば、$s[t] := \textrm{三}_a(b[0])$である。
  2. $t = t[0] + \overline{1}$ならば、$s[t] := s[t[0]] + s[\overline{1}]$である。
  3. 上記のいずれの条件も満たさないならば、$s[t] := 0$である。
3. $\textrm{dom}(b) \notin \{0,\overline{1}\}$とする。
  1. $\textrm{dom}(b) < s$ならば、$s[t] := \textrm{三}_a(b[t])$である。
  2. $s \leq \textrm{dom}(b) \neq \textrm{三}_{\textrm{succ}(a)}(0)$とする。
    1. $\textrm{dom}(b) = \textrm{三}_{\textrm{succ}(c)}(0)$かつ$a < c$を満たす$c \in T$が存在するとする。
      1. $t = \textrm{succ}(t[0])$かつ$s[t[0]] = \textrm{三}_a(b')$を満たす$b' \in T$が存在するならば、$s[t] := \textrm{三}_a(b[\textrm{三}_c(b')])$である。
      2. そうでないならば、$s[t] := \textrm{三}_a(b[\textrm{三}_c(0)])$である。
    2. $\textrm{dom}(b) = \textrm{三}_c(d)$かつ$\textrm{dom}(d) = \textrm{三}_{\textrm{succ}(c)}(0)$を満たす$d \in T$が存在するとする。
      1. $t = \textrm{succ}(t[0])$かつ$s[t[0]] = \textrm{三}_a(b')$を満たす$b' \in T$が存在するとする。
        $\beta \in T$を以下のように定める：
        $b' = b_0+\cdots+b_k$かつ$i < k$かつ$\textrm{dom}(d) \leq b_i$を満たす$(i,k) \in \mathbb{N}^2$と$(b_0,\ldots,b_k) \in PT^{k+1}$が存在するならば、そのような$i$の最大値を$i_0$と置くと、$\beta := b_{i_0+1}+\cdots+b_k$である。
        
        そうでないならば、$\beta := b’$である。
        
        $\Gamma \in T$を以下のように定める：
        $\beta < \textrm{dom}(d)$ならば、$\Gamma := \textrm{三}_c(d[\beta])$である。
        
        $\textrm{dom}(d) \leq \beta$ならば、$\Gamma := \textrm{三}_c(d[\textrm{三}_c(\beta)])$である。
        
        $s[t] := \textrm{三}_a(b[\Gamma])$である。
      2. そうでないならば、$s[t] := \textrm{三}_a(b[\textrm{三}_c(d[0])])$である。
  3. $\textrm{dom}(b) = \textrm{三}_{\textrm{succ}(a)}(0)$ならば、$s[t] := t$である。

以上WIP

急増加関数

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

計算可能部分写像 \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. $s = \textrm{succ}(t)$を満たす$t \in T$が存在するならば、$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)と名付ける。