# zbMATH — the first resource for mathematics

Counting and generating terms in the binary lambda calculus. (English) Zbl 1419.68039
Summary: In a paper [in: Randomness and complexity. From Leibniz to Chaitin. Dedicated to Gregory J. Chaitin on the occasion of his 60th birthday. Hackensack, NJ: World Scientific. 237–260 (2007; Zbl 1137.68020)], J. Tromp presents a simple way of encoding lambda calculus terms as binary sequences. In what follows, we study the numbers of binary strings of a given size that represent lambda terms and derive results from their generating functions, especially that the number of terms of size $$n$$ grows roughly like $$1.963447954\dots^n$$. In a second part we use this approach to generate random lambda terms using Boltzmann samplers.

##### MSC:
 68N18 Functional programming and lambda calculus 03B40 Combinatory logic and lambda calculus 05A15 Exact enumeration problems, generating functions