FANDOM


A program which calculates \(f_{\epsilon_0+1}(10)\) was posted at googology thread of Japanese BBS 2ch.net (anonymous author; now GWiki accout BashicuHyudora was created.).[1] Aycabta translated this program to C and Ruby.[2] This program is a simple implementation of Kirby-Paris hydra. Bashicu now calls this algorithm primitive sequence system.

BashicuHyudora also made an extended version of this program "Pair sequence system".

dim A(Infinity):B=9
for C=0 to 9
  for D=0 to B
    A(D)=D
  next
  for E=B to 0 step -1
    B=B*B
    for F=0 to E
      if A(E-F)<A(E) or A(E)=0 then G=F:F=E
    next
    for H=1 to B*G
      A(E)=A(E-G):E=E+1
    next
  next
next
print B

Linear array and ordinal

In this program, linear array A is stored in parameters A(0) to A(E). For example, when E=3, A(0)=0, A(1)=1, A(2)=2 and A(3)=3, we express this linear array as (0,1,2,3). The linear array is related to an ordinal. Ordinal \(\alpha < \epsilon_0\) is expressed with linear array as follows.

Hydra1

  1. Draw Kirby-Paris hydra of the ordinal \(\alpha\). For example, the figure represents \(\omega^{\omega^\omega+\omega^3}+\omega^{\omega^2+1}\), as explained in Kirby and Paris (1982).[3]
  2. Start from root node.
  3. Going up one node from root node is expressed as adding an entry with the value 0.
  4. Going up one node is expressed as adding an entry with "(value of the previous entry) + 1".
  5. Going down \(n\) nodes and going up one node for adjacent segment is expressed as adding an entry with "(value of the previous entry) - n + 1".
  6. Thus, the value of each entry expresses the height of the node from the root node - 1.
  7. In the figure, first going up the highest \(\omega^{\omega^\omega}\) segment is expressed as (0,1,2,3). Then going down 3 nodes and going to the adjcent segment, entries (1,2,2,2) is added. After that, the segment (0,1,2,2,1) is added. Thus, the hydra tree is expressed as a sequence of (0,1,2,3,1,2,2,2,0,1,2,2,1).
  8. We express this correspondence with the equation \(\omega^{\omega^\omega+\omega^3}+\omega^{\omega^2+1} = (0,1,2,3,1,2,2,2,0,1,2,2,1)\).

Here are examples.

\begin{eqnarray*} 1 &=& (0) \\ 2 &=& (0,0) \\ 3 &=& (0,0,0) \\ \omega &=& (0,1) \\ \omega+2 &=& (0,1,0,0) \\ \omega \cdot 2 &=& (0,1,0,1) \\ \omega^2 &=& (0,1,1) \\ \omega^2+\omega &=& (0,1,1,0,1) \\ \omega^3 &=& (0,1,1,1) \\ \omega^\omega &=& (0,1,2) \\ \omega^{\omega^\omega} &=& (0,1,2,3) \\ \omega^{\omega^{\omega^\omega}} &=& (0,1,2,3,4) \\ \omega^{\omega^{(\omega^\omega+1)}} &=& (0,1,2,3,4,2) \\ \omega^{\omega^{\omega^{\omega^\omega}}} &=& (0,1,2,3,4,5) \\ \end{eqnarray*}

Reading codes

dim A(Infinity):B=9

A is for linear array and B is for the value.

for C=0 to 9

This C loop repeats the \(B = f_{\epsilon_0}(B)\) calculation 10 times, therefore calculating \(f_{\epsilon_0+1}(10)\).

  for D=0 to B
    A(D)=D
  next

It sets ordinal \(\omega\)^^\(B=(0,1,2,3,...,B)\).

  for E=B to 0 step -1

This loop is a little tricky because the value of E changes inside the loop. E represents the position of the last entry of the sequence, and therefore it starts from B. The remaining will be explained later.

    B=B*B

At each step of cutting hydra head, B value is squared. If it is \(B=B+1\) and it is executed only for successor, it matches the Hardy hierarchy[4]. As it uses \(B=B^2\), it is slightly stronger than Hardy hierarchy.

    for F=0 to E
      if A(E-F)<A(E) or A(E)=0 then G=F:F=E
    next

It calculates G, the length of the sequence where the hydra tree is copied. For example, for (0,1,2,3), G=1, meaning that after (3) is cut, (2) is copied. For (0,1,2,3,0), G=0, meaning that the hydra head is not copied. For (0,1,2,3,1), G=4, meaning that after (1) is cut, (0,1,2,3) is copied.

    for H=1 to B*G
      A(E)=A(E-G):E=E+1
    next

When G=0, this loop is not calculated, meaning that the hydra head is not copied after cutting off. In this case, at the start of the next loop, E is decreased by one, meaning that the rightmost node was cut off.

When G>0, this loop cuts one hydra head and makes B copies of hydra heads expressed with the length G sequence. A(E)=A(E-G) is the operation of copying. It starts from A(E), meaning that the rightmost head was cut off. After copying, E=E+1 is calculated, and therefore the E is 1 larger than the position of the rightmost sequence. At the start of the next loop, E is decreased by one (STEP -1), and therefore it is cancelled.

  next
next

End of loops.

print B

Output the result.

At first, A(0) to A(9) are set as \(A(n)=n\). This sequence is expressed as (0,1,2,3,4,5,6,7,8,9), and parameter E is set as E=9, where E represents the position at the end of the sequence.

Example calculation

Example calculation for this simplified code was shown by the author of the program.[5]

dim A(Infinity):B=2
for D=0 to B
  A(D)=D
next
for E=B to 0 step -1
  for F=0 to E
    if A(E-F)<A(E) or A(E)=0 then G=F:F=E
  next
  for H=1 to B*G
    A(E)=A(E-G):E=E+1
  next
next
print B

The array is first initialized to \((0,1,2) = \omega^{\omega}\).

At the loop of F, G=1. At the loop of H, E=4 and the array becomes \((0,1,1,1) = \omega^3\).

After that, it goes to the second loop of E and E is decreased to 3 by STEP -1. Therefore, it matches the rightmost position of the sequence (0,1,1,1). In this second loop of E, the array changes to \((0,1,1,0,1,1,0,1,1) = \omega^2 \cdot 3\). After this, the ordinal will decrease as

  • \((0,1,1,0,1,1,0,1,0,1,0,1) = \omega^2 \cdot 2 + \omega \cdot 3\)
  • \((0,1,1,0,1,1,0,1,0,1,0,0,0) = \omega^2 \cdot 2+\omega \cdot 2+3\)
  • \((0,1,1,0,1,1,0,1,0,1,0,0) = \omega^2 \cdot 2+\omega \cdot 2+2\)
  • \((0,1,1,0,1,1,0,1,0,1,0) = \omega^2 \cdot 2+\omega \cdot 2+1\)
  • \((0,1,1,0,1,1,0,1,0,1) = \omega^2 \cdot 2+\omega \cdot 2\)
  • From here, not showing all the process.
  • \((0,1,1,0,1,1,0,1) = \omega^2 \cdot 2+\omega\)
  • \((0,1,1,0,1,1) = \omega^2 \cdot 2\)
  • \((0,1,1,0,1,0,1,0,1) = \omega^2+\omega \cdot 3\)
  • \((0,1,1,0,1,0,1) = \omega^2+\omega \cdot 2\)
  • \((0,1,1,0,1) = \omega^2+\omega\)
  • \((0,1,1) = \omega^2\)
  • \((0,1,0,1,0,1) = \omega \cdot 3\)
  • \((0,1,0,1) = \omega \cdot 2\)
  • \((0,1) = \omega\)
  • \((0,0,0) = 3\)
  • \((0,0) = 2\)
  • \((0) = 1\)

Sources

  1. BASIC program of \(\epsilon_0\) level
  2. Translation of the program to C and Ruby
  3. Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic"
  4. Modified C code to calculate Hardy hierarchy and result.
  5. Example calculation posted at 2ch.net

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.