(C) FGH up to phi(w,0)

Hey guys!

I made this C program for the fast-growing hiearchy. It needs some explanations:

"ORD" structures aren't really ordinals (they aren't sets at all), but in theory f(ord,n) would solve exactly like f_ord(n) in the real FGH (i.e. give the same results)

The functions of the form f(DECL_ORD(OMEGA,k,0),n) would correspond to f_φ(k-4,0)(n), and f(DECL_ORD(OMEGA,n,0),n) would therefore pretty much be f_φ(ω,0)(n-4)

ORD structures have the following members:

• p, another ordinal (e.g. in "ω+4", p is the structure "representing" ω). If it is "NULL", the ordinal is finite (e.g. 0,1,2,3,...)
• k, the "operation": letting o be the ORD object (of wich k is a member)
  • if k=0, o represents "p" (identity)
  • if k=1, o represents "p+n" (addition)
  • if k=2, o represents "p*n"
  • if k=3, o represents "p^n"
  • if k=4, o represents "p^^n"
  • and so on.
• n, the number used as above. Howerver, if n=0, o "represents" the limit of DECL_ORD(p,k,x) for finite x

To "create" an ORD structure, use DECL_ORD(p,k,n)

The interesting part is "ord_get_fs(o,m)", equivalent of o[m]. It works as the following: (using {p,k,n} to represent members of o)

• If o is finite (i.e. o = {NULL,k,n}), it doesn't do anything.
• If o has the form {p,0,n}, it returns p (k=0 is pretty much identity, as I said)
• If o has the form {p,k,0}, it returns [p,k,m] (={p,k+1,2}[m])
• If o has the form {p,k,1}, it returns p (excepted for k=1, for which is doesn't do anything, since it's successor case and p+1>p)
• Otherwise, it returns {{p,k,n-1},k-1,m}

That's how o[m] is encoded!

If you have any remark/question or spot any error/mistake, say me! :D

typedef struct ORD {
        struct ORD *p;
        int k;
        int n; /* if n=0, o is limit of all ORD's with finite n */
} ORD;

#define DECL_ORD(p_,k_,n_) ({ORD o_;o_.p=p_;o_.k=k_;o_.n=n_;&o_;})

#define ORD_PLUS_N(o,n) DECL_ORD(o,1,n)
#define ORD_TIMES_N(o,n) DECL_ORD(o,2,n)
#define ORD_POWER_N(o,n) DECL_ORD(o,3,n)
#define ORD_TETRATED_TO_N(o,n) DECL_ORD(o,4,n)

#define OMEGA DECL_ORD(NULL,1,0)
#define OMEGA_PLUS_ONE DECL_ORD(OMEGA,1,2)
#define OMEGA_TIMES_TWO DECL_ORD(OMEGA,2,2) /* NOT DECL_ORD(OMEGA,1,0)! */
#define OMEGA_TIMES_THREE DECL_ORD(OMEGA,2,2)
#define OMEGA_SQUARED DECL_ORD(OMEGA,3,2) /* = DECL_ORD(OMEGA,2,0) */
#define OMEGA_CUBED DECL_ORD(OMEGA,3,2)
#define OMEGA_POWER_OMEGA DECL_ORD(OMEGA,4,2) /* = DECL_ORD(OMEGA,3,0) */
#define EPSILON_ZERO DECL_ORD(OMEGA,5,2) /* = DECL_ORD(OMEGA,4,0)*/
#define VEBLEN(n) DECL_ORD(OMEGA,n+4,2) /* defined until phi(omega,0) */

#define ord_is_finite(o) (!o->p)
#define ord_is_zero(o) (ord_is_finite(o)&&o->k==0&&o->n==0)
#define ord_is_successor(o) (o->k==1||(ord_is_finite(o)&&o->k==0&&!ord_is_zero(o)))
#define ord_is_omega(o) (!o->p&&o->k==1&&!o->p) // omega is (NULL,1,0)
#define ord_dec(o) (!ord_is_successor(o)?(o->n>1?(o->n--&&1?o:o):o):o)

/* the hard part :V */
#define ord_get_fs(o,m) \
({ORD *r;if(!ord_is_finite(o)&&o->k>0){\
        if(o->n==0){if(!ord_is_omega(o)){o->n=m;r=o;}else{r=o}}\
        if(o->n==1){if(k>1){r=o->p;}else{r=o}}\
        else if(o->n==2){o->k--;o->n=m;r=o;}\
        else{if(k==0){r=p;}\
             if(k==1){r=o;}\
             else{o->n--;r=DECL_ORD(o,o->k-1,m);}\
        }else{r=(!ord_is_finite(o)&&!ord_is_omega(o)?ord_get_fs(o,m):o);}(r);})

int _fast_growing_hiearchy(ORD o, int r, int n)
{
        assert(n > 0);

        if (ord_is_zero(o)) {
                return n + r;
        }

        if (r > 1 || ord_is_successor(o)) {
                if (r > 1) {
                        return _fast_growing_hiearchy(o, r - 1, _fast_growing_hiearchy(ord_dec(o), 1, n))
                }
                return _fast_growing_hiearchy(ord_dec(o), n, n);
        }
        if (ord_is_omega(o)) {
                return _fast_growing_hiearchy(n, 1, n)
        }
        return _fast_growing_hiearchy(ord_get_fs(o, n), 1, n)
}

int fast_growing_hiearchy(ORD o, int n)
{
        return _fast_growing_hiearchy(o, 1, n);
}