2-シフトψ関数

英語版: https://googology.fandom.com/wiki/User_blog:Kanrokoti/2-shifted_%CF%88_function

概要[]

2-シフトψ関数を定義します。2-シフトψ関数は三関数を参考に拡張Buchholz OCFに伴う順序数表記を拡張した表記で、$\psi$の添字に自作の2段階のバッドルート探索を行う数列を埋め込んだものになります。

自作の2段階のバッドルート探索を行う数列を計算機として定式化し、その数列の$(0,0,2,2) = \varphi(\omega^{\omega},0)$までを解析してくださった竹取翁氏と、2-シフトψ関数計算機の作成とバグの指摘をしていただいたNaruyoko氏に感謝します。

2-シフトψ関数[]

表記[]

$0$と$+$と$\psi$と$($と$,$と$)$のみからなる文字列の集合$T$と$PT$を以下のように同時に再帰的に定める:

$0 \in T$である。
いかなる$(a,b) \in PT \times (T \setminus \{0\})$に対しても、$a+b \in T$である。
いかなる$(a,b) \in T^2$に対しても、$\psi(a,b) \in PT \cap T$である。

各$(a,b) \in T^2$に対し$\psi(a,b)$を$\psi_a(b)$と略記する。

計算可能性に意味を持たせるために$\omega$を単なる文字列として扱い、$\mathbb{N}^+ := \mathbb{N} \cup \{\omega\}$と定める。

計算可能全域写像 \begin{eqnarray*} $ \colon \mathbb{N}^+ & \to & T \\ n & \mapsto & $n \end{eqnarray*} を以下のように再帰的に定める:

$n = 0$ならば、$$n := 0$である。
$n = 1$ならば、$$n := \psi_0(0)$である。
$n = \omega$ならば、$$n := \psi_0($1)$である。
$n \notin \{0,1,\omega\}$ならば、$$n := $(n-1)+$1$である。

順序[]

$T$上の$2$項関係$s \le t$と$s \lt t$を以下のように同時に再帰的に定める:

$s \le t$の定義

$s = t$ならば、$s \le t$は真である。
$s \neq t$ならば、$s \le t$は$s \lt t$と同値である。

$s \lt t$の定義

$t = 0$ならば、$s \lt t$は偽である。
$t \neq 0$かつ$s = 0$ならば、$s \lt 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 \lt t$は以下のいずれかが成り立つことと同値である:
  1. $a \lt c$である。
  2. $a = c$かつ$b \lt d$である。
2. $t = \psi_c(d)$を満たす$(c,d) \in T^2$が存在するならば、$s \lt t$は$a \lt t$と同値である。
$t \neq 0$かつ$s = \psi_a(b)$を満たす$(a,b) \in T^2$が存在するとする。
1. $t = c+d$を満たす$(c,d) \in PT \times (T \setminus \{0\})$が存在するならば、$s \lt t$は$s \le c$と同値である。
2. $t = \psi_c(d)$を満たす$(c,d) \in T^2$が存在するならば、$s \lt t$は以下のいずれかが成り立つことと同値である:
  1. $a \lt c$である。
  2. $a = c$かつ$b \lt d$である。

探索関数[]

計算可能全域写像 \begin{eqnarray*} \textrm{BP} \colon T^4 & \to & T \\ (\Gamma,sbp,fbp,cp^-) & \mapsto & \textrm{BP}(\Gamma,sbp,fbp,cp^-) \end{eqnarray*} を以下のように再帰的に定める:

$fbp \le sbp$ならば、$\textrm{BP}(\Gamma,sbp,fbp,cp^-) := \psi_{cp^-}(\Gamma)$である。
$sbp \lt fbp$とする。
1. $\Gamma = \psi_a(b)+c$を満たす$(a,b,c) \in T^2 \times (T \setminus \{0\})$と$sbp = \psi_d(e)+f$を満たす$(d,e,f) \in T^2 \times (T \setminus \{0\})$が存在するとする。
  1. $d = cp^-$かつ$fbp \le b$ならば、$\textrm{BP}(\Gamma,sbp,fbp,cp^-) := \Gamma$である。
  2. そうでないならば、$\textrm{BP}(\Gamma,sbp,fbp,cp^-) := \textrm{BP}(c,f,fbp,cp^-)$である。
2. $\Gamma = \psi_a(b)$を満たす$(a,b) \in T^2$と$sbp = \psi_c(d)$を満たす$(c,d) \in T^2$が存在するとする。
  1. $d = 0$ならば、$\textrm{BP}(\Gamma,sbp,fbp,cp^-) := \textrm{BP}(a,c,fbp,cp^-)$である。
  2. $d \neq 0$ならば、$\textrm{BP}(\Gamma,sbp,fbp,cp^-) := \textrm{BP}(b,d,fbp,cp^-)$である。
3. 上記のいずれの条件も満たさないならば、$\textrm{BP}(\Gamma,sbp,fbp,cp^-) := 0$である。

共終数[]

計算可能全域写像 \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}(s) := \textrm{dom}(b)$である。
$s = \psi_a(b)$を満たす$(a,b) \in T^2$が存在するとする。
1. $\textrm{dom}(b) = 0$とする。
  1. $\textrm{dom}(a) \in \{0,$1\}$ならば、$\textrm{dom}(s) := s$である。
  2. $\textrm{dom}(a) \notin \{0,$1\}$ならば、$\textrm{dom}(s) := \textrm{dom}(a)$である。
2. $\textrm{dom}(b) = $1$ならば、$\textrm{dom}(s) := $\omega$である。
3. $\textrm{dom}(b) \notin \{0,$1\}$とする。
  1. $\textrm{dom}(b) \lt s$ならば、$\textrm{dom}(s) := \textrm{dom}(b)$である。
  2. $s \le \textrm{dom}(b)$ならば、$\textrm{dom}(b) = \psi_c(d)$を満たす$(c,d) \in T^2$を取る。
    1. $\textrm{dom}(d) \lt \textrm{dom}(b)$ならば、$\textrm{dom}(s) := s$である。
    2. $\textrm{dom}(b) \le \textrm{dom}(d)$ならば、$\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 = \psi_a(b)$を満たす$(a,b) \in T^2$が存在するとする。
1. $\textrm{dom}(b) = 0$とする。
  1. $\textrm{dom}(a) \in \{0,$1\}$ならば、$s[t] := t$である。
  2. $\textrm{dom}(a) \notin \{0,$1\}$ならば、$s[t] := \psi_{a[t]}(b)$である。
2. $\textrm{dom}(b) = $1$とする。
  1. $t = t[0]+$1$ならば、$s[t] := s[t[0]]+s[$1]$である。
  2. $t \neq t[0]+$1$ならば、$s[t] := \psi_a(b[0])$である。
3. $\textrm{dom}(b) \notin \{0,$1\}$とする。
  1. $\textrm{dom}(b) \lt s$ならば、$s[t] := \psi_a(b[t])$である。
  2. $s \le \textrm{dom}(b)$ならば、$\textrm{dom}(b) = \psi_c(d)$を満たす$(c,d) \in T^2$を取る。
    1. $\textrm{dom}(d) \lt \textrm{dom}(b)$ならば、$s[t] := \psi_a(b[t])$である。
    2. $\textrm{dom}(b) \le \textrm{dom}(d)$ならば、$\textrm{dom}(d) = \psi_e(0)$を満たす$e \in T$を取る。
      1. $\textrm{dom}(t) = $1$かつ$s[t[0]] = \psi_a(\Gamma)$を満たす$\Gamma \in T$が存在するならば、$s[t] := \psi_a(b[\textrm{BP}(\Gamma,b,d,e[0])])$である。
      2. そうでないならば、$s[t] := \psi_a(b[\psi_{e[0]}(0)])$である。

急増加関数[]

計算可能部分写像 \begin{eqnarray*} f \colon T \times \mathbb{N}^2 & \to & \mathbb{N} \\ (s,m,n) & \mapsto & f_s^m(n) \end{eqnarray*} を以下のように再帰的に定める:

$m = 0$ならば、$f_s^m(n) := n$である。
$m = 1$とする。
1. $\textrm{dom}(s) = 0$ならば、$f_s^m(n) := n+1$である。
2. $\textrm{dom}(s) = $1$ならば、$f_s^m(n) := f_{s[0]}^n(n)$である。
3. $\textrm{dom}(s) \notin \{0,$1\}$ならば、$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 & PT \\ n & \mapsto & \Lambda(n) \end{eqnarray*} を以下のように再帰的に定める:

$n = 0$ならば、$\Lambda(n) := \psi_0(0)$である。
$n \neq 0$ならば、$\Lambda(n) := \psi_{\Lambda(n-1)}(0)$である。

標準形[]

部分集合$OT \subset T$を以下のように再帰的に定める:

いかなる$n \in \mathbb{N}$に対しても、$\psi_0(\psi_0(\Lambda(n))) \in OT$である。
いかなる$(s,n) \in OT \times \mathbb{N}$に対しても、$s[$n] \in OT$である。

私の期待は$(OT,\lt)$が順序数表記になること、すなわち$OT$が再帰的かつ$\lt$の$OT$への制限が整列順序になることである。