TSS-ψ関数

英語版 https://googology.wikia.org/wiki/User_blog:Kanrokoti/TSS-%CF%88_Function

概要[]

TSS-ψ関数を定義します。拡張Buchholz OCFに伴う順序数表記を元に、3行BM4(BM2.3)への対応を目指した表記です。上昇関数はBM4(BM2.3)の挙動を参考にしつつも、アルゴリズム自体はオリジナルとなっています。

Naruyoko氏によるTSS-ψ関数計算機はこちら

類似研究: BMOCF

Special thanks: p進大好きbot Naruyoko Koteitan

定義の書き直しをしました

TSS-ψ関数[]

表記[]

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

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

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

$0$を$$0$と略記し、$\psi_0^0(0)$を$$1$と略記し、$n \in (\mathbb{N} \setminus \{0,1\})$に対し$\underbrace{$1+ \dots +$1}_{$1がn個}$を$$n$と略記し、$\psi_0^0($1)$を$$\omega$と略記する。

部分集合$RT \subset T$と$RPT \subset PT$を以下のように同時に再帰的に定める:

$0 \in RT$である。
いかなる$(a,b) \in RPT \times (RT \setminus \{0\})$に対しても、$a+b \in RT$である。
$a \le b$を満たすいかなる$(a,b,c) \in \mathbb{N}^2 \times RT$に対しても、$\psi_{$a}^{$b}(c) \in RPT \cap RT$である。

上昇関数[]

ここでは、上昇関数を定義する。

計算可能全域写像 \begin{eqnarray*} \Delta \colon RT \times (\mathbb{N} \setminus \{0\}) \times \mathbb{N} \times \{0,1\} & \to & RT \\ (s,\delta,br,pr) & \mapsto & \Delta(s,\delta,br,pr) \end{eqnarray*} を以下のように再帰的に定める:

$s = 0$ならば、$\Delta(s,\delta,br,pr) := 0$である。
$s = a+b$を満たす$(a,b) \in RPT \times (RT \setminus \{0\})$が存在するならば、$\Delta(s,\delta,br,pr) := \Delta(a,\delta,br,pr)+\Delta(b,\delta,br,pr)$である。
$s = \psi_{$a}^{$b}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $br \lt b$ならば、$\Delta(s,\delta,br,pr) := \psi_{$a}^{$b+$\delta}(\Delta(c,\delta,br,pr))$である。
2. $br \ge b$とする。
  1. $pr = 0$ならば、$\Delta(s,\delta,br,pr) := \psi_{$a}^{$b+$\delta}(\Delta(c,\delta,br,1))$である。
  2. そうでないならば、$\Delta(s,\delta,br,pr) := \psi_{$a}^{$b}(c)$である。

共終数[]

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

計算可能全域写像 \begin{eqnarray*} \textrm{cp} \colon RT & \to & RT \\ s & \mapsto & \textrm{cp}(s) \end{eqnarray*} を以下のように再帰的に定める:

$s = 0$ならば、$\textrm{cp}(s) := 0$である。
$s = a+b$を満たす$(a,b) \in RPT \times (RT \setminus \{0\})$が存在するならば、$\textrm{cp}(s) := \textrm{cp}(b)$である。
$s = \psi_{$a}^{$b}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $\textrm{cp}(c) = 0$ならば、$\textrm{cp}(s) := s$である。
2. そうでないならば、$\textrm{cp}(s) := \textrm{cp}(c)$である。

計算可能全域写像 \begin{eqnarray*} \textrm{dom} \colon RT & \to & RT \\ s & \mapsto & \textrm{dom}(s) \end{eqnarray*} を以下のように再帰的に定める:

$s = 0$ならば、$\textrm{dom}(s) := 0$である。
$s = a+b$を満たす$(a,b) \in RPT \times (RT \setminus \{0\})$が存在するならば、$\textrm{dom}(s) := \textrm{dom}(b)$である。
$s = \psi_{$a}^{$b}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $\textrm{dom}(c) = 0$ならば、$\textrm{dom}(s) := s$である。
2. $\textrm{dom}(c) \in \{$1,$\omega\}$ならば、$\textrm{dom}(s) := $\omega$である。
3. $\textrm{dom}(c) \notin \{0,$1,$\omega\}$とする。$\textrm{dom}(c) = \psi_{$d}^{$e}(f)$を満たす$(d,e,f) \in \mathbb{N} \times (\mathbb{N} \setminus \{0\}) \times RT$が存在する。
  1. $d = 0$とする。
    1. $b \lt e$ならば、$\textrm{dom}(s) := $\omega$である。
    2. そうでないならば、$\textrm{dom}(s) := \textrm{dom}(c)$である。
  2. $d \neq 0$とする。
    1. $a \lt d$とする。
      1. $b \le e$ならば、$\textrm{dom}(s) := $\omega$である。
      2. そうでないならば、$\textrm{dom}(s) := \textrm{dom}(c)$である。
    2. $a = d$とする。
      1. $b \lt e$ならば、$\textrm{dom}(s) := s$である。
      2. そうでないならば、$\textrm{dom}(s) := \textrm{dom}(c)$である。
    3. $a \gt d$ならば、$\textrm{dom}(s) := \textrm{dom}(c)$である。

基本列[]

ここでは、表記の基本列を定義する。

計算可能全域写像 \begin{eqnarray*} [ \ ] \colon RT^2 & \to & RT \\ (s,t) & \mapsto & s[t] \end{eqnarray*} を以下のように再帰的に定める:

$s = 0$ならば、$s[t] := 0$である。
$s = a+b$を満たす$(a,b) \in RPT \times (RT \setminus \{0\})$が存在するならば、$b' := b[t]$と置く。
1. $b' = 0$ならば、$s[t] := a$である。
2. そうでないならば、$s[t] := a+b'$である。
$s = \psi_{$a}^{$b}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $\textrm{dom}(c) = 0$ならば、$s[t] := t$である。
2. $\textrm{dom}(c) = $1$とする。
  1. $t = t[0]+$1$ならば、$s[t] := s[t[0]]+s[$1]$である。
  2. そうでないならば、$s[t] := \psi_{$a}^{$b}(c[0])$である。
3. $\textrm{dom}(c) = $\omega$ならば、$s[t] := \psi_{$a}^{$b}(c[t])$である。
4. $\textrm{dom}(c) \notin \{0,$1,$\omega\}$とする。$\textrm{dom}(c) = \psi_{$d}^{$e}(f)$を満たす$(d,e,f) \in \mathbb{N} \times (\mathbb{N} \setminus \{0\}) \times RT$が存在する。
  1. $d = 0$とする。
    1. $b \lt e$とする。
      1. $t = $i$を満たす$i \in (\mathbb{N} \setminus \{0\})$が存在し、かつ$s[t[0]] = \Gamma$を満たす$\Gamma \in RT$が一意に存在するならば、$s[t] := \psi_{$a}^{$b}(c[\Gamma])$である。
      2. そうでないならば、$s[t] := \psi_{$a}^{$b}(c[0])$である。
    2. そうでないならば、$s[t] := \psi_{$a}^{$b}(c[t])$である。
  2. $d \neq 0$とする。
    1. $a \lt d$とする。
      1. $b \le e$とする。$\textrm{cp}(c) = \psi_{$g}^{$h}(0)$を満たす$(g,h) \in (\mathbb{N} \setminus \{0\})^2$が存在する。$\delta := h-b$と置く。
        $t = $i$を満たす$i \in (\mathbb{N} \setminus \{0\})$が存在し、かつ$s[t[0]] = \Gamma$を満たす$\Gamma \in RT$が一意に存在するならば、$s[t] := \psi_{$a}^{$b}(c[\Delta(\Gamma,\delta,b,0)])$である。
        
        そうでないならば、$s[t] := \psi_{$a}^{$b}(c[0])$である。
      2. そうでないならば、$s[t] := \psi_{$a}^{$b}(c[t])$である。
    2. そうでないならば、$s[t] := \psi_{$a}^{$b}(c[t])$である。

急増加関数[]

ここでは、表記を使った急増加関数を定義する。

計算可能部分写像 \begin{eqnarray*} f \colon RT \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. $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}^2 & \to & RPT \\ (n,m) & \mapsto & \Lambda(n,m) \end{eqnarray*} を以下のように再帰的に定める:

$n \le m$ならば、$\Lambda(n,m) := \psi_0^0(\Lambda(n,m-1))$である。
$n \gt m$とする。$l := n-m$と置く。
1. $m = 0$ならば、$\Lambda(n,m) := \psi_{$l}^{$l}(0)$である。
2. そうでないならば、$\Lambda(n,m) := \psi_{$l}^{$l}(\Lambda(n,m-1))$である。

標準形[]

ここでは、表記の標準形を定める。

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

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

命名[]

計算可能全域写像 \begin{eqnarray*} F \colon \mathbb{N} & \to & \mathbb{N} \\ n & \mapsto & F(n) \end{eqnarray*} を$F(n) := f_{\Lambda(n,n)}(n)$と定める。

$F^{10^{100}}(10^{100})$を「TSS-ψ数」と名付ける。

表記の限界に対応する順序数を「TSS-psi ordinal」(TSSPO)と名付ける。

解析[]

3行BM4(BM2.3)の表記系を$B_3$とする。$\frown$を行列の連結演算子とする。任意の項$s \in OT$が、$\textrm{Trans}(s,0)$によって3行バシク行列に変換されることを目指す。

計算可能全域写像 \begin{eqnarray*} \textrm{Trans} \colon OT \times \mathbb{N} & \to & B_3 \\ (s,t) & \mapsto & \textrm{Trans}(s,t) \end{eqnarray*} を以下のように再帰的に定める:

$s = 0$ならば、$\textrm{Trans}(s,t) := ()$である。
$s = a+b$を満たす$(a,b) \in RPT \times (RT \setminus \{0\})$が存在するならば、$\textrm{Trans}(s,t) := \textrm{Trans}(a,t) \frown \textrm{Trans}(b,t)$である。
$s = \psi_{$a}^{$b}(c)$を満たす$(a,b,c) \in \mathbb{N}^2 \times RT$が存在するとする。
1. $c = 0$ならば、$\textrm{Trans}(s,t) := (t,b,a)$である。
2. そうでないならば、$\textrm{Trans}(s,t) := (t,b,a) \frown \textrm{Trans}(c,t+1)$である。

計算可能全域写像 \begin{eqnarray*} \textrm{F} \colon OT & \to & B_3 \\ s & \mapsto & \textrm{F}(s) \end{eqnarray*} を$\textrm{F}(s) := \textrm{Trans}(s,0)$として定める。