Abstract:
We consider a problem of calculating the terms $t$ of a family $T$ using a computer according to a program $\Pi (t)$. The quantity $S(t)=\min|\Pi (t)|$ is called the register complexity of calculating the term $t$, where $|\Pi (t)|$ is the number of registers used by the program $\Pi (t)$. We prove that $S(t)\geqslant h/2+1$ for the family of terms of height $h$.