Y sequence

Y sequence is a difference sequence system introduced by a Japanese googologist Yukito.The user page of Yukito in the Japanese Googology Wiki.Yukito, Y数列, Google Document. It is intended to be an extension of hyper primitive sequence system, which is a also an extension of primitive sequence system. Although it had not been formalised for a while, Yukito decidedYukito's twitter post to fix the definition as the one given by an algorithm created by a Japanese Googology Wiki user Naruyoko.The user page of Naruyoko in Googology Wiki.Naruyoko, YNySequence, GitHub page.Naruyoko, YNy_Sequenceの解説的な何か, Japanese Googology Wiki user blog. The expression \((1,3)\) in Y sequence is expected to correspond to the limit of Bashicu matrix system version 2.3, and its novel idea has given a new direction in googology. It is still unknown whether the system is terminating or not. Also, it is still unknown whether Y sequence is actually stronger than Bashicu matrix system version 2.3 under the assumption of their terminations.
== Explanation ==
An expression in Y sequence, which is also called a Y sequence, is a finite array \(a\) satisfying one of the following three conditions:
# \(a\) is the empty sequence \(()\).
# \(a\) is a non-empty sequence of positive numbers whose leftmost entry is \(1\).
# \(a\) is the sequence \((1,\omega)\).
For example, \((1)\), \((1,2,1,2)\), and \((1,3)\) are Y sequences, while \((0,1)\), \((2)\), or \((1,\omega+1)\) are not Y sequences.
We denote by \(\mathbb{Y}\) the set of Y sequences, and by \(\mathbb{N}_{>0}\) the set of positive integers. We abbrevaiate a pair \((a,n)\) of a Y sequence \(a\) and a positive integer \(n\) to \(a[n]\). The expansion rule is formalised into a well-defined map
\begin{eqnarray*}
\textrm{Expand} \colon \mathbb{Y} \times \mathbb{N}_{>0} & \to & \mathbb{Y} \times \mathbb{N}_{>0} \\
a[n] & \mapsto & \textrm{Expand}(a[n])
\end{eqnarray*}
by Naruyoko. We define a partial computable function
\begin{eqnarray*}
\textrm{Y} \colon \mathbb{Y} \times \mathbb{N}_{>0} & \to & \mathbb{N} \\
a[n] & \mapsto & \textrm{Y}a[n]
\end{eqnarray*}
in the following recursive way:
# If \(a = ()\), then \(\textrm{Y}a[n] = n\).
# If \(a\) is a non-empty sequence of positive integers whose leftmost entry is \(1\), then \(\textrm{Y}a[n] = \textrm{Y} \textrm{Expand}(a[n])\).
# If \(a = (1,\omega)\), then \(\textrm{Y}a[n] = \textrm{Y}(1,n)[n]\).
Assume \((1,\omega)[n] \in \textrm{dom}(\textrm{Y})\) for any \(n \in \mathbb{N}_{>0}\). Let \(f\) denote the total computable function \(n \mapsto \textrm{Y}(1,\omega)[n]\).
Yukito named \(f^{2000}(1)\) Y sequence number. Since \((1,3)\) is expected to correspond to the limit of Bashicu matrix system version 2.3, Y sequence number is expected to be significantly greater than Bashicu matrix number with respect to the version. We note that the well-definedness of Bashicu matrix number and Y sequence number is unknown, and the statement does not make sense if either one of them is ill-defined. Also, the expectation has not been justified by a proof even under the assumption of their terminations, and hence is an open problem.
== Expansion ==
Before Y sequence was formalised, Yukito has explained expansions for several examples. Here is a list of known expansions of Y sequences originally given by Yukito.
Y sequence \(a\)	expansion \(\textrm{Expand}(a,-)\)
\((1)\) 	\(()\)
\((1,1)\) 	\((1)\)
\((1,1,1)\) 	\((1,1)\)
\((1,1,1,1)\) 	\((1,1,1)\)
\((1,2)\) 	\((1,1,1,1,\ldots)\)
\((1,2,1)\) 	\((1,2)\)
\((1,2,2)\) 	\((1,2,1,2,1,2,1,2,\ldots)\)
\((1,2,2,2)\) 	\((1,2,2,1,2,2,1,2,2,1,2,2,\ldots)\)
\((1,2,3)\) 	\((1,2,2,2,2,\ldots)\)
\((1,2,3,3)\) 	\((1,2,3,2,3,2,3,2,3,\ldots)\)
\((1,2,4)\) 	\((1,2,3,4,5,\ldots)\)
\((1,2,4,1)\) 	\((1,2,4)\)
\((1,2,4,2)\) 	\((1,2,4,1,2,4,1,2,4,1,2,4,\ldots)\)
\((1,2,4,3)\) 	\((1,2,4,2,4,2,4,2,4,\ldots)\)
\((1,2,4,4)\) 	\((1,2,4,3,5,4,6,5,7,\ldots)\)
\((1,2,4,5)\) 	\((1,2,4,4,4,4,\ldots)\)
\((1,2,4,6)\) 	\((1,2,4,5,7,8,10,11,13,\ldots)\)
\((1,2,4,7)\) 	\((1,2,4,6,8,10,\ldots)\)
\((1,2,4,8)\) 	\((1,2,4,7,11,16,\ldots)\)
\((1,3)\) 	\((1,2,4,8,\ldots)\)
\((1,3,1)\) 	\((1,3)\)
\((1,3,2)\) 	\((1,3,1,3,1,3,1,3,\ldots)\)
\((1,3,3)\) 	\((1,3,2,5,4,9,8,17,\ldots)\)
\((1,3,4)\) 	\((1,3,3,3,3,\ldots)\)
\((1,3,5)\) 	\((1,3,4,7,11,18,29,47,\ldots)\)
\((1,3,6)\) 	\((1,3,5,7,9,\ldots)\)
\((1,3,7)\) 	\((1,3,6,12,24,48,96,192,\ldots)\)
\((1,3,8)\) 	\((1,3,7,15,31,\ldots)\)
\((1,3,9)\) 	\((1,3,8,20,48,\ldots)\)
\((1,4)\) 	\((1,3,9,27,\ldots)\)
\((1,5)\) 	\((1,4,16,64,\ldots)\)
\((1,6)\) 	\((1,5,25,125,\ldots)\)
\((1,7)\) 	\((1,6,36,216,\ldots)\)
Needless to say, the table does not unqiuely characterise the expansion rule. Indeed, Yukito officially kept the expansions of several Y sequences to be undecided. After a while, Yukito decided to use Naruyoko's algorithm to fix the expansion rule.
== Alternative Formalisations ==
Through the original examples of expansions, several googologists tried to find a formal rule (partially or essentially) consistent with them.Hexirp, Y数列 Hexirp 版, Japanese Googology Wiki user blog post.p進大好きbot, New Difference Sequence System, Googology Wiki user blog post.Syst3ms, Bismuth : not Y sequence, but close, Googology Wiki user blog post. The formalisations by others were not regarded as an official defintion of Y sequence, and should be distinguished from the original Y sequence. Sometimes several googologists introduce their formalisation as "the definition of Y sequence" or something like that, it does not mean that they are allowed to express so by Yukito or even that those are compatible with the original explanation by Yukito.
Yukito stated that Y sequence is the name only for the difference sequence system which he himself will complete, and he did not want others to name their own difference sequence systems Y sequence version 1.1 or something like that. Therefore others tend to call their own difference sequence systems distinct names unless they directly ask Yukito permissions.
== Mt. Fuji Notation ==
Yukito often use mountain-like notation with the lines as \(\land\) which shows the connections of the differential operations with lines to represent a Y sequence. He called it "Mt. Fuji". Each \(\land\) is called "a mountain". Naruyoko made a web site to draw this Mt. Fuji notations which correspond to the Y sequence input. Naruyoko, whY mountain
== (1,2,4,8,10,8) Problem ==
There were several candidates of the expansion of \((1,2,4,8,10,8)\) in the original and alternative formulations of Y-sequence. The expression \((1,2,4,8,10,8)\) was originally intended to be expanded as \((1,2,4,8,10,7,12,15,11,17,21,\ldots)\) up to the beginning of 06/2020, but is currently intended to be expanded as \((1,2,4,8,10,7,12,14,11,17,19,\ldots)\) from the end of 06/2020.
At the beginning of 07/2020, Googology Wiki user Ecl1psed276 stated that Ecl1psed276's alternative formulation and many other alternative formulations in which \((1,2,4,8,10,8)\) is expanded as \((1,2,4,8,10,7,12,15,11,17,21,\ldots)\) have an infinite loop at \((1,2,4,8,10,8)\), and actually Japanese Googology Wiki user Hexirp confirmed that one of Hexirp's alternative formulations has the same infinite loop.Hexirp, (2020-07-03) Y数列 Hexirp 版 2.1 の無限ループ, Japanese Googology Wiki user blog post. Therefore if Yukito had not changed the original intension, then Y-sequence would be non-terminating. Of course, this observation does not have significant meanings, because Yukito had not defined Y-sequence at the day. Indeed, Yukito clarified later that the infinite loop did not occur even in the previous version.
Yukito stated that \((1,3)\) in Y sequence corresponded to the limit of Bashicu matrix system version 2.3 before he changed the expansion of \((1,2,4,8,10,8)\), but the statement seems to be based on the wrong belief that the expansion of Y sequences below \((1,3)\) with respect to the previous version precisely corresponded to that of Bashicu matrix system version 2.3. Therefore the statement that \((1,3)\) in Y sequence with respect to the previous version corresponded to the limit of Bashicu matrix system version 2.3 might not be correct even if it had been formalised.
On the other hand, Eclpsed176 stated on 14/09/2019 that his unformalised notation DMBS reached the limit of Trio sequence system with respect to Bashicu matrix system version 2.3 and the limit of DBMS at the day corresponds to the limit of Y sequence in the previous version, and hence essentially stated that Y sequence in the previous version at least reached the limit of Trio sequence system. Of course, these analyses did not make sense because none of them other than Bashicu matrix system version 2.3 had been formalised.
Y sequences below \((1,3)\) with respect to the current version is also expected to directly correspond to Bashicu matrix system version 2.3 through the comparison of expansions of finitely many examples, but the situation was the same as the previous version until 01/09/2020. In other words, if there would be another example of a Y sequence whose expansion with respect to the current version was not compatible with that of Bashicu matrix system version 2.3, then the expectation that \((1,3)\) in Y sequence with respect to the current version corresponds to the limit of Bashicu matrix system version 2.3 might be declined.
At last, Yukito has fixed the definition by using Naruyoko's algorithm, and hence the (1,2,4,8,10,8) Problem has been solved. The remaining unsolved problem is the termination of Y sequence and the comparison to Bashicu matrix system.
== As a Notation of ordinals ==
Although Y sequence is not an ordinal notation system, it is strongly believed that it can "express" ordinals in the way explained in the article of fundamental sequences. Following that Bashicu coined ordinals corresponding to Bashicu matrices, Yukito coined the ordinal corresponding to \((1,\omega)\) in Y sequence as Y Sequence Ordinal or Small Y Sequence Ordinal (SYO). As \((1,3)\) in Y sequence is expected to correspond to the limit of Bashicu matrix system version 2.3, Y sequence Ordinal is expected to be larger than the omega back gear ordinal, which corresponds to \((0,0,0)(1,1,1)(2,2,2)\) in Bashicu matrix system version 2.3, under the assumption of the well-definedness of those ordinals.
== References ==
== See also ==
* Introduction to Y sequence
* YY sequence
* ω-Y sequence
ja:Y数列
fr:Séquence Y
Category:Numbers
Category:Functions
Category:Eponymous numbers
Category:Googology in Asia
Category:Difference sequence system
Category:Eponymous functions
Category:Higher computable level
Category:Unsolved problems
Category:Sequences