変更：ユーザーブログ:Kanrokoti/くまヒドラ関数

2021年11月18日 (木) 23:08時点における最新版

英語版 https://googology.wikia.org/wiki/User_blog:Kanrokoti/An_attempt_to_embed_nesting_into_a_parallel_relations

概要

くまヒドラ関数を定義します。並列関係にネスト構造を埋め込む試みです。p進大好きbot氏による拡張Buchholz OCFに伴う順序数表記を元にしました。

Naruyoko氏によるくまヒドラ関数計算機はこちら

$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$である。

略記

$0$を$$0$と略記し、$o(0)$を$$1$と略記し、$n \in (\mathbb{N} \setminus \{0,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) := \textrm{dom}(a)$である。

基本列

ここでは、表記の基本列を$\textrm{dom}$を用いて定義する。

計算可能全域写像 \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\})$が存在するとする。
1. $\textrm{dom}(b) = $1$とする。
  1. $b[0] = 0$ならば、$s[t] := a$である。
  2. そうでないならば、$s[t] := a+b[0]$である。
2. $\textrm{dom}(b) = $\omega$とする。
  1. $b[t] = 0$ならば、$s[t] := a$である。
  2. そうでないならば、$s[t] := a+b[t]$である。
3. $\textrm{dom}(b) \notin \{$1,$\omega\}$とする。
  1. $\textrm{dom}(b) < s$とする。
    1. $b[t] = 0$ならば、$s[t] := a$である。
    2. そうでないならば、$s[t] := a+b[t]$である。
  2. そうでないならば、$\textrm{dom}(b) = o(c)$と置く。
    1. $t = $i$を満たす$i \in (\mathbb{N} \setminus \{0\})$が存在し、かつ$s[t[0]] = a+\Gamma$を満たす$\Gamma \in T$が一意に存在するならば、$s[t] := a+b[o(c[0])+\Gamma]$である。
    2. そうでないならば、$s[t] := a+b[o(c[0])]$である。
$s = o(a)$を満たす$a \in T$が存在するとする。
1. $\textrm{dom}(a) = 0$ならば、$s[t] := 0$である。
2. $\textrm{dom}(a) = $1$ならば、$s[t] := t$である。
3. $\textrm{dom}(a) \notin \{0,$1\}$ならば、$s[t] := o(a[t])$である。

急増加関数

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

計算可能全域写像 \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)と名付ける。

期待

ここでは、表記が対応して欲しい順序数をいくつか挙げる。

$o(0) = 1$

$o(0)+o(o(0)) = \omega$

$o(0)+o(o(0))+o(0)+o(o(0)) = \omega \times 2$

$o(0)+o(o(0))+o(o(0)) = \omega^2$

$o(0)+o(o(0)+o(0)) = \omega^\omega$

$o(0)+o(o(0)+o(o(0))) = \varepsilon_0$

$o(0)+o(o(0)+o(o(0))+o(0)) = \varepsilon_{\omega}$

$o(0)+o(o(0)+o(o(0))+o(0)+o(0)) = \varepsilon_{\omega^\omega}$

$o(0)+o(o(0)+o(o(0))+o(0)+o(o(0))) = \varepsilon_{\varepsilon_0}$

$o(0)+o(o(0)+o(o(0))+o(o(0))) = \zeta_0$

$o(0)+o(o(0)+o(o(0)+o(0))) = \varphi(\omega,0)$

$o(0)+o(o(o(0))) = \Gamma_0$

@@ 1行目: / 1行目: @@
+英語版
-== 概要 ==
+https://googology.wikia.org/wiki/User_blog:Kanrokoti/An_attempt_to_embed_nesting_into_a_parallel_relations
-くまヒドラ関数を定義します。まずは一番簡単な\(1\)変数くまヒドラ関数を定義します。
+== 概要 ==
-定義を作るにあたって以下のページを参考にしています。ただし、三関数そのものとくまヒドラ関数に関連はありません。
+くまヒドラ関数を定義します。並列関係にネスト構造を埋め込む試みです。[[利用者:p進大好きbot|p進大好きbot]]氏による[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/%E6%8B%A1%E5%BC%B5Buchholz_OCF%E3%81%AB%E4%BC%B4%E3%81%86%E9%A0%86%E5%BA%8F%E6%95%B0%E8%A1%A8%E8%A8%98 拡張Buchholz OCFに伴う順序数表記]を元にしました。
+[[利用者:Naruyoko|Naruyoko]]氏による[https://naruyoko.github.io/googology/kumaHydra/implementation.html くまヒドラ関数計算機はこちら]
-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
+== \(1\)変数くまヒドラ関数 ==
-== 表記 ==
+=== 表記 ===
 ここでは、表記に用いる文字列について定義する。
@@ 18行目: / 20行目: @@
-== 略記 ==
+=== 略記 ===
-\(o(0)\)を\($1\)と略記し、\(n \in \mathbb{N} \land n \gt 1\)に対し\(\underbrace{$1+ \dots +$1}_{$1がn個}\)を\($n\)と略記し、\(o(0)+o($1)\)を\($\omega\)と略記する。
+\(0\)を\($0\)と略記し、\(o(0)\)を\($1\)と略記し、\(n \in (\mathbb{N} \setminus \{0,1\})\)に対し\(\underbrace{$1+ \dots +$1}_{$1がn個}\)を\($n\)と略記し、\(o(0)+o($1)\)を\($\omega\)と略記する。
-== 順序 ==
+=== 順序 ===
-ここでは、表記における辞書式順序の大小関係を定める。
+ここでは、表記における大小関係を辞書式順序で定める。
 \(T\)上の\(2\)項関係\(s \leq t\)と\(s < t\)を以下のように同時に再帰的に定める:
@@ 45行目: / 47行目: @@
-== 共終数 ==
+=== 共終数 ===
 ここでは、表記における共終数を定義する。
@@ 53行目: / 55行目: @@
 s & \mapsto & \textrm{dom}(s)
 \end{eqnarray*}
-を以下のように再帰的に定める：
+を以下のように再帰的に定める:
 # \(s = 0\)ならば、\(\textrm{dom}(s) := 0\)である。
 # \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するとする。
@@ 62行目: / 64行目: @@
 # \(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\)である。
+## \(\textrm{dom}(a) \notin \{0,$1\}\)ならば、\(\textrm{dom}(s) := \textrm{dom}(a)\)である。
-== 基本列 ==
+=== 基本列 ===
+ここでは、表記の基本列を\(\textrm{dom}\)を用いて定義する。
 計算可能全域写像
@@ 73行目: / 76行目: @@
 (s,t) & \mapsto & s[t]
 \end{eqnarray*}
-を以下のように再帰的に定める：
+を以下のように再帰的に定める:
 # \(s = 0\)ならば、\(s[t] := 0\)である。
+# \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するとする。
+## \(\textrm{dom}(b) = $1\)とする。
+### \(b[0] = 0\)ならば、\(s[t] := a\)である。
-# \(s = a+b\)を満たす\((a,b) \in PT \times (T \setminus \{0\})\)が存在するとし、\(b' := b[t]\)と置く。
-## \(b' = 0\)ならば、\(s[t] := a\)である。
+### そうでないならば、\(s[t] := a+b[0]\)である。
-## \(b' \neq 0\)ならば、\(s[t] := a + b'\)である。
+## \(\textrm{dom}(b) = $\omega\)とする。
-# \(s = \textrm{三}_a(b)\)を満たす\((a,b) \in T^2\)が存在するとする。
+### \(b[t] = 0\)ならば、\(s[t] := a\)である。
-## \(\textrm{dom}(b) = 0\)とする。
+### そうでないならば、\(s[t] := a+b[t]\)である。
-### \(\textrm{dom}(c) \in \{0,\overline{1}\}\)ならば、\(s[t] := t\)である。
+## \(\textrm{dom}(b) \notin \{$1,$\omega\}\)とする。
-### \(\textrm{dom}(c) \notin \{0,\overline{1}\}\)ならば、\(s[t] := \textrm{三}_{c[t]}(0)\)である。
+### \(\textrm{dom}(b) < s\)とする。
-## \(\textrm{dom}(b) = \overline{1}\)とする。
+#### \(b[t] = 0\)ならば、\(s[t] := a\)である。
-### \(t = \overline{1}\)ならば、\(s[t] := \textrm{三}_a(b[0])\)である。
+#### そうでないならば、\(s[t] := a+b[t]\)である。
+### そうでないならば、\(\textrm{dom}(b) = o(c)\)と置く。
-### \(t = t[0] + \overline{1}\)ならば、\(s[t] := s[t[0]] + s[\overline{1}]\)である。
-### 上記のいずれの条件も満たさないならば、\(s[t] := 0\)である。
+#### \(t = $i\)を満たす\(i \in (\mathbb{N} \setminus \{0\})\)が存在し、かつ\(s[t[0]] = a+\Gamma\)を満たす\(\Gamma \in T\)が一意に存在するならば、\(s[t] := a+b[o(c[0])+\Gamma]\)である。
+#### そうでないならば、\(s[t] := a+b[o(c[0])]\)である。
-## \(\textrm{dom}(b) \notin \{0,\overline{1}\}\)とする。
-### \(\textrm{dom}(b) < s\)ならば、\(s[t] := \textrm{三}_a(b[t])\)である。
+# \(s = o(a)\)を満たす\(a \in T\)が存在するとする。
-### \(s \leq \textrm{dom}(b) \neq \textrm{三}_{\textrm{succ}(a)}(0)\)とする。
+## \(\textrm{dom}(a) = 0\)ならば、\(s[t] := 0\)である。
-#### \(\textrm{dom}(b) = \textrm{三}_{\textrm{succ}(c)}(0)\)かつ\(a < c\)を満たす\(c \in T\)が存在するとする。
+## \(\textrm{dom}(a) = $1\)ならば、\(s[t] := t\)である。
-##### \(t = \textrm{succ}(t[0])\)かつ\(s[t[0]] = \textrm{三}_a(b')\)を満たす\(b' \in T\)が存在するならば、\(s[t] := \textrm{三}_a(b[\textrm{三}_c(b')])\)である。
+## \(\textrm{dom}(a) \notin \{0,$1\}\)ならば、\(s[t] := o(a[t])\)である。
-##### そうでないならば、\(s[t] := \textrm{三}_a(b[\textrm{三}_c(0)])\)である。
-#### \(\textrm{dom}(b) = \textrm{三}_c(d)\)かつ\(\textrm{dom}(d) = \textrm{三}_{\textrm{succ}(c)}(0)\)を満たす\(d \in T\)が存在するとする。
-##### \(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])\)である。
-##### そうでないならば、\(s[t] := \textrm{三}_a(b[\textrm{三}_c(d[0])])\)である。
-### \(\textrm{dom}(b) = \textrm{三}_{\textrm{succ}(a)}(0)\)ならば、\(s[t] := t\)である。
-== 急増加関数 ==
+=== 急増加関数 ===
 ここでは、表記を急増加関数階層とみなす急増加関数を定義する。
-計算可能部分写像
+計算可能全域写像
 \begin{eqnarray*}
 f \colon T \times \mathbb{N} \times \mathbb{N} & \to & \mathbb{N} \\
@@ 121行目: / 112行目: @@
 ## \(s = 0\)ならば、\(f_s^m(n) := n+1\)である。
 ## \(s \neq 0\)とする。
-###\(\textrm{dom}(s) = $1\)ならば、\(f_s^m(n) := f_{s[0]}^n(n)\)である。
+### \(\textrm{dom}(s) = $1\)ならば、\(f_s^m(n) := f_{s[0]}^n(n)\)である。
-###そうでないならば、\(f_s^m(n) := f_{s[$n]}^1(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))\)である。
-== 限界関数 ==
+=== 限界関数 ===
 ここでは、表記の限界を定める。
@@ 150行目: / 141行目: @@
-== 命名 ==
+=== 命名 ===
 \(F(10^{100})\)を「1変数くまヒドラ数」と名付ける。
 表記の限界に対応する順序数を「1-Kuma Hydra ordinal」(1-KHO)と名付ける。
+=== 期待 ===
+ここでは、表記が対応して欲しい順序数をいくつか挙げる。
+\(o(0) = 1\)
+\(o(0)+o(o(0)) = \omega\)
+\(o(0)+o(o(0))+o(0)+o(o(0)) = \omega \times 2\)
+\(o(0)+o(o(0))+o(o(0)) = \omega^2\)
+\(o(0)+o(o(0)+o(0)) = \omega^\omega\)
+\(o(0)+o(o(0)+o(o(0))) = \varepsilon_0\)
+\(o(0)+o(o(0)+o(o(0))+o(0)) = \varepsilon_{\omega}\)
+\(o(0)+o(o(0)+o(o(0))+o(0)+o(0)) = \varepsilon_{\omega^\omega}\)
+\(o(0)+o(o(0)+o(o(0))+o(0)+o(o(0))) = \varepsilon_{\varepsilon_0}\)
+\(o(0)+o(o(0)+o(o(0))+o(o(0))) = \zeta_0\)
+\(o(0)+o(o(0)+o(o(0)+o(0))) = \varphi(\omega,0)\)
+\(o(0)+o(o(o(0))) = \Gamma_0\)