<p>The Binary Lambda Calculus defines a binary encoding for any closed term in the untyped lambda calculus, and also suggests a bijection between natural numbers and binary strings, but the former is not surjective.
Still, the paper <a href="http://arxiv.org/abs/1401.0379" rel="nofollow">http://arxiv.org/abs/1401.0379</a>
"Counting Terms in the Binary Lambda Calculus"
might yield efficient ranking/unranking mappings.</p>
What is a mapping between natural numbers and valid simply typed lambda calculus terms?
<p>Is there any efficient algorithm that maps between well-typed, closed terms of the simply typed lambda calculus and natural numbers? For example, using bruijn indexes (and probably on incorrect order):</p>

<pre><code>0 → (λ 0)
1 → (λ (λ (0 1)))
2 → (λ (λ (1 0)))
3 → (λ 0 (λ 0))
4 → (λ (λ 0) 0)
5 → (λ (λ 1) 0)
6 → ... so on
</code></pre>

<p>Related questions: is there an algorithm that maps between natural numbers and <strong>normalized</strong> terms of the simply typed lambda calculus? Also, the same questions applied to the untyped lambda calculus.</p>