Computing without memory

Details Computing without memory Computing without memory

2011-11-25

arxiv.org/abs/1111.6026v2

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computing without memory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing without memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing without memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-174654