Arnold Beckmann and Andreas Weiermann
Archive for Mathematical Logic, Volume 39, Issue 7, Pages 475-491.
Publication year: 2000

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 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.

Leave a Reply

Your email address will not be published. Required fields are marked *