<p>Typically in lambda calculus you have an infinite stock of variables. Could we get away with a finite set?</p>

CC BY-SA 4.0
2021-08-29T13:21:35.663Z
If I understand what you mean by "get away with", yes, since only three variables are needed to encode a complete combinator basis such as [SKI](https://en.wikipedia.org/wiki/SKI_combinator_calculus) or [BCKW](https://en.wikipedia.org/wiki/B,_C,_K,_W_system).  Conversely, Richard Statman proved that two variables are not enough, as explained in [my answer here](https://cstheory.stackexchange.com/a/36344/674).
Noam Zeilberger
CC BY-SA 4.0
2021-08-29T14:09:52.950Z
Good point. That was my intuition about it. Thanks
Benjamin Grange
<lambda-calculus>
Is there some n such that lambda calculus with only n variables is Turing-complete?
Benjamin Grange
# Is there some n such that lambda calculus with only n variables is Turing-complete?

(Asked by: username_0 on 2021-08-29)

Typically in lambda calculus you have an infinite stock of variables. Could we get away with a finite set?

**Tags:** lambda-calculus
> **Comments:**
> **username_1**: If I understand what you mean by "get away with", yes, since only three variables are needed to encode a complete combinator basis such as [SKI](https://en.wikipedia.org/wiki/SKI_combinator_calculus) or [BCKW](https://en.wikipedia.org/wiki/B,_C,_K,_W_system).  Conversely, Richard Statman proved that two variables are not enough, as explained in [my answer here](https://cstheory.stackexchange.com/a/36344/674).  
> **username_0**: Good point. That was my intuition about it. Thanks  

---

## 0 answers

