![[PDF]](pdficon_large.png){kind=small}
Download "Googology in Japan - exploring large numbers" (in Japanese, PDF file)- Preview with Google Docs
- Citation: Fish (2013) "Googology in Japan - exploring large numbers" http://gyafun.jp/ln/en.html
- Jump to: Abstract | Contact | Keywords | Fish numbers | References
|
|
This Japanese book describes a decade of attempt to define large positive integers among Japanese googologists. It started in Japanese BBS at 2ch.net in 2002. The author of this book defined "Fish number", which is larger than Graham's number, and people on the Japanese BBS started to explore larger and larger numbers. At first very little mathematical knowledge was available among Japanese googologists, but as the discussion went on, they gradually learned higher mathematical concept of recursive functions such as Conway's chained array notation, ordinals, Hardy hierarchy, busy beaver function and so on. The large number page by Robert Munafo was very helpful in understanding the theory behind large numbers.
Some of the original numbers and functions developed by Japanese googologists and described in this book are as follows. Taro (2007) developed extentions of the famous Ackermann function. Taro's multivariable Ackermann function reached the growing level of F[ωω] with fast-growing hierarchy, corresponding to Bird's linear array notation. Yet it was defined with only 4 simple reccurence equations. Surprisingly enough with its simple definition, A(1,2,2) is larger than Graham's number and A(1,0,1,2) is larger than Conway's chained arrow notation with the length of Graham's number. A(1,0,2,1) is larger than the first version of Fish number, which beated Conway's chained array notation. Taro's nested array Ackermann function reached the level of F[ε0], corresponding to Bird's nested array notation. He also developed C0 function which has multivariable of ordinals. He believes that it reaches Ψ(Ωω). He speculated that by extending C0 function to nested array notation, it may reach Bachmann-Howard ordinal.
Fish, the author of this book, developed several versions of Fish numbers. With their complicated definitions using maps from functions to functions (functional), maps from "maps of functions to functions" to "maps of functions to functions", and so on, Fish number 3 (2003) reached the level of F[ωω+1 × 63], Fish number 5 (2003) reached the level of F[ε0], and Fish number 6 (2007) reached the level of F[φ2(0)], where φ is the Veblen function. Fish number 7 (2013) extended the definition of Rayo's function by introducing oracle formula in the micro-language of Rayo's definition to go beyond Rayo's number. He defined a hierarchy based on Rado's function, which is similar to fast-growing hierarchy but uncomputational. As the definitions of Fish numbers are available only in Japanese, the author translated them into English.
This free online book was written to introduce Japanese readers to the world of googology. The beta version of this book was published in 2007, and the first edition was published in 2013. In the first edition, development of googology during the recent years was mentioned based on the googology wiki. The author still does not catch up with the tremendous development of googology achived in these years, especially the notations and numbers developed by Chris Bird and Jonathan Bowers, and admire the efforts that the googologists have taken.
Definition and calculation of Fish numbers, written in this Japanese book, are shown briefly here. Fish number version N is denoted as FN and Fish function version N is denoted as FN(x).
Comparison among Fish numbers: F1 < F2 < F3 < F5 < F6 < F4 < F7
Googology wiki: Fish numbers
Fish number was first defined at 2ch.net on June 29, 2002. It was an attempt to make as large number as possible. All the knowledge that I had at that time was Ackermann function and Graham's numbers. Therefore, I tried to make a number that is much greater than Graham's number. I thought how I can generalize the process of making large numbers. I need to have large function, i.e., function that increases at very fast rate. OK, then how can I make larger functions? I thought S map, which maps a pair of "number and function" to a pair of "number and function", to produce larger numbers and functions at the same time, and increase the S map itself. To increase S map, I thought higher concept of SS map. So here is the definition. Later as I made larger Fish numbers I put version numbers to distinguish them.
(1) Define "S map", a map from "a pair of number and function" to "a pair of number and function", as follows.
S:[m,f(x)]→[g(m),g(x)]
Here, g(x) is given as follows.
(2) Define "SS map", a map from "a set of number, function and S map" to "a set of number, function and S map" as follows.
SS:[m,f(x),S]→[n,g(x),S2]
Here, S2, n, and g(x) are given as follows.
(3) Apply SS map 63 times to [3,x+1,S] and we get Fish number F1 and Fish function F1(x).
At first, I calculated Fish numbers as follows.
After applying S map for the first time, B(m,n) matchs Ackermann function, and therefore
S:[3,x+1]→[A(3,3),A(x,x)]
As A(3, 3) = 61, it is not so large yet.
The second Ｓ map is calculated as follows.
And therefore
As it recurses Ackermann function, B(1,x) grows very rapidly. g(2)=B(1,B(1,61)) recurses it for B(1,61) times, and it sure exceeds Graham's number which only recurses 64 times. As the S map grows number and function rapidly, and the SS map grows number, function, and S map rapidly at the same time, after 63 times of SS conversion unimaginably large number will be obtained.
This amazed many people on 2ch.net, and they started to calculate Fish numbers. We learned about Conway's chained arrow notation, and Chris Bird's rotating arrow notation (which is now obsolete). We were trying to compare these functions and numbers. It soon turned out that F1 is stronger than Conway's chained arrow notation, because applying the initial S map corresponds to adding one to the length of chained arrow. As SS map applies so many times of S map that was produced by this operation, it actually beats chained arrow.
Ackermann function counts up primitive recursion and it is double recursion. Chained arrow does not count up double recursion but it repeats primitive recursion to double recursion, and therefore chained arrow is double recursion. F1 counts up (diagonizes) the double recursion of chained arrow and therefore F1 is triple recursion.
Ruby program for calculating F1 by @aycabt
In 2007, Taro invented multivariable Ackermann function, which made the analysis much easier. Actually, when we denote Si(x) as a function obtained by applying S map i times to [3,x+1], S map can be written as
This is completely same as Taro's 3 variable Ackerman function. F1 can be compared with 4 variable Ackermann function as follows.
A(1,0,1,1) = A(2,3,3) is double recursion, because it repeats double recursion 2 times. A(1,0,1,2) is triple recursion, because it repeats double recursion for times obtained with double recursion. It is similar to Moser number, which repeats primitive recursion so many times (mega times) that was produced by primitive recursion and understood as double recursion.
A(1,0,1,n+1) corresponds to A(1,0,1,n) times of the initial S map, and it is similar to SS map, where numbers of the repetition of the S map is given by the produced large number. Actually, it is larger than that, because SS map uses f(x) instead of x, and S map itself grows up. However, it is trivial because the growth rate of f(x) (primitive recursion) is negligible compared to the main double recursion system, and the growth rate of S map is also just primitive recursion level. The first time of SS map corresponds to 4 times of S map, which is larger than A(1,0,1,1) = A(2,3,3) corresponding to 2 times of S map. Second SS map is larger than A(1,0,1,2). F1 repeats SS map 63 times and therefore it is larger than A(1,0,1,63). Now we keep on calculating.
A(1,0,2,1) corresponds to repeating SS map A(2,3,3) times. This is by far larger than F1. A(1,1,1,1) is even larger. We need SSS…SSS map with A(2,3,3) numbers of S denoted. We can summarize the evaluation as A(1,0,1,63) < F1 < A(1,0,2,1) < A(1,1,1,1). Please note that this evaluation was made possible years after F1 was invented, and we were not sure how to evaluate F1 in the year 2002.
By the way, why do I use 3 and 63 in the definitions of Fish numbers? At first I understood Graham's number as starting from 3 and repeats 63 times, while actually it is repetition of 64. I just imitated Graham's number.
Jump to: Page top | Abstract | Keywords | Fish numbers | References
Fish number version 2 was defined at 2ch.net on October 1, 2002. At this time, main interest on 2ch.net was comparison of Fish number to Bird's number; not the current one, but obsolete one with revolving array notation. By analysing Bird's revolving arrow notation, I realized that the revolving the arrow by Bird's definition diagonizes the double recursion of extending the length of chained arrow, while SS map in F1 repeats S map many times, but does not diagonize the operation of S map. Therefore, functions produced with SS map of F1 is double recursion, weaker than Bird's revolving arrow. In order to diagonize the S map in SS map, I changed the definition of SS map and defined F2 as follows.
Definition of F2 is similar to that of F1, except that of SS map SS:[m,f(x),S]→[n,g(x),S2], which is defined as follows.
Apply SS map 63 times to [3,x+1,S] and we get Fish number F2 and Fish function F2(x).
Definition of F2 is only adding one line, S2x:[m,f(x)]→[q(x),g(x)] . In this equation, SS map counts the operation of S map by using the variable x, variable of the function f. Therefore, the function produced by SS map is triple recursion, while function produced by the SS map in F1 is a very large double recursion.
As shown in the next version, F3, S map in F2 corresponds to s(2) in F3, and SS map in F2 corresponds to s(3) in F3. Applying s(3) 63 times corresponds to A(63, 0, 0, x), and as A(1,0,0,0,63) = A(63,0,0,63), it can be evaluated as follows.
Jump to: Page top | Abstract | Keywords | Fish numbers | References
Fish number version 3 was first defined on October 29, 2002. After that, definition was modified in the beta version of this book, on September 24, 2007. I only describe the modified version of the definition here.
(1) Define s(n) map (n > 0) from function f(x) to function g(x) as follows.
(2) Define ss(n) map (n > 0) from function f(x) to function g(x) as follows.
(3) F3(x):=ss(2)63f; f(x)=x+1
(4) F3: = F363(3)
Definition of F3 function was extended to 3 variable s function, where s(1, 1, n) = s(n), s(1, 2, n) = ss(n), in this book in 2007 as follows.Now definition has changed much from F1 and F2, but basically it is the extention of F2. At first I just tried to make as complicated definition as possible, because I believed that will produce much larger number, but I realized that simplification is also important. Just define what makes the function (and number) grows faster, and eliminate unnecessary complexity. From this point of view, I simplified as follows.
Starting from f(x)=x+1, s(n) can be compared with Taro's multivariable Ackermann function as follows.
[s(1)a1][s(2)a2]...[s(n)an]f(x) = A(an,...a2,a1,x)
Therefore, s(1) is primitive recursion, s(2) is double recursion, s(3) is triple recursion, and s(n) is n-times recursion. ss(1) counts the repetition of recursion of s(n), and thus for f(x) = x+1
As multivariable Ackermann function can not evaluate the function any more, we introduce the concept of FGH (fast-growing hierarchy) to evaluate the function.
When f(x) = x+1, F3 can be evaluated with FGH as follows.
Extended definition of 3 variable s function can be calculated as follows.
Jump to: Page top | Abstract | Keywords | Fish numbers | References
Fish number version 4 was defined in October 31, 2002. It uses the concept of oracle machine. Of course it is larger than any number defined by computational function, but it did not attract people at 2ch.net. People said it is meaningless because it is uncomputational. I said, well, Graham's number is uncomputational in reality. As we are going beyond the actual limit of computationality, I don't care about computationality. I just want a large number. Anyway the discussion at 2ch.net kept on computational numbers, and F5 and F6 will be computaional numbers again. Therefore, F4 is larger than F5 and F6.
(1) Define s'(1) map from function f to function g as follows.
Function g is a busy beaver function with an oracle machine having an oracle which calculates function f. That is, with Turing machine + function f, the maximum possible numbers of 1 that can be set with n-state machine is g(n).
(2) sʹ(n)(n > 1) and ssʹ(n)(n > 0) are defined with the same definition as F3.
(3) F4(x): = ssʹ(2)63f; f(x) = x + 1
(4) F4: = F463(3)
Please note that F4 is not a function that was recursively defined from busy beaver function. By applying s'(1) to the initial function f(x)=x+1, it is an ordinal Turing machine itself and the obtained function s'(1)f(x) is a busy beaver function in its original definition. By applying s'(1) to this, it will become a busy beaver function that is produced from 'the oracle machine with busy beaver function', which can compute any function recursively defined from the original busy beaver function. F4 will repeat such process for many many times.
Taro (2007) defined busy beaver hierarchy, similar to Hardy hierarchy, as follows.
As F3(n) ≈ F[ωω + 1×63](n), F4(n) ≈ B[ωω + 1×63](n).
Jump to: Page top | Abstract | Keywords | Fish numbers | References
The idea of Fish number version 5 was described in March 26, 2003, and l.b. described it in clear form in March 27. Up to F3, we made large functions by using map from functions to functions. The idea was how we can define a map that diagonizes the mapping itself. SS map in F1 just repeated S map many times, and did not diagonize the S map. By discussion with l.b., F5 was defined as follows.
(1) Define Mn set (n = 0, 1, 2, . . . ) as follows.
(2) Mn conversion m(n) (n≥1) is defined as follows.
For fn ∈ M(n), m(n+1)(fn) = gn is defined as follows.
For fn−1 ∈ M(n−1), gn(fn−1) = gn−1 is defined as follows.
For fn−2 ∈ M(n−2), gn−1(fn−2) = gn−2 is defined as follows
……
For f0 ∈ M(0), g1(f0) = g0 is defined as follows.
g0=(. . ((fnf0fn − 1)fn − 2). . . f1)f0
Therefore
- m(1)(f0) = f0f0
- (m(2)f1)f0 = (f1f0)(f0)
- (..((m(n+1)fn)fn-1)...f1)f0 := (..(fnf0fn-1)...f1)f0
(3) F5(x) := ((..((m(x)m(x-1))m(x-2))...m(2))m(1))(x)
(4) F5 := F563(3)
Next we compare with fast-growing hierarchy. We write m(2) = F[ + 1] meaning that when f(x) ≈ F[α](x), m(2)f(x)≈F[α + 1](x).
Similar calculation will lead us to
It was confirmed that calculation of F5 is similar to hydra battle by Kirby and Paris.
Jump to: Page top | Abstract | Keywords | Fish numbers | References
Fish number version 6 was defined in the beta version of this book in October 27, 2007.
(1) Define map M[m, n](m = 0, 1, . . . ; n = 1, 2, . . . ) as follows.
M[0, 1] = function from natural number to natural number
M[m + 1, 1] = set where each element is a set of element with one element each from M(m,n) (n=1,2,...)
Element of M[m, 1] works as a similar function as M[0, 1], which is an element of element of ... element of the element.
M[m, n + 1] = Set of maps from M[m, n] to M[m, n] (n=1,2,...)
(2) Define m(m,n), element of M[m, n], as follows. Here, ai, bi and fi are elements of m(m,i), and strict definition is same as F5.
(3) F6(x) := m(x,2)m(x,1)(x)
(4) F6 := F663(3)
When m(1,2) m(1,1) = [a1,a2,a3,…], as a1(x) = mx mx-1...m1 (x), we can get following relationship as we calculated in F5
As a2 f1(x) = my my-1 …m2 f1(x) (y=max(x,2)),
As a3 f2 f1(x) = my my-1...m3 f2 f1(x) (y=max(x,3)), for f2 = F[+a],
Therefore, a3 is a conversion from F[+a] to F[+a×ε0].
As a4 f3 f2 f1(x) = my my-1...m4 f3 f2 f1(x) (y=max(x,4)), for f2 = F[+a] and f3=F[+a]→ F[+ ab],
By writing m(1,2)3 m(1,1) = [b1,b2,b3,…], bi is same as ai = ε1 instead of ai = ε0 in the above equations. Therefore,
Calculation will go like
Defiition and calculation of m(x,x)m(x,x-1)…m(x,1)(x) might lead us to F[φω(0)], but that would not be appealing unless we reach to the point of F[Γ0]. That is why I defined F6 like this. The road to F[Γ0] with this approach seems to me very far indeed.
Jump to: Page top | Abstract | Keywords | Fish numbers | References
Fish number version 7 was defined in this book in October 19, 2013. It was inspired by Rayo's number. In October, 2013, I realized recent development of googology at googology wiki website. I found that the largest number at the googology wiki is the Rayo's number, and thought how I can go beyond Rayo's number. I needed to use the definition of Rayo's number to exceed it.
Rayo's number is "the smallest positive integer bigger than any finite positive integer named by an expression in the language of first order set theory with a googol symbols or less." It is defined with micro-language using first-order set theory, and diagonizes over the micro-language. According to the description of googology wiki, it is much stronger than the busy beaver function, because the Turing machine is basically first-order arithmetic, where second-order arithmetic is stronger than the first-order arithmetic and the first-order set theory is stronger than both. Therefore, oracle Turing machine or any order-n Turning machine cannot compute the Rayo's number.
In Fish number 4, oracle Turing machine was implemented in the definition to make a large uncomputable number. However, this approach does not exceed the Rayo's number. Only way to exceed the Rayo's number seems to be implementing oracle in the Rayo's micro-language itself. The micro-language has 5 formulas
(1) Functional RR from function f to function g, RR(f)=g, is defined as follows.
By adding an oracle formula of function f, "f(a)=b", meaning that the ath and bth members of the sequence satisfy the relation f(a)=b, to the definition of micro-language in the Rayo's function, we have stronger micro-language than the Rayo's original micro-language. Function g is Rayo's function of this stronger micro-language.
(2) Rayo hierarchy to ordinal α is defined as follows. See also busy beaver hierarchy in Fish number 4.
(3) Change the definition of m(0,2) in Fish number version 6 to m(0,2)=RR, and we get F7(x) = R[φ2(0)].
(4) F7 := F763(10100)
Calculation is completely impossible. We can only evaluate the magnitude of F7 with Rayo hierarchy. Up to F6, 3 was used for a starting number, but as 3 letters micro-language is very poor, F7 starts from googol, which is used in Rayo's number.
To my blog post introducing Fish numbers, people commented that FOST (micro-language of Rayo) can write Rayo function, and therefore implementing Rayo function in FOST is not very strong. However, this is not correct, as shown in the following proof.
Proof that there is no way to write Rayo function in compact form inside FOST
Suppose that you can write Rayo function in FOST. Then you can write Rayo(Rayo(i)) in FOST in compact form with a little more characters than i (if it requires billion characters, that is not so much). Now take j as a sufficiently large number which can describe Rayo(Rayo(i)), but not larger than Rayo(i); i < j < Rayo(i). That is, FOST with j characters can write Rayo(Rayo(i)).
Then, by definition of Rayo function, as FOST with j character can describe Rayo(Rayo(i)), Rayo(j) > Rayo(Rayo(i)). As Rayo function is increasing function, Rayo(j) > Rayo(Rayo(i)) means j > Rayo(i).
This is contradiction, because we assumed that j < Rayo(i).
Q.E.D.
As this proof shows, in order to write Rayo(Rayo(i)), we will need to have Rayo(i) characters of FOST. This is not at all compact expression. Therefore, no compact expression to write Rayo function exists.
By reading this proof, you may feel that Rayo function itself has contradiction in itself and it is ill-defined. But it is not true, either. If you give contradictory expression of FOST, it is excluded from a valid expression to name a specified number. Rayo defined Rayo number so that any contradiction can be excluded. If you make a statement of FOST that makes Rayo(i) < j < Rayo(i), this is a contradiction and it will be excluded. Therefore, don't worry. Rayo's number is well-defined.
By implementing Rayo function as oracle f, you can write Rayo(Rayo(i)) simply by f(f(i)) (formal expression is a little more complex). j < Rayo(i) and Rayo(Rayo(i)) < Rayo'(j) are not contradiction, because Rayo and Rayo' are different functions. In order to implement Rayo2, you will need to define different FOST from the original FOST. This is the reason why we need to have oracle formula to implement Rayo function itself. You can write Rayo2(i), Rayon, or any recursive function of Rayo(i) with OFOST (oracle-implemented FOST). Therefore, Rayo function with OFOST is much stronger than Rayo function with FOST. This is just a beginning and R[2] level. F7 is in the level of R[φ2(0)], and therefore much stronger than Rayo function.
Jump to: Page top | Abstract | Keywords | Fish numbers | References
List of websites cited in this book