Explanation:
^^^^^^^^^^^^

All numbers handled by my functions are non-negative.
The type used is "int" (typedef name J).

I have not even used any preprocessor tricks to shorten the code,
since I expect my entry to be already uncomparable to any other
entry not using a nearly identical function scema.

Overview:
^^^^^^^^^
- G(x) implements a (slightly modified) Goodstein sequence, and returns
  the resulting "base".
- f(n,x) uses an Ackermann-like recursion scema to iterate G(G(G(....G(y)...)))
  very often (for some y).
- h(n,x) does the same construction on F(x,x) instead of G(x).
- h() on nonzero arguments is huge.
  Even h(0,0) would already yield G(0), which in the modified version
  is already so large that I know of no other way to express that number.

main() calls h() on non-trivial arguments.


Details:
^^^^^^^^

P(x,y)	codes a pair of numbers into one number, by mixing bits
	alternatingly from x and y.
	Repeated use of pair construction is used to code lists
	of pairs of numbers, where the components of the elements (pairs)
	never both are zero.  Thus, 0 is a unique coding for an
	empty list.

H(z)	extracts the head of the list coded by z.
	H(z/2) is the corresponding tail function,
	expanded inline.

G(x)	computes a modified Goodstein sequence.
	The unmodified function would read:
	    J G(J x)        { return F(M(x,0), 2) ;}
	From x is built a list of pairs (factor, exponent),
	where the exponent is to base 2, and is itself coded this way.

	Exponents in such a list are always sorted increasingly.
	Factors are plain numbers and always smaller than the current base.

	It is proven that this sequence does converge, albeit
	transfinite induction is necessary to prove this.  See e.g.
	    Newsgroups: sci.math
	    Date: 11 Dec 95 02:34:50
	    Subject: Re: Goedel's theorem: about anything in real world?
	    Message-ID: <WGD.95Dec11023450@martigny.ai.mit.edu>

M(x,e)	codes x*pow(2,e) as expression list for base 2.

F(x,b)	performs the Goodstein iteration:
	while(x) { ++b; x = decr_term(x,b); } return b;

D(x,b)	is the decr_term() function of the Goodstein sequence.
	x is the (coded) list, b is the current base.

E(f,e,r,b)
	is just D with x decomposed into the first pair (f,e)
	(factor, exponent), where the factor f is non-zero.

I(f,e,r)
	constructs a term (list) from the factor f (int) and the exponent e
	(list) and the remaining list r.  If f is nonzero, the pair (f,e)
	is inserted before the list r.

f(n,x)	is an Ackermann-like construction, used to apply G very often on
	its own result:
	    f(0,x)	= G(x)
	    f(n,0)	= f(n-1, G(n))		(n>0)
	    f(n,x)	= f(n-1, G(f(n,x-1))	(n>0, x>0)
	A recursive call of f(n,x) never uses/produces negative arguments,
	and either
	- the first argument is decremented, or
	- the first argument is equal, and the second argument is decremented.
	That way the recursion must terminate, the same way as the Ackermann
	function does terminate.
	[ Proof by induction over n, and for each n over x. ]
	Where a recursive call decrements the first argument, an additional
	call to G() much increases the second argument.

g(x)	just constructs a single values function from f.

h(n,x)	does to g() what f(n,x) does to G().

Finally, main() calls h() with non-trivial arguments.

The initial construction of the Goodstein list can easily be modified to
yield much larger values, but I wanted to stay near the original.


According to my counting, this program consists of exactly 512
non-white-space characters.

-- 
Heiner Marxen	heiner@insel.de		http://www.drb.insel.de/~heiner/