N primitive (N原始 in Japanese, N PRIMITIV in German) is the generic name of difference sequence systems created by the Googology Wiki user Nayuta Ito. They are intended to surpass Bashicu matrix system version 2.3 with respect to koteitan's classification[1] and admit simple isomorphisms between the set of standard expressions below \((0,1,3)\) and the set of standard Bashicu matrices whose restriction to the subset of standard expressions below \((0,1,2,4)\) is the identity map onto the subset of standard primitive sequences.
Y sequence, Y function, S-σ, and SSAN are computable systems which arose in the same period as N primitive and are also expected to go beyond Bashicu matrix system, N primitive is the first example among them which has been formalised. (But it has not been verified yet under ZFC set theory that one version of N primitive terminates and actually goes beyond Bashicu matrix system.)
All functions defined by N primitive are intended to be computable and hence weaker than the busy beaver function.
Terminology[]
N primitive is named after the creator Nayuta Ito, and the primitive sequence system. Although the behaviour of N primitive below \((0,1,2,4)\) is consistent due to the restriction on the relation to the primitive sequence system, the behaviour above \((0,1,2,4)\) varies depending on the version.
Version Name[]
There are several versions of N primitive. Here is a name table of N primitive versions.[2]
| Casual Name | Another Casual Name | Official Name | Comment |
|---|---|---|---|
| N1.0 | |||
| N1.1 | DAS1.1 | Am schnellsteren | A variant of N1.0 |
| N1.1½ | DAS1.1½ | Am schnellsterhalben | A variant of N1.1 |
| N1.1.π | Am schnellsteren | A Python-version of N1.1 | |
| N1.2½ | DAS1.2½ | Am schnellstererhalben | A variant of N1.1½ |
| N1.3½ | A variant of N1.2½ | ||
| N2.0 | A variant of N1.0 | ||
| N2.1 | A variant of N1.1 | ||
| N3.0 | DAS3.0 | Am schnellstestesten | A variant of N2.1 |
| N4.0 | A variant of N3.0 | ||
| Nω.0甲 | A variant of N3.0 | ||
| Nω.0乙 | A variant of N3.0 | ||
| Nω.1甲 | A variant of Nω.0乙 | ||
| Nω.1乙 | A variant of Nω.0乙 | ||
| NΩ.0 | A cousin of Yn sequences |
Dead N primitive[]
A version of N primitive is said to be dead if it does not work as intended, to be alive if it is not known to be dead, and to be canceled if it is planned to be created but has not been born due to some troubles. For example, N1.1 is supposed to be dead because it does not seem to admit a simple isomorphism between the set of standard expressions below \((0,1,3)\) and the set of standard Bashicu matrices. It does not mean that N1.1 is actually weaker than Bashicu matrix system version 2.3 or admits an infinite loop. Here is a table of the status of versions of N primitive.
| Version Name | Status |
|---|---|
| N1.0 | dead |
| N1.1 | dead |
| N1.1½ | dead |
| N1.1.π | dead |
| N1.2½ | dead |
| N1.3½ | alive |
| N2.0 | dead |
| N2.1 | dead |
| N3.0 | dead |
| N4.0 | dead |
| Nω.0甲 | dead |
| Nω.0乙 | dead |
| Nω.1甲 | dead |
| Nω.1乙 | dead |
| NΩ.0 | canceled |
"Currently, 13½ N primitives were born, 26 of which are dead, and only 1 is alive. Besides, an N primitive was sunnied-side-up when it was still in an egg, but it is not counted because it has never been born at the first place. －Nayuta Ito"
Japanese Letters[]
The original Japanese name "N原始" of N primitive is pronounced as "enu gen ʃi". Needless to say, the "原始" in "N原始" is named after the original Japanese name "原始数列" of primitive sequence system.
The letter "甲" (resp. "乙") means "first" (resp. "second"), and is pronounced as "kou/kɔ́r/kɔː" (resp. "ɔts"). Therefore Nω.0甲 (resp. Nω.0乙) roughly means "the first Nω.0" (resp. "the second Nω.0").
Definition[]
The original definitions of N1.1, N1.1½, N1.2½, and N3.0 are open,[3] and the original source code of N1.1.π is also open.[4] Here, we explain the definition of N1.1, which is the easiest to understand among them.
Convention[]
We denote by \(\textrm{FinSeq}\) the set of finite sequences of natural numbers. Let \(a \in \textrm{FinSeq}\). We denote by \(\textrm{Lng}(a) \in \mathbb{N}\) the length of \(a\). For an \(i \in \mathbb{N}\) smaller than \(\textrm{Lng}(a)\), we denote by \(a_i \in \mathbb{N}\) the \((1+i)\)-th entry of \(a\).
Bad Root Searching Rule[]
The bad root searching rule for N1.1 in the sense of the terminology in the article of difference sequence system is the partial computable function \begin{eqnarray*} \textrm{Parent} \colon \textrm{FinSeq} \times \mathbb{N} & \to & \mathbb{N} \\ (a,i) & \mapsto & \textrm{Parent}(a,i) \end{eqnarray*} defined in the following recursive way:
- Denote by \(L\) the length of \(a\).
- If \(i \geq L\), then \(\textrm{Parent}(a,i)\) is not defined.
- Suppose \(i < L\).
- Suppose that there exists a \(j \in \mathbb{N}\) larger than \(i\) such that \(\textrm{Parent}(a,j)\) is defined and coincides with \(i\).
- Denote by \(k\) the maximum of such a \(j\).
- If \(a_0 \geq 1\) and \(a_k-1 \leq a_i < a_{L-1}\), then put \(b := 1\).
- Otherwise, put \(b:= 0\).
- Otherwise, put \(b := 0\).
- Suppose \(b = 0\).
- If there exists an \(m \in \mathbb{N}\) smaller than \(i\) such that \(a_m < a_i\), then \(\textrm{Parent}(a,i)\) is the maximum of such an \(m\).
- Otherwise, \(\textrm{Parent}(a,i)\) is not defined.
- Suppose \(b = 1\).
- If there exists an \(m \in \mathbb{N}\) smaller than \(i\) such that \(a_m \leq a_i\), then \(\textrm{Parent}(a,i)\) is the maximum of such an \(m\).
- Otherwise, \(\textrm{Parent}(a,i)\) is not defined.
- Suppose that there exists a \(j \in \mathbb{N}\) larger than \(i\) such that \(\textrm{Parent}(a,j)\) is defined and coincides with \(i\).
By the definition, the restriction of \(\textrm{Parent}\) to the direct product of the set of standard primitive sequences and \(\mathbb{N}\) coincides with the bad root searching rule for primitive sequence system. The main difference from the bad root searching rule for primitive sequence system is that \(((1,1,2),1)\) belongs to the domain of \(\textrm{Parent}\). Actually, we have \(\textrm{Parent}((1,1,2),1) = 0\).
Difference Sequence[]
Since \(\textrm{Parent}\) satisfies the axiom of a bad root searching rule in the sense of the terminology in the article for a difference sequence system, it induces the total computable maps \begin{eqnarray*} \begin{array}{lcrcl} \textrm{Ancestor} & \colon & \textrm{FinSeq} & \to & \textrm{FinSeq} \\ \textrm{RightNodes} & \colon & \textrm{FinSeq} & \to & \textrm{FinSeq} \\ \textrm{Kaiser} & \colon & \textrm{FinSeq} \setminus \{()\} & \to & \textrm{FinSeq} \\ \end{array} \end{eqnarray*} introduced in the same article. Roughly speaking, \(\textrm{Ancestor}(a)\) is the sequence of indices of ancestors of the rightmost entry of \(a\), \(\textrm{RightNodes}(a)\) is the sequence of entries of ancestors of the rightmost entry of \(a\), and \(\textrm{Kaiser}(a)\) is the difference sequence of \(\textrm{RightNodes}(a)\).
For an \(a \in \textrm{FinSeq} \setminus \{()\}\), we put \(\textrm{Height}(a) := \max \{k \in \mathbb{N} \mid a \in \textrm{dom}(\textrm{Kaiser}^{k+1})\}\), and denote by \(\textrm{Royal}(a)\) the diagonal difference sequence of \(a\) characterised by the following propeties:
- \(\textrm{Lng}(\textrm{Royal}(a)) = \textrm{Height}(a)\).
- For any \(i \in \mathbb{N}\) smaller than \(\textrm{Height}(a)\), \(\textrm{Royal}(a)_i = \textrm{RightNodes}(\textrm{Kaiser}^i(a))_0\).
Roughly Speaking, \(\textrm{Royal}(a)\) is the sequence given as the left edge of the tower of the ancestor subsequences of difference sequences of \(a\).
For example, when \(a = (0,1,4,13,20,30,44,64)\), then \(\textrm{Royal}(a) = (0,1,2,1,0,1)\). The tower of the difference sequences of \(a\) is constructed in the following way: \begin{eqnarray*} \begin{array}{rcccccccccccccccccc} \textrm{RightNodes}(\textrm{Kaiser}^5(a)) & = & & & & & & & & & & ( & \color{red}{1} & ) & & & & & \\ \textrm{Kaiser}^5(a) & = & & & & & & & & & & ( & 1 & ) & & & & & \\ \textrm{RightNodes}(\textrm{Kaiser}^4(a)) & = & & & & & & & & & ( & \color{red}{0} & , & 1 & ) & & & & \\ \textrm{Kaiser}^4(a) & = & & & & & & & & & ( & 0 & , & 1 & ) & & & & \\ \textrm{RightNodes}(\textrm{Kaiser}^3(a)) & = & & & & & & & & ( & \color{red}{1} & , & 1 & , & 2 & ) & & & \\ \textrm{Kaiser}^3(a) & = & & & & & & & & ( & 1 & , & 1 & , & 2 & ) & & & \\ \textrm{RightNodes}(\textrm{Kaiser}^2(a)) & = & & & ( & \color{red}{2} & , & & & & & 3 & , & 4 & , & 6 & ) & & \\ \textrm{Kaiser}^2(a) & = & & & ( & 2 & , & & & 4 & , & 3 & , & 4 & , & 6 & ) & & \\ \textrm{RightNodes}(\textrm{Kaiser}(a)) & = & & ( & \color{red}{1} & , & 3 & , & & & 7 & , & 10 & , & 14 & , & 20 & ) & \\ \textrm{Kaiser}(a) & = & & ( & 1 & , & 3 & , & 9 & , & 7 & , & 10 & , & 14 & , & 20 & ) & \\ \textrm{RightNodes}(a) & = & ( & \color{red}{0} & , & 1 & , & 4 & , & 13 & , & 20 & , & 30 & , & 44 & , & 64 & ) \\ a & = & ( & 0 & , & 1 & , & 4 & , & 13 & , & 20 & , & 30 & , & 44 & , & 64 & ) \end{array} \end{eqnarray*} The occurence of \(0\) in the difference sequences is a characteristic property of N primitive. It is possible because the bad root searching rule for N1.1 allows parents sharing the values of entries unlike other difference sequence systems.
Bad Root[]
We define a total computable map \begin{eqnarray*} \textrm{BadRoot} \colon \textrm{FinSeq} \setminus \{()\} & \to & \mathbb{N} \\ a & \mapsto & \textrm{BadRoot}(a) \end{eqnarray*} in the following recursive way:
- Put \(b := \textrm{Kaiser}(a)\)
- Put \(L_0 := \textrm{Lng}(a)\)
- Put \(L_1 := \textrm{Lng}(b)\)
- If \(L_1 = 0\), then \(\textrm{BadRoot}(a) := L_0-1\).
- Suppose \(L_1 \neq 0\).
- Put \(r := \textrm{BadRoot}(b)\).
- If \(r = L_1-1\), then \(\textrm{BadRoot}(a) := \textrm{Ancestor}(a)_r\).
- If \(r \neq L_1-1\), then \(\textrm{BadRoot}(a) := \textrm{Ancestor}(a)_{r+1}\).
As the name of the function indicates, \(\textrm{BadRoot}(a)\) is the bad root of \(a\) with respect to the bad root searching rule \(\textrm{Parent}\). The initial segment of \(a\) of length \(\textrm{BadRoot}(a)\) will be regarded as the good part of \(a\), and the rest final segment of \(a\) will be regarded as the bad part of \(a\) in the expansion rule.
For example, when \(a = (0,1,4,13,20,30,44,64)\), then \(\textrm{BadRoot}(a) = 6\). The bad root searching of \(a\) is executed in the following way: \begin{eqnarray*} \begin{array}{rcccccccccccccccccc} \textrm{Kaiser}^5(a) & = & & & & & & & & & & ( & \color{red}{1} & ) & & & & & \\ \textrm{Kaiser}^4(a) & = & & & & & & & & & ( & \color{red}{0} & , & 1 & ) & & & & \\ \textrm{Kaiser}^3(a) & = & & & & & & & & ( & 1 & , & \color{red}{1} & , & 2 & ) & & & \\ \textrm{Kaiser}^2(a) & = & & & ( & 2 & , & & & 4 & , & 3 & , & \color{red}{4} & , & 6 & ) & & \\ \textrm{Kaiser}(a) & = & & ( & 1 & , & 3 & , & 9 & , & 7 & , & 10 & , & \color{red}{14} & , & 20 & ) & \\ a & = & ( & 0 & , & 1 & , & 4 & , & 13 & , & 20 & , & 30 & , & \color{red}{44} & , & 64 & ) \\ & \rightsquigarrow & & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & & \color{red}{6} & & 7 & \end{array} \end{eqnarray*} Namely, mark the rightmost entry of the highest difference sequence. Then shift to the left downward. After then, repeat to shift right downward. The good part of \(a\) is \((0,1,4,13,20,30)\), and the bad part of \(a\) is \((44,64)\).
Reconstruction[]
We define a total computable map \begin{eqnarray*} \textrm{Reconstruct} \colon (\textrm{FinSeq} \setminus \{()\})^2 & \to & \textrm{FinSeq} \\ (d,a) & \mapsto & \textrm{Reconstruct}(d,a) \end{eqnarray*} in the following recursive way:
- Put \(r := \textrm{BadRoot}(a)\).
- Denote by \(b\) the sequence given by removing the first \(r\) entries from \(a\).
- Put \(L_0 := \textrm{Lng}(d)\).
- Put \(L_1 := \textrm{Lng}(\textrm{Ancestor}(b))\).
- Suppose \(L_1 \leq 1\).
- For each \((i,j) \in \mathbb{N} \times \mathbb{N}\) satisfying \(i+j <L_0\), define a \(c_{i,j} \in \mathbb{N}\) in the following recursive way:
- If \(j = 0\), then \(c_{i,j} := d_j\).
- If \(j \neq 0\), then \(c_{i,j} := c_{i,j-1}+c_{i+1,j-1}\).
- Set \(\textrm{Reconstruct}(d,a) := (c_{0,j})_{j=0}^{L_0-1}\).
- For each \((i,j) \in \mathbb{N} \times \mathbb{N}\) satisfying \(i+j <L_0\), define a \(c_{i,j} \in \mathbb{N}\) in the following recursive way:
- Suppose \(L_1 > 1\).
- Put \(q := \max \{k \in \mathbb{N} \mid k(L_1-1)+1 \leq L_0\}\).
- Put \(L_2 := \textrm{Lng}(b)\).
- For each \(i \in \mathbb{N}\) smaller than \((q-1)(L_2-1)\), we define a \(c_i \in \mathbb{N}\) in the following recursive way:
- Put \(q' := \max \{k \in \mathbb{N} \mid k(L_2-1) \leq i\}\).
- Put \(i' := i-q'(L_2-1)\).
- If \(q' = 0\), then \(c_i := a_{r+i}\).
- Suppose that \(q' \neq 0\) and \(i'\) is an entry of \(\textrm{Ancestor}(b)\).
- Denote by \(j' \in \mathbb{N}\) the unique number smaller than \(L_1\) satisfying \(i' = \textrm{Ancestor}(b)_{j'}\).
- If \(j' = 0\), put \(p := (q'-1)(L_2-1) + \textrm{Ancestor}(b)_{L_1-2}\).
- If \(j' \neq 0\), put \(p := q'(L_2-1) + \textrm{Ancestor}(b)_{j'-1}\).
- Set \(c_i := c_p + d_{q'(L_1-1)+j'}\).
- Suppose that \(q' \neq 0\) and \(i'\) is not an entry of \(\textrm{Ancestor}(b)\).
- Put \(j' := \max \{k \in \mathbb{N} \mid k < L_1 \land \textrm{Ancestor}(b)_k < i'\}\).
- Put \(p := q'(L_2-1) + \textrm{Ancestor}(b)_{j'}\)
- Set\(c_i := c_p + (c_{i-(L_2-1)} - c_{p-(L_2-1)}) + (d_{q'(L_1-1)+j'+1}- d_{(q'-1)(L_1-1)+j'+1})\).
- Set \(\textrm{Reconstruct}(d,a) := (c_i)_{i=0}^{(q-1)(L_2-1)-1}\).
Roughly speaking, \(\textrm{Reconstruct}(d,a)\) is a sequence such that the difference sequence of a suitable subsequence related to \(\textrm{Ancestor}(b)\) is given by \(d\).
For example, when \(d = (19,25,32,40,49)\) and \(a = (0,1,4,13,20,30,44,64)\), then \(\textrm{Reconstruct}(a,d) = (44,63,88,120,160)\). The reconstruction is executed in the following way: \begin{eqnarray*} \begin{array}{rccccccccccccccccc} d & = & & & & & & ( & 19 & , & 25 & , & 32 & , & 40 & , & 49 & ) \\ a & = & ( & 0 & , & \ldots & , & \color{red}{44} & , & 64 & ) & & & & & & & \\ & \rightsquigarrow & & & & & ( & \color{red}{44} & , & 63 & , & 88 & , & 120 & , & 160 & ) & \end{array} \end{eqnarray*} Here, we do not have a non-trivial offset, i.e. an entry between the bad root and the right most entry which is not an ancestor of the rightmost entry, and hence the reconstructed sequence is simply given by adding the entries of \(d\). Although the rightmost entry of \(d\) is not used in this case, it can be actually used in the computation of offsets. The reconstruction process of an entry which is not a copy of an ancestor of the rightmost entry using the difference of entries above adjacent ancestors of the rightmost entry placed at distinct sides from the reconstructed entry, is a distinguishing feature of N1.1 and N1.1½, and is not employed in N1.2½.
Expansion[]
We define a partial computable map \begin{eqnarray*} [ \ ] \colon \textrm{FinSeq} \times \mathbb{N} & \to & \textrm{FinSeq} \\ (a,n) & \mapsto & a[n] \end{eqnarray*} in the following recursive way:
- If \(a = ()\), then \(a[n] := ()\).
- If \(a \neq ()\) and \(\textrm{Kaiser}(a) = ()\), then \(a[n]\) is the sequence given by removing the rightmost entry from \(a\).
- If \(a = (0,1)\), then \(a[n]\) is the sequence of length \(n+1\) whose entries are \(0\).
- Suppose \(a \neq ()\), \(\textrm{Kaiser}(a) \neq ()\), and \(a \neq (0,1)\).
- Put \(H := \textrm{Height}(a)\).
- Denote by \(d \in \textrm{FinSeq} \setminus \{()\}\) the sequence given by removing the first \(H-1\) entries from \(\textrm{Royal}(a)[n+H-1]\).
- For each \(i \in \mathbb{N}\) smaller than \(H\), define a \(C_i \in \textrm{FinSeq}\) in the following recursive way:
- If \(i = H-1\), then \(C_i := \textrm{Reconstruct}(d,\textrm{Kaiser}^{H-1}(a))\).
- If \(i \neq H-1\), then \(C_i := \textrm{Reconstruct}(C_{i+1},\textrm{Kaiser}^i(a))\).
- Put \(r := \textrm{BadRoot}(a)\).
- Denote by \(g \in \textrm{FinSeq}\) the initial segment of \(a\) of length \(r\).
- Denote by \(b \in \textrm{FinSeq}\) the sequence given by removing the first \(r\) entries from \(a\).
- Denote by \(b^{(n)} \in \textrm{FinSeq} \setminus \{()\}\) the initial segment of \(C_0\) of length \(n(\textrm{Lng}(b)-1)\).
- Set \(a[n] := g \frown b^{(n)}\).
Since \([ \ ]\) recursively call \([ \ ]\) itself, it is not trivial that \(((0,1,k),n) \in \textrm{dom}([ \ ])\) for any \((k,n) \in \mathbb{N}^2\). Actually, we have \(((0,1,k),n) \in \textrm{dom}([ \ ])\) and \begin{eqnarray*} (0,1,k)[n] = \left\{ \begin{array}{ll} (0,1) & (k = 0) \\ (\underbrace{0,1,0,1,\ldots,0,1}_{n+1}) & (k = 1) \\ (0,1,(k-1),(k-1)^2,\ldots,(k-1)^n) & (k > 1) \end{array} \right. \end{eqnarray*} for any \((n,m) \in \mathbb{N}^2\) by induction on \(n\). We will show totality of the restriction of \([ \ ]\) to a certain subset later.
For example, when \(a = (0,1,4,13,20,30,44,64)\) and \(n = 4\), then \(a[n] = (0,1,4,13,20,30,44,63,88,120,160)\). The expansion of \(a\) is executed in the following way: \begin{eqnarray*} \begin{array}{rccccccccccccccccccccc} C_5 & = & & ( & \color{red}{0} & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & ) \\ C_4 & = & ( & \color{red}{0} & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & ) & \\ C_3 & = & & ( & \color{red}{1} & , & 1 & , & 1 & , & 1 & , & 1 & , & 1 & , & 1 & , & 1 & ) & & \\ C_2 & = & & & ( & \color{red}{4} & , & 5 & , & 6 & , & 7 & , & 8 & , & 9 & , & 10 & ) & & & \\ C_1 & = & & & & ( & \color{red}{14} & , & 19 & , & 25 & , & 32 & , & 40 & , & 49 & ) & & & & \\ C_0 & = & & & & & ( & \color{red}{44} & , & 63 & , & 88 & , & 120 & , & 160 & ) & & & & & \\ a & = & ( & 0 & , & \ldots & , & \color{red}{44} & , & 64 & ) & & & & & & & & & & & \\ & \rightsquigarrow & ( & 0 & , & \ldots & , & \color{red}{44} & , & 63 & , & 88 & , & 120 & , & 160 & ) & & & & & \end{array} \end{eqnarray*} Namely, expand the diagonal sequence given by \(\textrm{Royal}(a)\), replace the highest difference sequence by the sequence reconstructed by the expanded diagonal sequence, and repeat the reconstruction step for each difference sequences.
Standard Form[]
We define a partial computable map \begin{eqnarray*} \textrm{Expand} \colon \textrm{FinSeq} \times \textrm{FinSeq} & \to & \textrm{FinSeq} \\ (a,n) & \mapsto & \textrm{Expand}(a,n) \end{eqnarray*} in the following recursive way:
- Put \(L := \textrm{Lng}(n)\).
- If \(L = 0\), then \(\textrm{Expand}(a,n) := a\).
- Suppose \(L \neq 0\).
- Denote by \(n'\) the initial segment of \(n\) of length \(L-1\).
- Set \(\textrm{Expand}(a,n) := \textrm{Expand}(a,n')[n_{L-1}]\).
Namely, \(\textrm{Expand}(a,n)\) is just the formalisation of the iterated expansion \(a[n_0] \cdots [n_{L-1}]\).
We denote by \(<_{\textrm{lex}}\) the lexicographic ordering on \(\textrm{FinSeq}\). By the structural induction with respect to \([ \ ]\), we obtain the following:
| Proposition (order-lowering property) |
|---|
| For any \((a,n) \in \textrm{dom}(\textrm{Expand})\), if \(a \neq ()\) and \(n \neq ()\), then \(\textrm{Expand}(a,n) <_{\textrm{lex}} a\). |
By the order-lowering property, there is no simple infinite loop in expansions, i.e. there exists no \((a,n) \in \textrm{dom}(\textrm{Expand})\) such that \(a \neq ()\), \(n \neq ()\), and \(\textrm{Expand}(a,n) = a\). It implies that if there is an infinite loop in expansions, then it is so complicated that we need a non-trivial argument in order to show that it is actually an infinite loop.
For an \(a \in \textrm{FinSeq}\), We denote by \(I_a \subset \textrm{FinSeq}\) the recursively enumerable subset \(\{\textrm{Expand}(a,n) \mid n \in \textrm{FinSeq} \setminus \{()\} \land (a,n) \in \textrm{dom}(\textrm{Expand})\}\).
We put \(OT := \bigcup_{k \in \mathbb{N}} I_{(0,1,k)}\), and call an element of \(OT\) a standard N primitive sequence. Since we have \(\textrm{Expand}((0,1,1),(1,0)) = (0,1,0)\) and \(\textrm{Expand}((0,1,2),(1)) = (0,1,1)\), \((0,1,k)\) is a standard N primitive sequence for any \(k \in \mathbb{N}\) by induction on \(k\).
By the definition, \(\textrm{Royal}\) does not increase the length. Since the lexicographic order restricted to the subset of sequence of length bounded by a fixed upperbound is well-founded and \(OT\) is closed under \(\textrm{Expand}\), we obtain the following corollary of the order-lowering property:
| Corollary (totality of the restriction of \([ \ ]\)) |
|---|
| The set \(OT \times \mathbb{N}\) (resp. \(OT \times \textrm{FinSeq}\)) is contained in \(\textrm{dom}([ \ ])\) (resp. \(\textrm{dom}(\textrm{Expand})\)). |
Recursiveness[]
We show the recursiveness of \(OT\) in a way analogous to the proof by the Googology Wiki user fish of the recursiveness of the subset of standard Bashicu matrices with respect to Bashicu matrix system version 2.3.
We denote by \(\textrm{FinSeq}^{< \omega}\) the set of finite arrays in \(\textrm{FinSeq}\). We define a partial recursive map \begin{eqnarray*} \textrm{ApproximateSequence} \colon \textrm{FinSeq} \times \textrm{FinSeq} & \to & \textrm{FinSeq}^{< \omega} \setminus \{()\} \\ (a,b) & \mapsto & \textrm{ApproximateSequence}(a,b) \end{eqnarray*} in the following recursive way:
- Put \(L_1 := \textrm{Lng}(a)\).
- Put \(c := b[L_1]\).
- If \(a\) is an initial segment of \(c\), then \(\textrm{ApproximateSequence}(a,b) := (b,a)\).
- If \(c <_{\textrm{lex}} a\), then \(\textrm{ApproximateSequence}(a,b) := (b)\).
- Suppose that \(a\) is not an initial segment of \(c\) and \(a <_{\textrm{lex}} c\).
- Put \(L_2 := \textrm{Lng}(c)\).
- Denote by \(i \in \mathbb{N}\) the least natural number satisfying \(i < \min \{L_1,L_2\}\) and \(a_i < c_i\).
- Denote by \(d \in \textrm{FinSeq}\) the initial segment of \(c\) of length \(i+1\).
- Set \(\textrm{ApproximateSequence}(a,b) := (b) \frown \textrm{ApproximateSequence}(a,d)\).
Suppose \(b \in OT\). Then \(c\) is defined by the totality of the restriction of \([ \ ]\), and is standard by the definition. Moreover, since \([0]\) is the operation removing the rightmost entry as long as the input is a standard N primitive sequence other than \((0)\), \(d\) is derived by the repetition of \([0]\) to \(c\). Therefore \(d\) is also standard. In particular, by order-lowering property and the well-foundedness of \(<_{\textrm{lex}}\) restricted to \(\textrm{N}^{L_1}\), the computation of \(\textrm{ApproximateSequence}(a,b)\) terminates, and its output is an array whose entries are standard except for the rightmost entry.
We define a total recursive map \begin{eqnarray*} \textrm{IsStandard} \colon \textrm{FinSeq} \setminus \{()\} & \to & \{0,1\} \\ a & \mapsto & \textrm{IsStandard}(a) \end{eqnarray*} in the following recursive way:
- Put \(L := \textrm{Lng}(a)\).
- If \(L = 1\) and \(a_0 = 0\), then \(\textrm{IsStandard}(a) := 1\).
- Suppose \(L \geq 2\), \(a_0 = 0\), and \(a_1 = 0\).
- If every entry of \(a\) is \(0\), then , then \(\textrm{IsStandard}(a) := 1\).
- If \(a\) has a non-zero entry, then , then \(\textrm{IsStandard}(a) := 0\).
- If \(2 \leq L \leq 3\), \(a_0 = 0\), and \(a_1 = 1\), then \(\textrm{IsStandard}(a) := 1\).
- If \(L \geq 2\), \(a_0 = 0\), and \(a_1 > 1\), then \(\textrm{IsStandard}(a) := 0\).
- Suppose \(L \geq 4\), \(a_0 = 0\), and \(a_1 = 1\).
- Denote by \(b \in \textrm{FinSeq}\) the rightmost entry of \(\textrm{ApproximateSequence}(a,(0,1,a_2+1))\).
- If \(a = b\), then \(\textrm{IsStandard}(a) := 1\).
- If \(a \neq b\), then \(\textrm{IsStandard}(a) := 0\).
- If \(a_0 \neq 0\), then \(\textrm{IsStandard}(a) := 0\).
This is an analogue of the algorithm by the Googology Wiki user rpakr to determine the standardness of a Bashicu matrix. By the argument above, \(\textrm{IsStandard}\) is actually a total map because \((0,1,a_2+1)\) in clause 6-1 in the definition of \(\textrm{IsStandard}\) is standard. The equality \(a = b\) in the clause 6-2 in the definition of \(\textrm{IsStandard}\) implies that the computation of \(\textrm{ApproximateSequence}(a,(0,1,a_2+1))\) terminates in the clause 3 in the definition of \(\textrm{ApproximateSequence}\), and hence \(a\) is an initial segment of a standard N primitive sequence, which is standard by the argument on \([0]\) above.
The inequality \(a \neq b\) in the clause 6-3 in the definition of \(\textrm{IsStandard}\) implies that the computation of \(\textrm{ApproximateSequence}(a,(0,1,a_2+1))\) terminates in the clause 4 in the definition of \(\textrm{ApproximateSequence}\). In this case, the rightmost entry \(b\) of \(\textrm{ApproximateSequence}(a,(0,1,a_2+1))\) satisfies \(a <_{\textrm{lex}} b\) and \(b[n] <_{\textrm{lex}} a\) for any \(n \in \mathbb{N}\). We show that \(a\) is not standard by reduction to the absurd.
Assume that \(a\) is standard. Then there exists an \((k,n) \in \mathbb{N} \times (\textrm{FinSeq} \setminus \{()\})\) such that \(\textrm{Expand}((0,1,k),n) = a\). Put \(L_1:= \textrm{Lng}(n)+1\) and \(L_2 := \textrm{Lng}(\textrm{ApproximateSequence}(a,(0,1,a_2+1)))\). For each \(i \in \mathbb{N}\) smaller than \(L_1\), we denote by \(m_i \in OT\) the initial segment of \(n\) of length \(i\). By \((0,1,a_2) <_{\textrm{lex}} (0,1,k)\) and the definition of \([ \ ]\), there exists an \(i_0 \in \mathbb{N}\) smaller than \(L_1\) such that \(\textrm{Expand}((0,1,k),m_{i_0}) = (0,1,a_2+1)\). For any \(j \in \mathbb{N}\) smaller than \(L_2\), if \(\textrm{ApproximateSequence}(a,(0,1,a_2+1))_j\) is an entry of \((\textrm{Expand}((0,1,k),m_i))_{i=0}^{L_1-1}\), then so is \(\textrm{ApproximateSequence}(a,(0,1,a_2+1))_{j+1}\) by the definition of \(\textrm{ApproximateSequence}\) and \([ \ ]\). Therefore by induction on \(j\), \(\textrm{ApproximateSequence}(a,(0,1,a_2+1))\) forms a subsequence of \((\textrm{Expand}((0,1,k),m_i))_{i=0}^{L_1-1}\). It implies \(b = \textrm{Expand}((0,1,k),m_i)\) for some \(i \in \mathbb{N}\) smaller than \(L_1-1\), and hence \(b[n_i] = a\). This contradicts \(b[n_i] <_{\textrm{lex}} a\). Thus \(a\) is not standard.
As a consequence, we obtain the following:
| Proposition (recursiveness of \(OT\)) |
|---|
| The characteristic function of \(OT \subset \textrm{FinSeq} \setminus \{()\}\) coincides with the total recurisve function \(\textrm{IsStandard}\), and hence \(OT\) is a recursive subset of \(\textrm{FinSeq}\). |
Well-Foundedness[]
We define the binary relation \(a < b\) on \((a,b) \in \textrm{FinSeq}^2\) as the existence of an \(n \in \textrm{FinSeq}\) such that \(b \neq ()\), \(n \neq ()\), \((b,n) \in \textrm{dom}(\textrm{Expand})\), and \(a = \textrm{Expand}(b,n)\). The well-foundedness of the system \((OT,<)\) is open.
In order to argue the termination and the strength of the resulting computable large function which will be introduced later, we prepare a conjecture.
| Conjecture (Axiom \(\textrm{WFN1.1}\)) |
|---|
| The restriction of \(<\) on \(OT\) is a strict well-ordering. |
Of course, if we find an infinite loop in expansions of standard N primitive sequences, then \(\textrm{WFN1.1}\) is disproved. Although we do not know whether \(\textrm{WFN1.1}\) is consistent with \(\textrm{ZFC}\) or not, we sometimes explicitly assume it.
By the order-lowering property, we immediately obtain the following:
| Proposition (well-foundedness of N1.1) |
|---|
| Assume \(\textrm{WFN1.1}\). Let \(a \in OT\). For any infinite sequence \(n\) of natural numbers, there exists a finite initial segment \(n'\) of \(n\) such that \(\textrm{Expand}(a,n') = ()\). |
Ordinal Notation[]
Since \(\textrm{WFN1.1}\) implies that the restriction of \(<\) is a strict total ordering, we obtain the following corollary of the order-lowering property:
| Corollary (comparison of \(<\) and \(<_{\textrm{lex}}\)) |
|---|
| Assume \(\textrm{WFN1.1}\). Then the restriction of \(<\) on \(OT\) coincides with the restriction of \(<_{\textrm{lex}}\) on \(OT\). |
Since \(<_{\textrm{lex}}\) is recursive, the recursiveness of \(OT\) implies the following corollary of the comparison of \(<\) and \(<_{\textrm{lex}}\):
| Corollary (recursive well-foundedness of \((OT,<)\)) |
|---|
| Assume \(\textrm{WFN1.1}\). Then \((OT,<)\) forms an ordinal notation. |
For an \(a \in \textrm{FinSeq}\), if \((I_a,<)\) is a well-ordered set, we denote by \(o(a) \in \omega_1\) its ordinal type. By the recursive well-foundedness of \((OT,<)\), \(o(a)\) is defined and is a recursive ordinal for any \(a \in OT\) under the assumption of \(\textrm{WFN1.1}\).
Large Function[]
We define a partial computable map \begin{eqnarray*} F \colon \mathbb{N} \times \textrm{FinSeq} \times \mathbb{N} & \to & \mathbb{N} \\ (m,a,n) & \mapsto & F^m[a](n) \end{eqnarray*} in the following recursive way:
- If \(m = 0\), then \(F^m[a](n) := n\).
- Suppose \(m = 1\).
- If \(a = ()\), then \(F^m[a](n) := n+1\).
- If \(a \neq ()\) and \(\textrm{Kaiser}(a) = ()\), then \(F^m[a](n) := F^n[a[0]](n)\).
- If \(a \neq ()\) and \(\textrm{Kaiser}(a) \neq ()\), then \(F^m[a](n) := F^1[a[n]](n)\).
- If \(m > 1\), then \(F^m[a](n) := F^{m-1}[a](F^1[a](n))\).
We define a partial computable map \begin{eqnarray*} N \colon \textrm{FinSeq} \times \mathbb{N} & \to & \mathbb{N} \\ (a,n) & \mapsto & N(a,n) \end{eqnarray*} by setting \(N(a,n) = F^1[a](n)\). Since this construction is essentially equivalent to fast-growing hierarchy, \(N(a,n)\) coincides with \(f_{o(a)}(n)\) with respect to a suitable system of fundamental sequences as long as \(o(a)\) is defined. By the well-foundedness of N1.1 and the recursive well-foundedness of \((OT,<)\), we obtain the following:
| Theorem (termination of N) |
|---|
| Assume \(\textrm{WFN1.1}\). Then \(\textrm{dom}(N)\) contains \(OT \times \mathbb{N}\), and the assignment \(n \mapsto N((0,1,n),n)\) gives a total computable map \(\mathbb{N} \to \mathbb{N}\), which coincides with \(f_{\alpha}(n)\), where \(\alpha \in \omega_1^{\textrm{CK}}\) is the ordinal type of \((OT,<)\) equipped with a suitable recursive system of fundamental sequences. |
Of course, the assumption of \(\textrm{WFN1.1}\) is essential in the proof of the termination of N. In particular, the totality of the restriction of \(N\) to \(OT \times \mathbb{N}\) in \(\textrm{ZFC}\) set theory is open.
Large Number[]
Nayuta Ito coined 7 large numbers based on a naming system using N primitive. Since the naming system is given by a complicated rule referring to Chinese letters, we only show the results of the nameing for those specific 7 numbers.
| name | definition |
|---|---|
| 第一宇宙破壊数 | \(F^1[(0,1,2)](1)\) with respect to N1.1½ |
| 第二宇宙破壊数 | \(F^1[(0,1,2,4)](2)\) with respect to N1.1½ |
| 第二宇宙破壊数改三 | \(F^1[(0,1,2,4,7)](2)\) with respect to N1.1½ |
| 第二宇宙破壊数改三改三 | \(F^1[(0,1,2,4,7,10)](2)\) with respect to N1.1½ |
| 第三宇宙破壊数 | \(F^1[(0,1,2,4,8)](3)\) with respect to N1.1½ |
| 第四宇宙破壊数 | \(F^1[(0,1,2,4,8,16)](4)\) with respect to N1.1½ |
| ６ (or 全角の6) | the maximum of \(6\) and \(F^1[a](6)\) with respect to N3.0, where \(a\) runs through all sequences satisfying that \((1,a,6) \in \textrm{dom}(F)\), \(\textrm{Lng}(a) \leq 6\), and the sum of entries of \(a\) is smaller than or equal to \(6 \times 6\) |
Since the definition of ６ directly refers to \(\textrm{dom}(F)\), we do not have an evidence of its computability. At least, since ６ is the maximum of a finite set of natural numbers including at least one element, i.e. 6, it is well-defined. In addition, if N3.0 is verified to terminate for any standard N primitive sequence with respect to N3.0 below \((0,1,35)\), then it is actually computable and is expected to be much larger than Bashicu matrix number with respect to Bashicu matrix system version 2.3, because the standard N primitive sequence \((0,1,3)\) with respect to N3.0 is expected to correspond to its limit.
Lower bound[]
It is proven that ６ > \( 10^{12} \). [3] In particular, taking the maximum with \(6\) in the definition of ６ is in fact unnecessary.
Upper bound[]
Since the \(3\)-ary relation \((m,a,n) \in \textrm{dom}(F)\) is computable by the halting problem \(\textrm{Halt}\) of Turing machines, ６ is computable by an oracle Turing machine. Therefore ６ is bounded by a specific value of the second order busy beaver function \(\Sigma_2\) whose input is a meta natural number. Namely, it is expected to be roughly bounded by \(\Sigma_2(10^{100})\).
In addition, if N3.0 is verified to terminate for any standard N primitive sequence with respect to N3.0 below \((0,1,35)\), then ６ is computable by the argument above, and hence it is expected to be bounded by \(\Sigma(10^{100})\), where \(\Sigma\) is the busy beaver function.
Japanese Letters[]
The letter "第" means "the -th" for the ordinal numerals, and is pronounced as "dαɪ". The letter "一" (resp. "二", "三", "四") means "one" (resp. "two", "three", "four"), and is pronounced as "itʃ" (resp. "ni", "sʌn/sən/sαn", "jɔn"). The word "宇宙" means "universe", and is pronounced as "u tʃreuː". The word "破壊" means "destruction", and is pronounced as "hʌ/hə/hα kʌi/kəi/kαi". The word "数" means "number", and is pronounced as "suː" (or "kʌz/kəz/kαz" depending on the situation). The letter "改" means "updated/renewed/revised", and is pronounced as "kʌi/kəi/kαi". Therefore "第二宇宙破壊数改三改三" roughly means "the third revision of the third revision of the second universe destruction number", and "第四宇宙破壊数" roughly means "the fourth universe destruction number"
The letter "６" means "six", and is pronounced as "rɔk/lɔk". The word "全角の" means "two-byte", and is pronounced as "zen/zεn kʌk/kək/kαk nɔ". Therefore "全角の6" roughly means "two-byte letter corresponding to 6".
Example[]
Although N1.1 is relatively easy to handle compared to other versions including ½ in the names, the computation rules of expansions of standard N primitive sequences are still complicated. In order to grasp the behaviour, we need to observe explicit computations and results of sufficiently generic expansions.
Demonstration of Computation[]
We show computation steps of \((0,1,4,13,20,30,44,64)[4]\) with respect to N1.1. As we have already computed, we have \(\textrm{Height}((0,1,4,13,20,30,44,64)) = 6\), \(\textrm{Royal}((0,1,4,13,20,30,44,64)) = (0,1,2,1,0,1)\), and \(\textrm{BadRoot}((0,1,4,13,20,30,44,64)) = 6\). Since the computation of \((0,1,4,13,20,30,44,64)[4]\) calls \(\textrm{Royal}((0,1,4,13,20,30,44,64))[4+\textrm{Height}((0,1,4,13,20,30,44,64))]\), we need to compute \((0,1,2,1,0,1)[10]\).
Exhibit the tower of difference sequences of \((0,1,2,1,0,1)\). \begin{eqnarray*} \begin{array}{rccccccccccccc} \textrm{RightNodes}(\textrm{Kaiser}(a)) & = & & & & & & & & & & ( & \color{red}{1} & ) & \\ \textrm{Kaiser}(a) & = & & & & & & & & & & ( & 1 & ) & \\ \textrm{RightNodes}(a) & = & & & & & & & & & ( & \color{red}{0} & , & 1 & ) \\ a & = & ( & 0 & , & 1 & , & 2 & , & 1 & , & 0 & , & 1 & ) \end{array} \end{eqnarray*} We obtain \(\textrm{Height}((0,1,2,1,0,1)) = 2\) and \(\textrm{Royal}((0,1,2,1,0,1)) = (0,1)\). Since the computation of \((0,1,2,1,0,1)[10]\) calls \(\textrm{Royal}((0,1,2,1,0,1))[10+\textrm{Height}((0,1,2,1,0,1))]\), we need to compute \((0,1)[12]\).
Exhibit the tower of the difference sequences of \((0,1)\). \begin{eqnarray*} \begin{array}{rcccccc} \textrm{RightNodes}(\textrm{Kaiser}(a)) & = & & ( & \color{red}{1} & ) & \\ \textrm{Kaiser}(a) & = & & ( & 1 & ) & \\ \textrm{RightNodes}(a) & = & ( & \color{red}{0} & , & 1 & ) \\ a & = & ( & 0 & , & 1 & ) \end{array} \end{eqnarray*} We obtain \(\textrm{Height}((0,1)) = 2\) and \(\textrm{Royal}((0,1)) = (0,1)\). Since the computation of \((0,1)[12]\) calls \(\textrm{Royal}((0,1))[12+\textrm{Height}((0,1))]\), we need to compute \((0,1)[14]\)... Wait! Is it an infinite loop? No, no. Please remember that \((0,1)\) is the exception in the computation rule of the expansion. Namely, \((0,1)[12]\) is directly defined as \((0,0,0,0,0,0,0,0,0,0,0,0,0)\).
Next, we need to calculate \(\textrm{BadRoot}((0,1))\). Although the computation of \(\textrm{BadRoot}((0,1,4,13,20,30,44,64))\) above includes the computation of \(\textrm{BadRoot}((0,1))\), we show its computation process in order to help readers to understand bad roots better. For this purpose, we need to compute \(\textrm{BadRoot}(\textrm{Kaiser}((0,1)))\). As we computed above, we have \((\textrm{Kaiser}((0,1)) = 1\), and hence \(\textrm{BadRoot}(\textrm{Kaiser}((0,1))) = \textrm{BadRoot}((1))\). By the definition of \(\textrm{Kaiser}\), we have \(\textrm{Kaiser}((1)) = ()\) and hence \(\textrm{BadRoot}((1)) = \textrm{Lng}((1))-1 = 1-1 = 0\).
Again exhibit the tower of the difference sequences of \((0,1)\). \begin{eqnarray*} \begin{array}{rcccccc} \textrm{Kaiser}(a) & = & & ( & \color{red}{1} & ) & \\ a & = & ( & \color{red}{0} & , & 1 & ) \\ & \rightsquigarrow & & \color{red}{0} & & 1 & \end{array} \end{eqnarray*} Therefore we obtain \(\textrm{BadRoot}(\textrm{Kaiser}((0,1))) = 0\).
Reconstruct \((0,1,2,1,0,1)[10]\) from the diagonal \((0,0,0,0,0,0,0,0,0,0,0,0,0)\). \begin{eqnarray*} \begin{array}{rcccccccccccccccccc} & & & & & & & & & & & & & & ( & \vdots & \vdots & \vdots & ) & & & \\ & & & & & & & & & & & & & ( & 0 & , & \ldots & , & 0 & ) & & \\ & & & & & & & & & & & & ( & 0 & , & 0 & , & \ldots & , & 0 & ) & \\ C_1 & = & & & & & & & & & & ( & \color{red}{0} & , & 0 & , & \ldots & , & 0 & , & 0 & ) \\ C_0 & = & ( & 0 & , & 1 & , & 2 & , & 1 & , & \color{red}{0} & , & 0 & , & 0 & , & \ldots & , & 0 & ) & \\ a & = & ( & 0 & , & 1 & , & 2 & , & 1 & , & \color{red}{0} & , & 1 & ) \\ & \rightsquigarrow & ( & 0 & , & 1 & , & 2 & , & 1 & , & \color{red}{0} & , & 0 & , & 0 & , & 0 & , & \ldots & , & 0 & ) & \end{array} \end{eqnarray*} Therefore we obtain \((0,1,2,1,0,1)[10] = (0,1,2,1,0,0,0,0,0,0,0,0,0,0)\).
Reconstruct \((0,1,4,13,20,30,44,64)[4]\) from the diagonal \((0,1,2,1,0,0,0,0,0,0,0,0,0,0)\). \begin{eqnarray*} \begin{array}{rccccccccccccccccccccc} & & & & & & ( & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & ) & & & & & & \\ & & & & & ( & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & ) & & & & \\ & & & & ( & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & ) & & \\ C_5 & = & & ( & \color{red}{0} & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & ) \\ C_4 & = & ( & \color{red}{0} & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & , & 0 & ) & \\ C_3 & = & & ( & \color{red}{1} & , & 1 & , & 1 & , & 1 & , & 1 & , & 1 & , & 1 & , & 1 & ) & & \\ C_2 & = & & & ( & \color{red}{4} & , & 5 & , & 6 & , & 7 & , & 8 & , & 9 & , & 10 & ) & & & \\ C_1 & = & & & & ( & \color{red}{14} & , & 19 & , & 25 & , & 32 & , & 40 & , & 49 & ) & & & & \\ C_0 & = & & & & & ( & \color{red}{44} & , & 63 & , & 88 & , & 120 & , & 160 & ) & & & & & \\ a & = & ( & 0 & , & \ldots & , & \color{red}{44} & , & 64 & ) & & & & & & & & & & & \\ & \rightsquigarrow & ( & 0 & , & \ldots & , & \color{red}{44} & , & 63 & , & 88 & , & 120 & , & 160 & ) & & & & & \end{array} \end{eqnarray*} Therefore we obtain \((0,1,4,13,20,30,44,64)[4] = (0,1,4,13,20,30,44,63,88,120,160)\).
Table of Expansions[]
Here is a table of examples of expansions of standard N primitive sequences with respect to N1.1.
| sequence | expansion |
|---|---|
| \(()\) | \(()\) |
| \((0)\) | \(()\) |
| \((0,0)\) | \((0)\) |
| \((0,0,0)\) | \((0,0)\) |
| \((0,1)\) | \((0,0,0,\ldots)\) |
| \((0,1,0)\) | \((0,1)\) |
| \((0,1,0,1)\) | \((0,1,0,0,0,\ldots)\) |
| \((0,1,1)\) | \((0,1,0,1,\ldots)\) |
| \((0,1,1,0)\) | \((0,1,1)\) |
| \((0,1,1,0,1)\) | \((0,1,1,0,0,0,\ldots)\) |
| \((0,1,1,0,1,1)\) | \((0,1,1,0,1,0,1,\ldots)\) |
| \((0,1,1,1)\) | \((0,1,1,0,1,1,\ldots)\) |
| \((0,1,2)\) | \((0,1,1,1,\ldots)\) |
| \((0,1,2,0)\) | \((0,1,2)\) |
| \((0,1,2,1)\) | \((0,1,2,0,1,2,\ldots)\) |
| \((0,1,2,2)\) | \((0,1,2,1,2,\ldots)\) |
| \((0,1,2,3)\) | \((0,1,2,2,2,\ldots)\) |
| \((0,1,2,4)\) | \((0,1,2,3,4,\ldots)\) |
| \((0,1,2,4,0)\) | \((0,1,2,4)\) |
| \((0,1,2,4,1)\) | \((0,1,2,4,0,1,2,4,\ldots)\) |
| \((0,1,2,4,2)\) | \((0,1,2,4,1,2,4,\ldots)\) |
| \((0,1,2,4,3)\) | \((0,1,2,4,2,4,2,4,\ldots)\) |
| \((0,1,2,4,4)\) | \((0,1,2,4,3,5,4,6,\ldots)\) |
| \((0,1,2,4,5)\) | \((0,1,2,4,4,4,\ldots)\) |
| \((0,1,2,4,5,0)\) | \((0,1,2,4,5)\) |
| \((0,1,2,4,5,1)\) | \((0,1,2,4,5,0,1,2,4,5,\ldots)\) |
| \((0,1,2,4,5,2)\) | \((0,1,2,4,5,1,2,4,5,\ldots)\) |
| \((0,1,2,4,5,3)\) | \((0,1,2,4,5,2,4,5,\ldots)\) |
| \((0,1,2,4,5,4)\) | \((0,1,2,4,5,3,5,6,4,6,7,\ldots)\) |
| \((0,1,2,4,5,5)\) | \((0,1,2,4,5,4,5,4,5,\ldots)\) |
| \((0,1,2,4,5,6)\) | \((0,1,2,4,5,5,5,5,\ldots)\) |
| \((0,1,2,4,5,7)\) | \((0,1,2,4,5,6,7,8,9,\ldots)\) |
| \((0,1,2,4,5,7,0)\) | \((0,1,2,4,5,7)\) |
| \((0,1,2,4,5,7,1)\) | \((0,1,2,4,5,7,0,1,2,4,5,7,\ldots)\) |
| \((0,1,2,4,5,7,2)\) | \((0,1,2,4,5,7,1,2,4,5,7,\ldots)\) |
| \((0,1,2,4,5,7,3)\) | \((0,1,2,4,5,7,2,4,5,7,\ldots)\) |
| \((0,1,2,4,5,7,4)\) | \((0,1,2,4,5,7,3,5,6,8,\ldots)\) |
| \((0,1,2,4,5,7,5)\) | \((0,1,2,4,5,7,4,5,7,\ldots)\) |
| \((0,1,2,4,5,7,6)\) | \((0,1,2,4,5,7,5,7,5,7,\ldots)\) |
| \((0,1,2,4,5,7,7)\) | \((0,1,2,4,5,7,6,8,7,9,8,10,9,11,\ldots)\) |
| \((0,1,2,4,5,7,8)\) | \((0,1,2,4,5,7,7,7,\ldots)\) |
| \((0,1,2,4,6)\) | \((0,1,2,4,5,7,8,10,11,13,14,16,\ldots)\) |
| \((0,1,2,4,6,0)\) | \((0,1,2,4,6)\) |
| \((0,1,2,4,6,1)\) | \((0,1,2,4,6,0,1,2,4,6,\ldots)\) |
| \((0,1,2,4,6,2)\) | \((0,1,2,4,6,1,2,4,6,\ldots)\) |
| \((0,1,2,4,6,3)\) | \((0,1,2,4,6,2,4,6,\ldots)\) |
| \((0,1,2,4,6,4)\) | \((0,1,2,4,6,3,5,7,4,6,8,\ldots)\) |
| \((0,1,2,4,6,5)\) | \((0,1,2,4,6,4,6,4,6,\ldots)\) |
| \((0,1,2,4,6,6)\) | \((0,1,2,4,6,5,7,6,8,\ldots)\) |
| \((0,1,2,4,6,7)\) | \((0,1,2,4,6,6,6,6,\ldots)\) |
| \((0,1,2,4,6,8)\) | \((0,1,2,4,6,7,9,11,12,14,16,\ldots)\) |
| \((0,1,2,4,6,9)\) | \((0,1,2,4,6,8,10,12,14,16,18,\ldots)\) |
| \((0,1,2,4,7)\) | \((0,1,2,4,6,9,12,16,20,25,30,\ldots)\) |
| \((0,1,2,4,8)\) | \((0,1,2,4,7,11,16,22,29,37,46,\ldots)\) |
| \((0,1,3)\) | \((0,1,2,4,8,16,32,64,128,256,\ldots)\) |
| \((0,1,3,0)\) | \((0,1,3)\) |
| \((0,1,3,1)\) | \((0,1,3,0,1,3,\ldots)\) |
| \((0,1,3,2)\) | \((0,1,3,1,3,1,3,\ldots)\) |
| \((0,1,3,3)\) | \((0,1,3,2,5,4,9,8,17,16,33,32,\ldots)\) |
| \((0,1,3,4)\) | \((0,1,3,3,3,3,3,\ldots)\) |
| \((0,1,3,5)\) | \((0,1,3,4,7,9,14,18,27,35,52,68,\ldots)\) |
| \((0,1,3,6)\) | \((0,1,3,5,8,13,22,39,72,137,\ldots)\) |
| \((0,1,3,6,0)\) | \((0,1,3,6)\) |
| \((0,1,3,6,1)\) | \((0,1,3,6,0,1,3,6,\ldots)\) |
| \((0,1,3,6,2)\) | \((0,1,3,6,1,3,6,\ldots)\) |
| \((0,1,3,6,3)\) | \((0,1,3,6,2,5,8,4,9,12,8,17,20,16,\ldots)\) |
| \((0,1,3,6,4)\) | \((0,1,3,6,3,6,3,6,\ldots)\) |
| \((0,1,3,6,5)\) | \((0,1,3,6,4,9,7,11,9,16,14,20,18,29,27,\ldots)\) |
| \((0,1,3,6,6)\) | \((0,1,3,6,5,9,8,14,13,23,22,40,39,\ldots)\) |
| \((0,1,3,6,7)\) | \((0,1,3,6,6,6,6,\ldots)\) |
| \((0,1,3,6,8)\) | \((0,1,3,6,7,10,14,16,21,27,31,40,50,58,\ldots)\) |
| \((0,1,3,6,9)\) | \((0,1,3,6,8,12,15,21,26,36,45,63,80,\ldots)\) |
| \((0,1,3,6,10)\) | \((0,1,3,6,9,13,19,29,37,71,\ldots)\) |
| \((0,1,3,6,11)\) | \((0,1,3,6,10,15,21,28,36,45,55,\ldots)\) |
| \((0,1,3,7)\) | \((0,1,3,6,11,21,42,85,171,342,\ldots)\) |
| \((0,1,3,8)\) | \((0,1,3,7,15,31,63,127,255,\ldots)\) |
| \((0,1,3,9)\) | \((0,1,3,8,22,63,185,550,1644,\ldots)\) |
| \((0,1,4)\) | \((0,1,3,9,27,81,243,729,2187,\ldots)\) |
| \((0,1,5)\) | \((0,1,4,16,64,256,1024,4096,\ldots)\) |
| \((0,1,\textrm{Rayo}(10^{100})+1)\) | \((0,1,\textrm{Rayo}(10^{100}),\textrm{Rayo}(10^{100})^2,\textrm{Rayo}(10^{100})^3,\ldots)\) |
Sources[]
- ↑ Koteitan, Categorizing of the rule sets for all sub versions of bashicu matrix, Googology Wiki user blog, 2018.
- ↑ GoogologyBot, A tweet about N primitive versions, Twitter, 2020.
- ↑ 3.0 3.1 Nayuta Ito, Ich denke, dass dies wahrscheinlich am schnellsten ist., document in Google Spread Sheet, 2019.
- ↑ Nayuta Ito, Nayuta-Ito/N-primitive, GitHub, 2019.
See also[]
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
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
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
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
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
See also: Template:Googology in Asia