1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

Found this paper proving that for Turing completeness, you need a minimum of three variables.

This still leaves open the question of what, if anything, one- and two-variable systems are computationally equivalent to.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .