Wiki Googologie
Advertisement

La séquence Y est un système de séquences par différence introduit par le googologue japonais Yukito.[1] Elle se veut une extension du système de séquence hyper primitif, qui est également une extension du système de séquence primitif. Bien qu'elle n'ait pas été formalisée depuis un certain temps, Yukito a décidé[2] de fixer la définition comme étant celle donnée par un algorithme créé par un utilisateur japonais du Googology Wiki, Naruyoko.[3][4][5] L'expression (1,3) dans la séquence Y devrait correspondre à la limite du système de matrice de Bashicu 2.3, et son idée novatrice a donné une nouvelle direction à la googologie. On ne sait toujours pas si le système se termine ou non. De même, on ne sait toujours pas si la séquence Y est réellement plus forte que le système matriciel de Bashicu version 2.3 dans l'hypothèse de leur terminaison.

Explication

Une expression dans la séquence Y, que l'on appelle aussi séquence Y, est un tableau fini a satisfaisant l'une des trois conditions suivantes :

  1. a est la séquence vide ().
  2. a est une suite non vide de nombres positifs dont l'entrée la plus à gauche est 1.
  3. a est la séquence (1,ω).

Par exemple, (1), (1,2,1,2) et (1,3) sont des séquences Y, tandis que (0,1), (2) ou (1,ω+1) ne le sont pas.

Nous désignons par l'ensemble des séquences Y, et par l'ensemble des entiers positifs. Nous abrégeons une paire (a,n) d'une séquence Y a et d'un entier positif n par a[n]. La règle d'expansion est formalisée en une carte bien définie \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*} par Naruyoko.[4] Nous définissons une fonction partielle calculable \begin{eqnarray*} \textrm{Y} \colon \mathbb{Y} \times \mathbb{N}_{>0} & \to & \mathbb{N} \\ a[n] & \mapsto & \textrm{Y}a[n] \end{eqnarray*} de la manière récursive suivante :

  1. Si a = (), alors Ya[n] = n.
  2. Si a est une suite non vide d'entiers positifs dont l'entrée la plus à gauche est 1, alors Ya[n] = Y Expand(a[n]).
  3. Si a = (1,ω), alors Ya[n] = Y(1,n)[n].

Supposons que \((1,\omega)[n] \in \textrm{dom}(\textrm{Y})\) pour tout \(n \in \mathbb{N}_{>0}\). Soit f la fonction totale calculable \(n \mapsto \textrm{Y}(1,\omega)[n]\).

Yukito named f2000(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

Although Y sequence had not been formalised yet, 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 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.[6][7][8] 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 call 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. [9]

(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,...) up to the beginning of June 2020, but is currently intended to be expanded as (1,2,4,8,10,7,12,14,11,17,19,...) from the end of June 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,...) 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.[10] 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 September 1, 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.

Références

  1. The user page of Yukito in the Japanese Googology Wiki.
  2. Yukito's twitter post
  3. The user page of Naruyoko in Googology Wiki.
  4. 4,0 et 4,1 Naruyoko, YNySequence, GitHub page.
  5. Naruyoko, YNy_Sequenceの解説的な何か, Japanese Googology Wiki user blog.
  6. Hexirp, Y数列 Hexirp 版, Japanese Googology Wiki user blog post.
  7. p進大好きbot, New Difference Sequence System, Googology Wiki user blog post.
  8. Syst3ms, Bismuth : not Y sequence, but close, Googology Wiki user blog post.
  9. Naruyoko, whY mountain
  10. Hexirp, (2020-07-03) Y数列 Hexirp 版 2.1 の無限ループ, Japanese Googology Wiki user blog post.
Advertisement