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 Tpred and which witnesses the strong normalization for Tpred . Furthermore the derivation lengths function for Tpred is elementary recursive, hence representable functions in Tpred 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 Tpred represents any elementary recursive function.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!