# Minimum number of distinct variables needed for lambda calculus to be Turing-complete?

Suppose you start with your everyday vanilla untyped lambda calculus, but restrict the alphabet to a finite number of variables. What is the minimum number of variables you need for Turing-completeness?

For example, if you only have $$\Sigma=\{x\}$$, it seems like the number of things you can do with $$\lambda x . M$$ will be heavily curtailed, since every variable is bound to its nearest $$\lambda$$, so you can only work with one variable at a time.

However, since $$\Sigma=\{x,y,z\}$$ is sufficient to form the $$\mathbf{S}$$ and $$\mathbf{K}$$ combinators, that immediately seems like it must be Turing-complete.

My question: what are the limitations of lambda calculus when restricted to one or two variables? Do they correspond to other well-known computational categories, like having the same expressive power as some class of automaton? I would expect two variables to be strictly more powerful than one, but I can't seem to find anything on either case by searching.

• Yes, three variables are definitely enough, for the reason you have. No idea about fewer variables. Commented Oct 10, 2021 at 4:00