| s(n) map | |
|---|---|
| Based on | \(f^x(x)\) |
| Growth rate | \(f_{\omega^\omega}(n)\) |
s(n) map is a functional, which is a function which maps functions to functions. It was defined by Japanese googologist Fish in 2002[1] and used to define Fish number 3. The name of the map was taken from the Japanese word shazou, which means mapping.
Definition[]
\begin{eqnarray*} s(1)f & := & g; g(x)=f^x(x) \\ s(n)f & := & g; g(x)=[s(n-1)^x]f(x) (\text{if }n>1) \end{eqnarray*}
Analysis[]
Let \(f(x) = x+1\), and the growth rate can be calculated as:
\begin{eqnarray*} f^2(x) & = & x+2 \\ f^3(x) & = & x+3 \\ s(1)f(x) & = & f^x(x) = x+x = 2x \\ s(1)^2f(x) & = & g^x(x) = 2^x x > 2^x\text{, where }g(x)=2x \\ s(1)^3f(x) & > & h^{x}(x) > 2 \uparrow^2x \text{, where } h(x)=2^x \\ s(2)f(x) & = & s(1)^{x}f(x) > 2\uparrow^xx>A(x,x)=A(1,0,x) \approx f_{\omega}(x) \end{eqnarray*}
Similar calculation can be written with the method of the lambda calculus as[2]
\begin{eqnarray*} f & = & \lambda x.x+1 \\ f^2 & = & ff = (\lambda x.x+1)f = f+1 = \lambda x.x+2 \\ f^n & = & \lambda x.x+n \\ s(1)f & = & \lambda x.2x \\ s(1)^2f & = & s(1)(\lambda x.2x) = \lambda x.2^x x \approx \lambda x.2^x \\ s(1)^3f & \approx & s(1)(\lambda x.2^x) \approx \lambda x.2 \uparrow ^2 x \\ s(1)^4f & \approx & s(1)(\lambda x.2\uparrow ^2 x) \approx \lambda x.2 \uparrow ^3 x \\ s(1)^nf & \approx & s(1)(\lambda x.2\uparrow ^{n-1} x) \approx \lambda x.A(n+1,x) \end{eqnarray*}
Here, \(A\) is Taro's multivariable Ackermann function, where the growth rate in FGH is: \begin{eqnarray*} A(..., a3, a2, a1, a0, n) \approx f_{... + \omega^3･a3 + \omega^2･a2 + \omega･a1 + a0}(n) \end{eqnarray*}
Let \(f(n) = A(X, b, n)\) (X is a vector in any length), and: \begin{eqnarray*} A(X, b+1, n) & = & A(X, b, A(X, b+1, n-1)) \\ & = & f(A(X , b+1, n-1)) \\ & = & f^2(A(X, b+1, n-2)) \\ & = & … = f^n(A(X, b+1, 0)) \\ & \approx & f^n(n) \end{eqnarray*}
Therefore, comparing the 3 functions,
- \(s(1)f(x) = f^x(x)\)
- \(f_{\alpha+1}(n) = f^n_\alpha(n)\)
- \(A(X, b+1, n) = f^n(n)\) where \(f(n) = A(X, b, n)\)
they all have similar growth rate. \(s(1)\) map has the same effect of adding 1 to the ordinal in FGH and adding 1 to the second parameter from right in the Ackermann function. This results in:
\begin{eqnarray*} s(1)s(2)f(x) & \approx & A(1,1,x) \approx f_{\omega + 1}(x) \\ s(1)^2 s(2)f(x) & \approx & A(1,2,x) \approx f_{\omega + 2}(x) \\ s(1)^n s(2)f(x) & \approx & A(1,n,x) \approx f_{\omega + n}(x) \end{eqnarray*}
and by diagonizing \(s(1)\) again,
\begin{eqnarray*} s(2)^2 f(x) = s(1)^x s(2)f(x) \approx A(1,x,x) = A(2,0,x) \approx f_{\omega \times 2}(x) \end{eqnarray*}
Here, the calculation of \(s(2)^2f(3)\) goes as follows:
\begin{eqnarray*} s(2)^2f(3) &=& s(1)^3s(2) f(3) \\ &=& [s(1)^2 s(2)f]^3(3) \\ &=& [s(1)^2 s(2)f]^2[[s(1)s(2)f]^3(3)] \end{eqnarray*}
For this calculation, by changing \(s(2)^2 f\) to \(f_{\omega \times 2}\), \(s(1)^3 s(2)f\) to \(f_{\omega+3}\), \(s(1)^2s(2)f\) to \(f_{\omega+2}\), and \(s(1)s(2)f\) to \(f_{\omega+1}\), respectively, the following is obtained:
\begin{eqnarray*} f_{\omega \times 2}(3) &=& f_{\omega+3}(3) \\ &=& f_{\omega+2}^3(3) \\ &=& f_{\omega+2}^2(f_{\omega+1}^3(3)) \end{eqnarray*}
which shows exactly how FGH is calculated.
Calculation goes in the same way:
\begin{eqnarray*} s(2)^n f(x) & \approx & A(n,0,x) \approx f_{\omega \times n}(x) \\ s(3)f(x) & = & s(2)^{x}f(x) \approx A(x,0,x) = A(1,0,0,x) \approx f_{\omega^2}(x) \\ s(3)^2 f(x) & \approx & A(2,0,0,x) \approx f_{\omega^2 \times 2}(x) \\ s(3)^n f(x) & \approx & A(n,0,0,x) \approx f_{\omega^2 \times n}(x) \\ s(4)f(x) & = & s(3)^{x}f(x) \approx A(x,0,0,x) = A(1,0,0,0,x) \approx f_{\omega^3}(x) \\ s(1)^4 s(2)^3 s(3)^2s(4)f(x) & \approx & A(1,2,3,4,x) \approx f_{\omega^3+\omega^2 \times 2+\omega \times 3 + 4}(x) \\ s(5)f(x) & \approx & f_{\omega^4}(x) \\ s(6)f(x) & \approx & f_{\omega^5}(x) \\ s(n)f(x) & \approx & f_{\omega^{n-1}}(x) \\ s(x)f(x) & \approx & f_{\omega^\omega}(x) \end{eqnarray*}
Therefore, by applying \(s(x)\) map, which diagonizes \(s(n)\) map, to the function \(f(x)=x+1\), the growth rate is \(f_{\omega^\omega}(x)\), similar to array notation and Taro's multivariable Ackermann function.
Sources[]
- ↑ Fish, Googology in Japan - exploring large numbers (2013)
- ↑ Fish "巨大数の世界 (The world of googology)" 数学セミナー (Mathematics seminar) July, 2019. pp. 28--31.
See also[]
By Aeton: Okojo numbers · N-growing hierarchy
By 新井 (Arai): Arai's psi function
By aster: White-aster notation · White-aster
By バシク (BashicuHyudora): Primitive sequence number · Pair sequence number · Bashicu matrix system 1/2/3/4 original idea
By ふぃっしゅ (Fish): Fish numbers (Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7 · S map · SS map · s(n) map · m(n) map · m(m,n) map) · Bashicu matrix system 1/2/3/4 formalisation · TR function (I0 function)
By Gaoji: Weak Buchholz's function
By じぇいそん (Jason): Irrational arrow notation · δOCF · δφ · ε function
By 甘露東風 (Kanrokoti): KumaKuma ψ function
By koteitan: Bashicu matrix system 2.3
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Naruyoko Naruyo: Y sequence formalisation · ω-Y sequence formalisation
By Nayuta Ito: N primitive · Flan numbers (Flan number 1 · Flan number 2 · Flan number 3 · Flan number 4 version 3 · Flan number 5 version 3) · Large Number Lying on the Boundary of the Rule of Touhou Large Number 4 · Googology Wiki can have an article with any gibberish if it's assigned to a number
By Okkuu: Extended Weak Buchholz's function
By p進大好きbot: Ordinal notation associated to Extended Weak Buchholz's function · Ordinal notation associated to Extended Buchholz's function · Naruyoko is the great · Large Number Garden Number
By たろう (Taro): Taro's multivariable Ackermann function
By ゆきと (Yukito): Hyper primitive sequence system · Y sequence original idea · YY sequence · Y function · ω-Y sequence original idea
By バシク (BashicuHyudora): Bashicu matrix system as a notation template
By じぇいそん (Jason): Shifting definition
By mrna: Side nesting
By Nayuta Ito and ゆきと (Yukito): Difference sequence system
By ふぃっしゅ (Fish): Ackermann function
By koteitan: Ackermann function · Beklemishev's worms · KumaKuma ψ function
By Mitsuki1729: Ackermann function · Graham's number · Conway's Tetratri · Fish number 1 · Fish number 2 · Laver table
By みずどら: White-aster notation
By Naruyoko Naruyo: p進大好きbot's Translation map for pair sequence system and Buchholz's ordinal notation · KumaKuma ψ function · Naruyoko is the great
By 猫山にゃん太 (Nekoyama Nyanta): Flan number 4 version 3 · Fish number 5 · Laver table
By Okkuu: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 5 · Fish number 6
By rpakr: p進大好きbot's ordinal notation associated to Extended Weak Buchholz's function · Standardness decision algorithm for Taranovsky's ordinal notation
By ふぃっしゅ (Fish): Computing last 100000 digits of mega · Approximation method for FGH using Arrow notation · Translation map for primitive sequence system and Cantor normal form
By Kihara: Proof of an estimation of TREE sequence · Proof of the incomparability of Busy Beaver function and FGH associated to Kleene's \(\mathcal{O}\)
By koteitan: Translation map for primitive sequence system and Cantor normal form
By Naruyoko Naruyo: Translation map for Extended Weak Buchholz's function and Extended Buchholz's function
By Nayuta Ito: Comparison of Steinhaus-Moser Notation and Ampersand Notation
By Okkuu: Verification of みずどら's computation program of White-aster notation
By p進大好きbot: Proof of the termination of Hyper primitive sequence system · Proof of the termination of Pair sequence number · Proof of the termination of segements of TR function in the base theory under the assumption of the \(\Sigma_1\)-soundness and the pointwise well-definedness of \(\textrm{TR}(T,n)\) for the case where \(T\) is the formalisation of the base theory
By 小林銅蟲 (Kobayashi Doom): Sushi Kokuu Hen
By koteitan: Dancing video of a Gijinka of Fukashigi · Dancing video of a Gijinka of 久界 · Storyteller's theotre video reading Large Number Garden Number aloud
See also: Template:Googology in Asia