Mashimo function is a googological function which is intended to work as a scale of various googological numbers[1]. It is now a beta version and it might be updated based on the discussion in this blog post. Mashimo scale is defined with this function. Mashimo is a character in Sushi Kokuuhen.
Definition of Mashimo function \(M(x)\) is as follows.
For \(x \ge 1\), \[M(x) = max(10^{10x}, ^{x/5}e, H(^{x/20}2,2), H(^{H(x-70,2)}3,3), \\ V(x-72), V(3^{x-80}), BHO(x-83), O(x-85), OF(x-86),\\ L(x-90), D(5(x-94),10), \\ FC(x-80), RC(x-120)) \]
For \(0 \le x < 1\), \(M(x) = 10^{10x}\)
For \(x < 0\), \(M(x) = M(-x)^{-1}\)
Here, \(max\) function returns the largest number in the parameters, and several subfunctions of \(H, V, BHO, O, OF, L, D, FC, RC\) are defined in this page. \(M(x)\) is a continuous and strictly monotonically increasing function. Extention of tetration to parameters of real numbers is defined with the method of Tetration#Extension to real heights, i.e.,
\begin{eqnarray*} ^{x}a &=& log_a{(^{x+1}a)} &for& x \le -1 \\ ^{x}a &=& x+1 &for& -1 < x \le 0 \\ ^{x}a &=& a^{(^{x-1}a)} &for& 0 < x \\ \end{eqnarray*}
Subfunctions[]
First of all, for \(x<0\), \(H(x,n) = V(x) = BHO(x) = O(x) = OF(x) = L(x) = D(x,n) = FC(x) = RC(x) = 0\).
H function[]
H function with 2 variables of natural numbers is defined with Hardy function. It is defined as \[H(a,n) = H_\alpha(n)\] where \(a\) is a natural number, \(n \ge 2\) is a natural number, and \(\alpha\) is an ordinal related to \(a\) as follows; write \(a\) with hereditary base-n notation, change \(n\) to \(\omega\), and we get \(\alpha\). For example,
\[H(35,2) = H(2^{2^2+1}+2+1,2) = H_{\omega^{\omega^\omega+1}+\omega+1}(2) \]
Therefore, \(\alpha < \epsilon_0\). Wainer hierarchy is used for fundamental sequence. First parameter of H function is extended to real numbers as follows. Let
\begin{eqnarray*} N &=& floor(a) \\ r &=& a-N \\ H(N,n) &=& H(x,N+1) \\ H(N+1,n) &=& H(y,N+1) \\ \end{eqnarray*}
and define \(H(a,n) = H(N+r,n)\) as
\[H(a,n) = H(x+r(y-x),n+1)\]
For example,
\begin{eqnarray*} H(4,2) &=& H_{\omega^{\omega}}(2) = H_{\omega+2}(2) = H_{\omega+1}(3)\\ &=& H(4,3) \\ H(5,2) &=& H_{\omega^{\omega}+1}(2) = H_{\omega^{\omega}}(3) \\ &=& H(27,3) \\ \end{eqnarray*}
and therefore
\[H(4.3,2) = H(4+0.3(27-4),3) = H(10.9,3) \]
as \(n\) increases, the ordinal in the Hardy function corresponding to the first parameter of H function decreases, and therefore the ordinal finally reaches 0 (this is similar to the proof that Goodstein sequence finally stops). Therefore, by defining
\[H(r,n) = n+r (0 \le r < 1)\]
it is guaranteered that the calculation stops, and \(H(a,n)\) is now defined for \(a \in \mathbb{R}\).
V function[]
V function is defined with Veblen function and Hardy hierarchy as follows.
\[V(\sum_{k=0}^{n} 3^k a_k) = H_{\phi(..., a_3, a_2, a_1, a_0)}(3) \]
Fundamental sequence of \(\epsilon_1 = lim(\epsilon_0+1, \omega^{\epsilon_0+1}, \omega^{\omega^{\epsilon_0+1}}, ...)\) is used, and it is calculated as follows.
\begin{eqnarray*} V(0) &=& H_{\phi(0,0)}(3) = H_1(3) = 4 \\ V(1) &=& H_{\phi(0,1)}(3) = H_\omega(3) = 6 \\ V(2) &=& H_{\phi(0,2)}(3) = H_{\omega^2}(3) = 24 \\ V(3) &=& H_{\phi(1,0)}(3) = H_{\epsilon_0}(3) = H_{\omega^{\omega^{\omega}}}(3) \\ V(4) &=& H_{\phi(1,1)}(3) = H_{\epsilon_1}(3) = H_{\omega^{\omega^{\epsilon_0+1}}}(3) = H_{\epsilon_0^{\omega}}(3) = H_{\epsilon_0^3}(3) = f_{\epsilon_0 3}(3)\\ V(5) &=& H_{\phi(1,2)}(3) = H_{\epsilon_2}(3) = f_{\epsilon_1 3}(3) \\ V(6) &=& H_{\phi(2,0)}(3) = H_{\zeta_0}(3) \approx f_{\zeta_0}(3) \\ V(7) &=& H_{\phi(2,1)}(3) = H_{\zeta_1}(3) \approx f_{\zeta_1}(3)\\ V(8) &=& H_{\phi(2,2)}(3) = H_{\zeta_2}(3) \approx f_{\zeta_2}(3)\\ V(9) &=& H_{\phi(1,0,0)}(3) = H_{\Gamma_0}(3) \approx f_{\Gamma_0}(3)\\ V(10) &=& H_{\phi(1,0,1)}(3) = H_{\Gamma_1}(3) \approx f_{\Gamma_1}(3)\\ V(27) &=& H_{\phi(1,0,0,0)}(3)\\ V(81) &=& H_{\phi(1,0,0,0,0)}(3)\\ \end{eqnarray*}
Interpolation between \(V(a) = H_{\alpha}(3)\) and \(V(a+h) = H_{\beta}(3)\) is
- When \(\beta = lim(\beta_i)\) and \(\alpha < \beta_1\), \(V(a+ih/3) = H_{\beta_i}(3)\) for \(i=1,2,3\).
- When \(\beta = lim(\beta_i)\) and \(\beta_1 \le \alpha < \beta_2\), \(V(a+(i-1)h/2) = H_{\beta_i}(3)\) for \(i=2,3\).
- When \(\beta = lim(\beta_i)\) and \(\beta_2 \le \alpha\), \(V(a+h) = H_{\beta_3}(3)\).
- When \(\beta\) is a successor, linear interpolation of \(V(a+nh) = V(a) + (n/h)[V(a+h)-V(a)]\)
For example, interpolation between \(V(5) = \epsilon_2\) and \(V(6) = \zeta_0 = lim(0, \epsilon_0, \epsilon_{\epsilon_0}, \epsilon_{\epsilon_{\epsilon_0}}, ...)\) is
\begin{eqnarray*} V(5.5) &=& H_{\epsilon_{\epsilon_0}}(3)\\ V(6) &=& H_{\epsilon_{\epsilon_{\epsilon_0}}}(3)\\ \end{eqnarray*}
and between these is
\begin{eqnarray*} V(5+4/6) &=& H_{\epsilon_{\epsilon_{\omega}}}(3)\\ V(5+5/6) &=& H_{\epsilon_{\epsilon_{\omega^{\omega}}}}(3)\\ V(6) &=& H_{\epsilon_{\epsilon_{\omega^{\omega^{\omega}}}}}(3)\\ \end{eqnarray*}
Between V(3) and V(4) is interpolated as
- \(V(3+1/3) = H_{\epsilon_0+1}(3) = H_{\epsilon_0}(4) = f_{\epsilon_0}(3)\)
- \(V(3+7/18) = H_{\epsilon_0 +\omega}(3) = H_{\epsilon_0 +3}(3) = f_{\epsilon_0}(5)\)
- \(V(3+8/18) = H_{\epsilon_0 +\omega^{\omega}}(3) \approx f_{\epsilon_0}(3↑↑3)\)
- \(V(3.5) = H_{\epsilon_0 2}(3) = H_{\epsilon_0 +\omega^{\omega^{\omega}}}(3) \approx f_{\epsilon_0}(A(1,0,0,0,3))\)
- \(V(3+2/3) = H_{\epsilon_0 \omega}(3) = f_{\epsilon_0 + 1}(3)\)
- \(V(3+5/6) = H_{\epsilon_0 ^2}(3)\)
BHO function[]
BHO function is defined with the Bachmann-Howard ordinal and FGH as follows, using fundamental sequence described in Ordinal collapsing function#Standard sequences for ordinal notations.
\[BHO(n) = f_{\psi(\varepsilon_{\Omega+1})}(n)\]
Therefore calculation is;
\begin{eqnarray*} BHO(0) &=& f_{\psi(\Omega)}(0) = f_{\psi(0)}(0) = f_{\omega}(0) = 0 \\ BHO(1) &=& f_{\psi(\Omega^\Omega)}(1) = f_{\psi(\Omega^{\psi(0)})}(1) = f_{\psi(\Omega^{\omega^{\omega}})}(1) \\ &=& f_{\psi(\Omega)}(1) = f_{\psi(\psi(0))}(1) = f_{\psi(1)}(1) = f_{\psi(0)^{\psi(0)}}(1) \\ &=& f_{1}(1) = 2 \\ BHO(2) &=& f_{\psi(\Omega^{\Omega^{\Omega}})}(2) = f_{\psi(\Omega^{\Omega^{\psi{(\Omega^{\psi(0)})}}})}(2) \\ &=& f_{\psi(\Omega^{\Omega^{\psi{(\Omega^{\omega^{\omega^{\omega}}})}}})}(2) \\ &=& f_{\psi(\Omega^{\Omega^{\psi{(\Omega^{\omega^{\omega+2}})}}})}(2) \\ &=& f_{\psi(\Omega^{\Omega^{\psi{(\Omega^{\omega^{\omega+1}\omega})}}})}(2) \\ &=& f_{\psi(\Omega^{\Omega^{\psi{(\Omega^{\omega^{\omega+1}2})}}})}(2) \\ &=& f_{\psi(\Omega^{\Omega^{\psi{(\Omega^{\omega^{\omega+1}}+{\omega^{\omega}}+\omega+2)}}})}(2) \\ &=& ... \end{eqnarray*}
Interpolation method is similar to V function. For example, as
\[BHO(2) = f_{\psi(\Omega^{\Omega^{\psi{(\Omega^{\psi(0)})}}})}(2)\]
\(BHO(1.5)\) is
\[BHO(1.5) = f_{\psi(\Omega^{\Omega^{\psi(0)}})}(2)\]
O function[]
O function is defined with Ψ₀(Ωω) and FGH as follows.
\[O(n) = f_{\vartheta(\Omega_\omega)}(n)\]
I am not sure about the canonical fundamental sequence up to this ordinal. Definition is complete when fundamental sequence is given.
OF function[]
OF function is defined with Ψ(ψᵢ(0)) and FGH, using fundamental sequence of \(\psi(0), \psi(\omega), \psi(\Omega_\omega), \psi(\Omega_{\Omega_\omega}), ... \).
\[OF(n) = f_{\psi(\psi_I(0))}(n)\]
L function[]
L function is defined with Ln (L2, L3, L4, ...) space of BEAF. It is linearly interpolated.
\[L(n) = \lbrace Ln,10\rbrace_{10,10}\]
D function[]
2 variable D function is defined with 1 variable D function of loader.c as follows.
\[D(m,n) = D^m(n)\]
It is linearly interpolated.
CKF function[]
CKF function is a subfunction for defining FC and RC functions. It returns ordinal.
\begin{eqnarray*} CKF(0) &=& 1 \\ CKF(1) &=& 2 \\ CKF(2) &=& 3 \\ CKF(3) &=& \omega \\ CKF(4) &=& \omega+1 \\ CKF(5) &=& \omega 2 \\ CKF(6) &=& \omega^2 \\ CKF(7) &=& \omega^\omega \\ CKF(8) &=& \omega^{\omega^\omega} \\ CKF(9) &=& \epsilon_0 = \phi(1,0) = \psi(0) \\ CKF(10) &=& \epsilon_1 = \phi(1,1) = \psi(1) \\ CKF(11) &=& \zeta_0 = \phi(2,0) = \psi(\Omega) \\ CKF(12) &=& \Gamma_0 = \phi(1,0,0) = \psi(\Omega^{\Omega}) = \vartheta(\Omega) \\ CKF(13) &=& \phi(1,0,0,0) = \psi(\Omega^{\Omega^2}) = \vartheta(\Omega^2) \\ CKF(14) &=& \psi(\Omega^{\Omega^\omega}) = \vartheta(\Omega^\omega) \\ CKF(15) &=& \psi(\Omega^{\Omega^\Omega}) = \vartheta(\Omega^\Omega) \\ CKF(16) &=& \psi(\epsilon_{\Omega+1}) = \vartheta(\varepsilon_{\Omega+1}) \\ CKF(17) &=& \psi_0(\Omega_{\omega}) \\ CKF(18) &=& \psi_0(\varepsilon_{\Omega_\omega + 1}) \\ CKF(19) &=& \psi(\psi_I(0)) \\ \end{eqnarray*}
For \(n \ge 20\), \[CKF(n) = \omega_{CKF(n-20)}^\text{CK}\]
FC function[]
FC function is defined with the previous CKF function and FGH as
\[FC(x) = f_{CKF(x)}(1000)\]
It is linearly interpolated.
In Church-Kleene ordinal and Kleene's O, a sytem called Kleene's \(\mathcal{O}\) is defined. It enumerates \(f_0, f_1, f_2, \ldots\) of all the partial recursive functions by ordering all the Turing machines lexicographically. Once \(\mathcal{O}\) is defined, it can be used as a fundamental sequence of \(\omega_1^\text{CK}\).
According to Admissible ordinal (accessed 7 July, 2014), by a theorem of Gerald Sacks, "the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles.[2] One sometimes writes \(\omega_\alpha^{\mathrm{CK}}\) for the \(\alpha\)-th ordinal which is either admissible or a limit of admissibles; an ordinal which is both is called recursively inaccessible.[3]" It is, however, still controvertial whether oracle Turing machines can reach \(\omega_2^{\mathrm{CK}}\). [4]
Based on the theorem that the countable admissible ordinals can be constructed with oracle Turing machines, fundamental sequence of \(f_{\omega_{\alpha+1}^{\mathrm{CK}}}\) is defined with \(\mathcal{O}_\alpha\) by ordering all the Turing machines which have \(f_{\omega_{\alpha}^{\mathrm{CK}}}(n)\) as oracle.
RC function[]
RC function is defined with CKF function and Rayo hierarchy of Fish number 7 as
\[RC(x) = R_{CKF(x)}(10^{10})\]
It is linearly interpolated.
Sources[]
- ↑ Blog post in Japanese Googology Wiki
- ↑ Friedman, Sy D. (1985), "Fine structure theory and its applications", Recursion theory (Ithaca, N.Y., 1982), Proc. Sympos. Pure Math. 42, Amer. Math. Soc., Providence, RI, pp. 259–269, doi:10.1090/pspum/042/791062, Mathematical Reviews 791062. See in particular p. 265.
- ↑ Friedman, Sy D. (2010), "Constructibility and class forcing", Handbook of set theory. Vols. 1, 2, 3, Springer, Dordrecht, pp. 557–604, doi:10.1007/978-1-4020-5764-9_9, Mathematical Reviews 2768687. See in particular p. 560.
- ↑ Forum:On oracles and admissibles