[cpsjxejd] Implementing Goodstein

The Goodstein function is one of the fastest growing computable functions.  As best as I can tell, it grows faster than the Ackermann function and faster than Conway's chained arrow notation.  It is fairly straightforward to implement -- implementation is where the rubber meets the road when a function claims to be computable: source code in Haskell here.

Some excerpts of code, first demonstrating converting to and from Hereditary Base notation:

-- curiously, these Terms may be reordered, i.e., commutative, which is different from normal base N notation which is place value.
type HerditaryBase = [Term];

-- value is Integer * base ^ HerditaryBase. base is given exogenously.
data Term = Term Integer HerditaryBase deriving Show;

-- wrap Base in newtype to defend against accidentally mixing it up with a coefficient
newtype Base = Base Integer deriving (Show, Enum); -- Enum needed for succ

-- output is little-endian
int_to_hb :: Base -> Integer -> HerditaryBase;
int_to_hb base x = zipWith Term (radix_convert base x) (map (int_to_hb base) [0..]);
-- [0..] are the list of exponents

hb_to_int :: Base -> HerditaryBase -> Integer;
hb_to_int base = map (term_to_int base) >>> sum;

term_to_int :: Base -> Term -> Integer;
term_to_int _ (Term 0 _) = 0; -- optimization
term_to_int (Base base) (Term k x) = k * base ^ (hb_to_int (Base base) x);

-- input must be zero or positive. output is little-endian.
radix_convert :: Base -> Integer -> [Integer];
radix_convert (Base base) = unfoldr $ \n -> if n==0 then Nothing else Just $ swap $ divMod n base;

-- Compute the next value in a Goodstein sequence
goodstein_tuple :: (Base, Integer) -> (Base, Integer);
goodstein_tuple (base, x) = (succ base , int_to_hb base x & hb_to_int (succ base) & subtract 1);

goodstein_sequence_from :: (Base, Integer) -> [Integer];
goodstein_sequence_from = iterate goodstein_tuple >>> map snd >>> takeWhile (>=0);

goodstein_sequence :: Integer -> [Integer];
goodstein_sequence x = (Base 2,x) & goodstein_sequence_from;

goodstein :: Integer -> Integer;
goodstein = goodstein_sequence >>> genericLength;

goodstein {0, 1, 2, 3} will complete within a reasonable amount of time.  4 and larger are huge so will not terminate within a reasonable amount of time.  (This unfortunately limits the testcases available for testing whether the implementation is correct.) The full source code also demonstrates computing the first 6 steps in hereditary base notation of the evaluation of goodstein 19 (Comparing with Wikipedia).

Harvey Friedman's tree and subcubic graph numbers supposedly grow faster, but they are difficult to understand, difficult to understand that they are computable, and consequently difficult to implement.