FANDOM


Here come two sets of fundamental sequences (FS) on Taranovsky's ordinal notation. One is for ideal use, and the other is for reality use.

Ideal use - FS in Bignum Bakeoff

Here's a code to calculate fast-growing function based on Taranovsky's notation. This code is used for Bignum Bakeoff.


#define E return
#define R r(x)
#define L l(x)
#define B ,y,n,d)
#define G g(
L
    E x%2 ? 0 : 1+l(x/2) ;
R
    E x >> 1+L ;
G x,y)
    E x-1 &&(
        y-1 ? y-2 ? x-2 ? G R,r(y)) || R==r(y)&&G L,l(y))
                        : G x,r(y))
                  : x-2 && !G y,R)
            :1);
b(x B
   E G x,y) ? x-2 ? G d,x) ? b(L B * b(R B
                           : n && b(L,y,n-1,x) * b(R,y,n-1,x)
                  : n + G d,x)
            :1;
t(x,n)
    E x<3||
        t(L,n) *
        t(R,n) *
        (R<3 || !G L,l(R))) *
        b(L,R,n,1);
s(x)
    E x%2 ? x<3 : x==2 || s(L) * s(R) ;
f(x,n,k){
    int m=1;
    while(--k)
        if(s(k) * t(k,n) * G x,k) * G k,m)) m=k;
    E m;
}
#define X x,2,
c(x,p,z,o B
    E p-1? c(o-1? c(X x,f(o,y,x) B
                :n-1? c(X X x,f(n,d,x),d)
                    :x*x
            ,f(p,z,x),z,o B
         :x;
a(x)
    E x? c(X X X a(x-1)) :1;
main()
    E a(a(a(a(9))));

Here're some explanation. As we all know, ordinals in Taranovsky's notation are made up from two constants: \(0,\Omega_n\), and a binary function C. In that code, ordinals are coded to integers.

  • 0 is coded to 1.
  • \(\Omega_n\) is coded to 2.
  • \(C(\alpha,\beta)\) is coded to \(2^a\times(2b+1)\), where \(\alpha\) and \(\beta\) are coded to a and b respectively.

So l(x) give the left component of x, and r(x) give the right component of x. This trick is similar to Loader's one. Function g(x,y) compare two ordinals, and it returns true iff x > y. b is for built-from-below, and it's identical to Taranovsky's original one. t judges an ordinal in standard form or not. However, not all positive integers can be decoded to ordinals, so we need function s.

And function f is for FS. Here, the definition of FS on Taranovsky's notation is:

\(\alpha[k]\) is the largest ordinal \(\beta\) such that \(\beta<\alpha\) in and \(\beta\) is coded to a number smaller than \(k\).

This definition is irregular, e.g. C(C(0,0),0)[k] = 0 for k = 0 ~ 6, C(C(0,0),0)[k] = C(0,0) for k = 7 ~ 26, C(C(0,0),0)[k] = C(0,C(0,0)) for k = 27 ~ 106, C(C(0,0),0)[107] = C(0,C(0,C(0,0))), etc. . And we surely can't use this to evaluate FS in reality. For example, we may need a program to evaluate FS, and use it for analysis of Taranovsky's notation. Due to the long calculating time of FS, we must think about a new way.

Reality use

To make analysis of Taranovsky's notation, we need a FS such that \(\alpha[n]\) has some periodic patterns for n, e.g. the FS of C(C(0,0),0) is C(0,0), C(0,C(0,0)), C(0,C(0,C(0,0))), etc. So we need this definition:

  • Let \(L(\alpha)\) be the amount of C's in standard representation of \(\alpha\).
  • \(\alpha[k]=\max\{\beta|\beta<\alpha\land L(\beta)=L(\alpha)+k\}\)

In this definition, C(C(0,0),0)[0] = C(0,C(0,0)) and C(C(0,0),0)[k+1] = C(0,C(C(0,0),0)[k]).

Here's a thought for the computing of FS. For limit ordinal \(\alpha\), let \(\beta\) be a copy of it, then

  1. Let \(\beta_1,\beta_2\cdots,\beta_m\) and \(\gamma\) be such that \(\beta=C(\cdots C(C(\gamma,\beta_1),\beta_2)\cdots,\beta_m)\), where \(\gamma=0\) or \(\Omega_n\).
  2. If \(\gamma=\Omega_n\), then change it into \(0\). If \(\gamma=0\) and \(m=1\), then change the \(C(0,\beta_1)\) into \(\beta_1\), and go back to step 1. If \(\gamma=0\) and \(m\ge2\), then change the \(C(C(0,\beta_1),\beta_2)\) into \(C(\Omega_n,C(\beta_1,\beta_2))\). Now the \(\beta\) is changed.
  3. Do step 4 and 5 until \(L(\beta)=L(\alpha)+k\).
  4. Let \(\beta_1,\beta_2\cdots,\beta_m\) and \(\gamma\) be such that \(\beta=C(\cdots C(C(\gamma,\beta_1),\beta_2)\cdots,\beta_m)\), where \(\gamma=0\) or \(\Omega_n\).
  5. Change the \(\gamma\) into \(C(\Omega_n,\gamma)\).
  6. Now, if \(\beta\) is in standard form, then \(\alpha[k]=\beta\); if not, go back to step 1.

This can give us FS with the "reality" definition. However, it runs in a very slow speed. For example, when k increases 1 it takes about 8 times as before.

Here's a theorem, and it can help reducing the calculating time a lot:

If \(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_m)\) is in standard form (where \(\alpha\) is 0 or \(\Omega_n\)), then \(C(\cdots C(\beta_1,\beta_2)\cdots,\beta_m)\) is also in standard form.

To proof it, we need a lemma.

Lemma: \(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_m)>C(\cdots C(\beta_1,\beta_2)\cdots,\beta_m)\), where \(\alpha\) is 0 or \(\Omega_n\).

Proof: Let the postfix form of ordinal \(\beta\) be \(\overline{\beta}\).

The postfix form of \(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_m)\) is \(\overline{\beta_m}\overline{\beta_{m-1}}\cdots\overline{\beta_1}\overline{\alpha}CC\cdots C\), and the postfix form of \(C(\cdots C(\beta_1,\beta_2)\cdots,\beta_m)\) is \(\overline{\beta_m}\overline{\beta_{m-1}}\cdots\overline{\beta_1}CC\cdots C\). \(\overline{\alpha}\) is 0 or \(\Omega\), so it's larger than C. So \(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_m)>C(\cdots C(\beta_1,\beta_2)\cdots,\beta_m)\).

Main proof: Suppose \(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_m)\) is in standard form.

If \(\beta_m=C(\gamma,\delta)\), then \(\gamma\ge C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_{m-1})>C(\cdots C(\beta_1,\beta_2)\cdots,\beta_{m-1})\).

\(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_{m-1})\) is n-built from below \(\beta_m\).

If m=1, then \(C(\cdots C(\beta_1,\beta_2)\cdots,\beta_m)=\beta_m\) is standard.

For m>1, let f be a map from subtrees of \(C(\cdots C(\beta_1,\beta_2)\cdots,\beta_{m-1})\) to subtrees of \(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_{m-1})\). If \(\gamma\) is a subtree in \(\beta_i\) in \(C(\cdots C(\beta_1,\beta_2)\cdots,\beta_{m-1})\), then \(f(\gamma)\) is the same subtree in \(\beta_i\) in \(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_{m-1})\). If \(\gamma=C(\cdots C(\beta_1,\beta_2)\cdots,\beta_i)\), then \(f(\gamma)=C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_i)\).

f is an injection. Let \(g(\gamma)\) be such a subtree \(\delta\) of \(C(\cdots C(\beta_1,\beta_2)\cdots,\beta_{m-1})\) that \(f(\delta)=\gamma\).

For any subtree \(\gamma\) of \(C(\cdots C(\beta_1,\beta_2)\cdots,\beta_{m-1})\), consider \(f(\gamma)\). \(f(\gamma)\) is a subtree of \(C(\cdots C(C(\alpha,\beta_1),\beta_2)\cdots,\beta_{m-1})\), and there're 2 conditions:

-

Based on the theorem, the step 3 changes into "If \(L(\beta)<L(\alpha)+k\) and \(\beta\) is in standard form, do step 4 and 5". Here's a code in Mathematica, which use the modified method to calculate FS of Taranovsky's notation.

Uncompress@"1:eJzdWs1v3DYWt51kk0232La33rinxog6sMeHNgZ6sJ26LZB4k4wXPiQ+0BLHQ1gjTiQqM0bR/7l/Qdv3SIkiKWpGE0+wQAuEY0mP7/P3PkT1P1fizXhna2ur+AqWEzGdiTJLflzMclYUXGTjbXz2AJbXJWdy/OUSUsXmMSwjJp+zlN6yRN97BEsM9BQo9Z2HsLyiUrI8K/AG3R9v1YKOU5rddJANfbJ/1ZcXEx5P9C68/PF9SdOKdbWV41ZNcQ+WoywJk2sR92F5wQvZKPK/jDVUQ5eK/wn/BXi39gW5exr4vLeN3uoWeLuJyinPC1mzDt0dWqqhNj/ljII/1+KwXcs+z0sWCKl5/oZ5rNybwyBEFOE/kbt4JcAlfNEOPtIs/NijpxXjX8aNH0d0yl43wn9mNNG71RrrJ8j6NEXemeZi4tGlzH2lTC41L+3TnrS4WjF8rFwyS2nMjtK00RTFV3bubLUgohxZpkyBmO84iMD7aucFv+eI8fPwYRO0DaehVyU6IOL4ysFJ4MmwSSewQ9lTTEQuJzRLilAWdVk84tNZCojvB6ogVRak8iKp7v27uQc/mGrJWsSVUg+6EaCv0GEnIku4NJVX4zsYsJj2imt8FSRzKhoW3KqGqJLVgSylTCW74l1dWWUYjcByFmbk7ra2qfxKy6LW2eT+KzFnefEP+Ovd4d7BybPa9r+r/0zfWOW7bWfLGm4KkqtSo9e+e3TZchvZ0mCEmHziMHV7c2VImhYbIAoV6sbuUXlVxDmfSWPo0bOq5qwN2y5+Pb1lIcuaFGobm+AtF+Nmp/aNX71D9fqeYV3TdVXsbUdrpcDodnol0vCG1aDQ7vbYIsEvmWTX0DrQpqVTb92lmkmDNk3waDZjWXIugl5w42v1K83F1u2xMfQMhhx977MtNWB+oGlptY9lnVNt+wIWcDyT7Hk5S3kMewuPUGl2Vta96nPN7UjKnF+VSO7ESl39LNJEDY5NeztJGc2tTQYdSP/fPGF5ivNsCBDK6Rjc45Kn8vVdghtO+H5d3qdKfKrH9aX1CrKiszWh1X3NG67NHGsRViVjR7kt3Eq0EV6xX6lBYlWvtTfUrc2PlfceYdmrlaw8Gdymxh66ZJeramW1Ccop3GKeQ9dX06tlWoYqZRp1vTVfxaizFP7/kV8VEF+ddlx8b7QprNYSGtNVKZFQRmie3MncsCGo2UuRYJV1X7fQMnw7ab1J1rWzRVDnnpei3lDWTt77NgwDNnciMeukDqAtW6JoaFNI7U7mF30HWNeWEL+guVoZH/shyiX2O8Bte86mrYNrghyC53atTvyczeTkU55MOIWiJTjgh+pooTO1jBbj9U7dAkNm4ARgybgUHCGdA7g+Ig5Wimg1QL3PkmNlvnvO08rylE9DEdCNnI5PYOozR1smpOd8ygpuGjM9UHHhLne8mAln76qzVpgkQOMHfUhf0CuWWj3fnkS5j6JKlzA+m27KvaPSxgorR8PwNl4+w1M/9yQRnGBxf1irNppzGU+qR40hfcbtyhy3HPg3fxJS6EzZ6bDKfnWzKp1OS4d56IC0S4FQaoXk4ghfnQKpU0P7mft28LnOmgKqmTzKc3rrvVGbCYPzP7w30hVmLQ9bUEJzBHoXLn84o6Qp2uYI1d6KDOFdKr1Vb1Uj9r5kWbzUNS00N8nlzIVGZnO43k58gK9TKNzGYmf5sD+Cl6bpJ/ZLGx99slcri5RnIthiHU84inb1p9PROjPfit6h54B1upM/ofYQ0DqEWN2bdMdWUky4T0RaTm0ROcOjAqvB0Kt6aEVvvRHzUB/zcgrXEQb+Wzkh8JI/ZZk8JK0DBns+cOYixcWeJ53PEzqdbC/Umj20aUcY7PMJI2NEEAkoqseX0S4stZYFEWMicROkDMU7NCVFBWh8tvSUZIQuJTwj2Q/Vja/xRnFbSDYlMJmSFBRjCYGOKeaHf3tMtocd55unLhnObbx4SWeqjlSqvbaPlFZsw052JrIzdk0l/8BsrXy0d4D7kQOh+zWE3MHMrYTNCF0h/6mL/A1D6jMLUrzon1XdWvvPm0xrXPeCZddyUjn0kYl+LiSLpfOlzfuUZh/h2DZ6zWZcVKAPncC2jv70kZfR9SPFV2cFbvNYRy+jACr4Bl6nKn+wRPtMxDcsGf3+CEEEoZrl4jqnKmplAVVAClJMxLwTHKoYiTzhGVRvxMA5zWkmPhQ3t98U9QOSCUkxJwfv9vaH54LQD4InJIYkLbHb476XFERMgSqmEZkzlE7it3hmfrwfqZ/hJdABpGiCMk+eOM92kUdxC7otlJCjtBA1mwt737vD0+9O9tX6TK3fm1P6Y7F4Wz/Ao3r1916ktzzL9OWl/hmQkQAd9iLUYyMco73dXZIKcVNABb5B4/ei+O1FtHd5SSYsZ8os/NdMScRAonZUdkkkTiVkPmHgz1zFjTUbNJnKVcz+JkXRexUzMhb5FEKHURv4AjU0LXHXWMOUmAKf8TFnNYdxWJzPc1wYdtHCZvhk8XR/d40iFZZGsDiKUs5KiYbOc47/R0PL4IjABeGSxDSD3qcE8Qw3AWfj56j2gCYHpCsvjwt1eTrybTsdddimGz4Y2Lurd1hnS/i1FxQXLgr3XRR+DIvh3VkcuCwGg8FvDhTubpnGUvRxrIabY3UQYEXA3l5AGJBjQBwBeJUpUOK4ZgPazUCNUWB1i6D+Rm4O1qbHvF1ETSlIGSAahVBivpChIisLUITlCkypHwbK0RNQybJvdwCSgA4kqW99EYGei/VeG4pVX04ErCD424SNeQY+0aSHpO61Uf1XREwztjyhW29ke0k33QgcE4FXosZMuDY+AbKIXEREf4/Xv0fwi40tvjJl/DxQMsGiQvI0JXOOzhFTNEDAADiFYjwfbKp5QdWZ8uuJJAkvZjDSE1qQ/aeb6mMKMxtiNmwrOtxUB/8LkiiRLQ=="

And I'll continue to work on Taranovsky's notation analysis use this FS calculator.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.