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:
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/