Googology Wiki
Register
Advertisement
Googology Wiki

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 b(y,z,n,
#define N n)
L
 E x%2 ? 0 : 1+l(x/2) ;
R
 E x >> 1+L ;
g(x,y,N
 E x-1 &&(
  y-1 ?
   y-n ?
    x-n ?
     g(R,r(y),N||R==r(y)&&g(L,l(y),N:
     g(x,r(y),N:
    x-n && !g(y,R,N:
   1);
B x)
 E n-1 ?
  b(x,z,n-2,x)+
   !g(x,y,N*
   (x&1 || B L) * B R))
 :g(z,y,N;
t(x,N
 E x&1 || x &&
  t(L,N *
  t(R,N *
  (R&1 || !g(L,l(R),N ) *
  b(L,x,n,L);
s(x,N
 E x&1 ? x-1 ? x < n ? 3<<x+2 : n : 1 : s(R,N *2+1 << s(L,N;
q(x)
 E x&1 ? x : q(L) > q(R) ?q(L):q(R) ;
f(x,N {
 int m=1;
 while(--N
  if(t(s(n,q(N ),q(N ) && g(x,N * g(n,m)) m=n;
 E m;
}
a(x,y,z,N
 E z-1 ? a(x,y,f(z,N ,
  y-1 ? a(x,f(y,N ,n,N : x-1 ? a(f(x,N ,n,n,N : n*N
 :n;
main()
 E a(99,9,9,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 2n+1.
  • \(C(\alpha,\beta)\) is coded to \(2^a\times(2b+1)\) (so it should be an even number), 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,n) compare two ordinals, and it returns true iff x > y. b is for built-from-below, where b(y,z,2n+1,x) works in nth system. t(x,2n+1) judges x in standard form or not in nth system. s(x,2n+1) turns ordinals x in "combined system" into nth system. And q give the highest system index (2n+1 for nth system) of an expression.

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[k]\) has some periodic patterns for k, 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:

In the nth system, given a standard term \(\alpha\) (in prefix form), every nonempty suffix of \(\alpha\) augmented with the corresponding number of "C" on the left is standard.

which can be found on Taranovsky's original page.

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.

Advertisement