### arnold beckmann's pages

## Characterizing the elementary recursive functions by a
fragment of Gödel's T

**File:** PDF-File

**Author:** Arnold Beckmann and Andreas Weiermann

**Title:** Characterizing the elementary recursive functions by a
fragment of Gödel's T

**Journal:** Arch. Math. Logic 2000, **39**: 475-91

**DOI:** 10.1007/s001530050160

**Abstract:**
We use a modified Howard-Schütte-function
[ ]_{0}
which assigns finite ordinals to each
term from
T^{pred}
and which witnesses the strong normalization for
T^{pred}
. Furthermore the derivation lengths
function for
T^{pred}
is elementary recursive,
hence representable functions in
T^{pred}
are
computable in elementary time, hence are elementary recursive. On the
other hand it is shown that random-access machine transitions can be
simulated in simple typed combinatorial calculus with combinators for
the case distinction function and for the predecessor function, hence
T^{pred}
represents any elementary recursive
function.