Computing without memory
Source: Maximilien Gadouleau
Abstract
In this paper, we generalise the famous algorithm for swapping the contents of two variables without using a buffer. We introduce a novel combinatorial framework for procedural programming languages, where programs are only allowed to update one variable at a time. We first consider programs which do not have any memory. We prove that any function of all the variables can be computed this way in a number of updates which grows linearly with the number of variables. Similarly, any linear function can be computed using a linear number of linear instructions. We then derive the exact number of instructions required to compute any manipulation of variables. This shows that the idea of combining variables instead of simply moving them around not only allows for memoryless programs, but also yields shorter programs. Second, we show that allowing programs to use memory is also incorporated in our framework. We quantify the gains obtained by using memory. This leads to shorter programs and allows us to use only binary instructions, which is not sufficient in general when no memory is used.
| }
|