Constant time parallel computations in lambda-calculus
We are studying here the computations over free algebras that can be done in a constant number of complete developments of the pure lambda -calculus. In the following, such computations will be called constant time parallel computations (considering that all redexes in lambda -term are reduced "at the same time" to produce its complete development). This has obviously nothing to do with a realistic definition of constant time parallel computation, but the set K-Lambda of numeric functions that are computable in this way enjoys good closure properties making it close in some sense to the class of elementary functions. We prove that a function over free algebras is computable in parallel constant time in the pure lambda -calculus, iff it is representable in the simply typed lambda -calculus Lambda (-->). In considering the latter, the full type structures of Lambda (-->) prove to be serious tools for an extensional study of the functions A-representable with constant parallel runtime, giving us in particular a full description of the A-representable predicates. (C) 2001 Published by Elsevier Science B.V.
complete developments full type structure lambda calculus simple typing elementary complexity