23
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ A base type is never equal to a function type (a mistake appearing twice in this question). I think you're trying to say that the final output of a function type is a particular base type, which is different. $\endgroup$ Jul 28, 2012 at 19:52
  • 1
    $\begingroup$ @HuckBennett: That is false. The encoding for the type of Church numerals in the simply typed lambda calculus is (A -> A) -> A -> A where the numerals are defined as usual. Likewise the type of the booleans is indeed A -> A -> A where true = \x . \y . x and false = \x . \y . y. $\endgroup$
    – Anthony
    Jul 29, 2012 at 3:51
  • $\begingroup$ @Anthony: My mistake. I didn't realize that Church encodings were used except in the untyped lambda calculus. $\endgroup$ Jul 29, 2012 at 7:03
  • 2
    $\begingroup$ Why does “deciding equivalence of normal forms of two simply typed lambda-terms is not elementary recursive” imply that you can express nonelementary functions? I do not think that there is any guarantee that equivalence can be expressed. $\endgroup$ Jul 29, 2012 at 11:45
  • 1
    $\begingroup$ Looking forward for this answer in 2015, any luck yet? $\endgroup$
    – MaiaVictor
    Oct 5, 2015 at 19:08

1 Answer 1

9
$\begingroup$

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…)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.