Advertisement
NaZaRa

Fast-Growing Hiearchy up to φ(ω,0)

Aug 12th, 2015
305
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.33 KB | None | 0 0
  1. typedef struct ORD {
  2.         struct ORD *p;
  3.         int k;
  4.         int n; /* if n=0, o is limit of all ORD's with finite n */
  5. } ORD;
  6.  
  7. #define DECL_ORD(p_,k_,n_) ({ORD o_;o_.p=p_;o_.k=k_;o_.n=n_;&o_;})
  8.  
  9. #define ORD_PLUS_N(o,n) DECL_ORD(o,1,n)
  10. #define ORD_TIMES_N(o,n) DECL_ORD(o,2,n)
  11. #define ORD_POWER_N(o,n) DECL_ORD(o,3,n)
  12. #define ORD_TETRATED_TO_N(o,n) DECL_ORD(o,4,n)
  13.  
  14. #define OMEGA DECL_ORD(NULL,1,0)
  15. #define OMEGA_PLUS_ONE DECL_ORD(OMEGA,1,2)
  16. #define OMEGA_TIMES_TWO DECL_ORD(OMEGA,2,2) /* NOT DECL_ORD(OMEGA,1,0)! */
  17. #define OMEGA_TIMES_THREE DECL_ORD(OMEGA,2,2)
  18. #define OMEGA_SQUARED DECL_ORD(OMEGA,3,2) /* = DECL_ORD(OMEGA,2,0) */
  19. #define OMEGA_CUBED DECL_ORD(OMEGA,3,2)
  20. #define OMEGA_POWER_OMEGA DECL_ORD(OMEGA,4,2) /* = DECL_ORD(OMEGA,3,0) */
  21. #define EPSILON_ZERO DECL_ORD(OMEGA,5,2) /* = DECL_ORD(OMEGA,4,0)*/
  22. #define VEBLEN(n) DECL_ORD(OMEGA,n+4,2) /* defined until phi(omega,0) */
  23.  
  24. #define ord_is_finite(o) (!o->p)
  25. #define ord_is_zero(o) (ord_is_finite(o)&&o->k==0&&o->n==0)
  26. #define ord_is_successor(o) (o->k==1||(ord_is_finite(o)&&o->k==0&&!ord_is_zero(o)))
  27. #define ord_is_omega(o) (!o->p&&o->k==1&&!o->p) // omega is (NULL,1,0)
  28. #define ord_dec(o) (!ord_is_successor(o)?(o->n>1?(o->n--&&1?o:o):o):o)
  29.  
  30. /* the hard part :V */
  31. #define ord_get_fs(o,m) \
  32. ({ORD *r;if(!ord_is_finite(o)&&o->k>0){\
  33.         if(o->n==0){if(!ord_is_omega(o)){o->n=m;r=o;}else{r=o}}\
  34.         if(o->n==1){if(k>1){r=o->p;}else{r=o}}\
  35.         else if(o->n==2){o->k--;o->n=m;r=o;}\
  36.         else{if(k==0){r=p;}\
  37.              if(k==1){r=o;}\
  38.              else{o->n--;r=DECL_ORD(o,o->k-1,m);}\
  39.         }else{r=(!ord_is_finite(o)&&!ord_is_omega(o)?ord_get_fs(o,m):o);}(r);})
  40.  
  41. int _fast_growing_hiearchy(ORD o, int r, int n)
  42. {
  43.         assert(n > 0);
  44.  
  45.         if (ord_is_zero(o)) {
  46.                 return n + r;
  47.         }
  48.  
  49.         if (r > 1 || ord_is_successor(o)) {
  50.                 if (r > 1) {
  51.                         return _fast_growing_hiearchy(o, r - 1, _fast_growing_hiearchy(ord_dec(o), 1, n))
  52.                 }
  53.                 return _fast_growing_hiearchy(ord_dec(o), n, n);
  54.         }
  55.         if (ord_is_omega(o)) {
  56.                 return _fast_growing_hiearchy(n, 1, n)
  57.         }
  58.         return _fast_growing_hiearchy(ord_get_fs(o, n), 1, n)
  59. }
  60.  
  61. int fast_growing_hiearchy(ORD o, int n)
  62. {
  63.         return _fast_growing_hiearchy(o, 1, n);
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement