Fish number 4

View full site to see MathJax equation

Fish number 4 (F₄) is a number defined by Japanese googologist Fish in 2002.^[1] It is the smallest of the Fish numbers that is defined using an uncomputable function.

s'(1) map is a function which maps functions to functions, as follows.

Function \(s'(1)f\) is a busy beaver function for an oracle machine having an oracle which calculates function \(f\). That is, the maximum possible numbers of ones that can be written with an n-state, two-color oracle Turing machine is \(s'(1)f(n)\).

By comparing with the order-n busy beaver function \(\Sigma_n(x)\), let \(f\) be a computable function. Then it's easy to see that (exponents mean iteration of the map here):

\begin{eqnarray*} s'(1)f & = & \Sigma_1(x)\\ s'(1)^2f & = & \Sigma_2(x)\\ s'(1)^3f & = & \Sigma_3(x)\\ s'(1)^nf & = & \Sigma_n(x)\\ s'(1)^xf & = & \Sigma_x(x) & = & \Sigma_{\omega}(x)\end{eqnarray*}

For \(n>1\), \(s'(n)\) map is defined similar to the s(n) map,

\begin{eqnarray*} s'(n)f & = & s'(n-1)^{x}f(x) (\text{for } n>1) \\ \end{eqnarray*}

Its analysis is exactly the same except for ordinals being indices of oracle and not of FGH:

\begin{eqnarray*} s'(2)f & = & s'(1)^xf(x) & = & \Sigma_{\omega}(x) \\ s'(1)s'(2)f & = & \Sigma_{\omega+1}(x) \\ s'(2)^2f & = & \Sigma_{\omega \times 2}(x) \\ s'(3)f & = & \Sigma_{\omega^2}(x) \\ s'(4)f & = & \Sigma_{\omega^3}(x) \\ s'(n)f & = & \Sigma_{\omega^{n-1}}(x) \\ s'(x)f & = & \Sigma'_{\omega^\omega}(x) \end{eqnarray*}

where \(\Sigma'_\alpha(x)\) is oracle busy beaver function, where Wainer hierarchy is used with a single modification: \(\omega^\omega [n] = \omega^{n-1}\).

After this, the definition is similar to Fish number 3;

\begin{eqnarray*} ssʹ(1)f & = & sʹ(x)f(x) \\ ssʹ(n)f & = & [ssʹ(n − 1)^{x}]f(x) (\text{for } n>1) \\ F_4(x) & = & ssʹ(2)^{63}f; f(x) = x + 1 \\ F_4 & = & F_4^{63}(3) & = & \Sigma'^{63}_{\omega^{\omega+1}63}(3) \end{eqnarray*}

Sources[]

↑ Fish, Googology in Japan - exploring large numbers (2013)

See also[]

Googology in Japan

Original numbers, functions, notations, and notions

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

Methodology

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

Implementation of existing works into programs

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

Proofs, translation maps for analysis schema, and other mathematical contributions

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

Entertainments

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