What's the expressive power of Simply Typed Lambda calculus?

Question

The standard approach to simply typed lambda calculus considers computations over Church numerals. If input and outputs are Church numerals always typed as $Int$, where $Int = (\tau \rightarrow \tau) \rightarrow \tau \rightarrow \tau $, a result of Schwichtenberg showed that expressible functions are the extended polynomials.

If inputs are Church numerals given more complex types than $Int$, exponentiation and predecessor can be expressed (however Statman showed that equality, ordering and subtraction are not expressibile for any typing of church numerals.

However we should be more permissive and provide only an output restriction: a boolean type ( $Bool = \tau \rightarrow \tau \rightarrow \tau $). Under this convention, Statman's theorem that "deciding equivalence of normal forms of two simply typed lambda-terms is not elementary recursive" can be seen as an expressibility result (right?): we can express nonelementary functions.

Pushing to the limit, where we can arrive? Of course (by strong normalization) we can express only total functions. But I'm asking if there is a precise upper bound to simply typed lambda calculus expressive power.

I've found many articles, in particular "On the expressive power of simply typed and let-polymorphic lambda calculi" but I'm not able to understand if it is what I'm looking for.

Answer 1

As explained by Damiano Mazza here on MathOverflow (see also this TCS.SE question), for a very natural choice of encodings of input strings and output booleans, one gets exactly the regular languages! This is in fact a theorem in Hillebrand and Kanellakis's paper "On the expressive power…" that you mention (though your link seems dead).

By changing the input/output representation, one can get different things. For instance, the following paper shows that, when a certain input encoding inspired by relational databases is used, the simply typed λ-calculus can express exactly the elementary recursive predicates: https://www.sciencedirect.com/science/article/pii/S0890540196900553

In fact this implies Statman's result that convertibility is non-elementary: if it were, it would be decidable in time bounded by a tower of exponentials of fixed height, but the fact that all elementary recursive functions are representable makes this impossible. So Statman's theorem hints at an expressibility property, but not in the way you're saying; to the contrary, morally, reasonable encodings cannot yield anything beyond elementary recursive.

More precisely, let the order of a type be defined as the nesting depth of → to the left ($ord(o) = 0$ and $ord(A \to B) = max(ord(A)+1, ord(B))$) and the level of a term be the greatest order of the type of one of its subterms. Then for terms of level at most k, normalization is in O(k)-EXPTIME (*). So if you consider input/output encodings such that the order of terms may depend on the function being represented, but not on the input, then all the functions you can represent are elementary recursive (i.e. in the union of the k-EXPTIME classes over all k). This condition seems to be satisfied by practically all typable encoding schemes that one could naturally come up with.

(*) see for instance https://www.beckmann.pro/PaperFiles/lambda.pdf or https://www.kurims.kyoto-u.ac.jp/~terui/nbi8.pdf

(Let me mention that I've tried to clarify some of these points concerning the expressive power of STLC in the introduction to my PhD thesis (sections 1.1.6, 1.3.5 and 1.3.6) though in retrospect I suspect the attempt is a failure…)