We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Memoryless computation : new results, constructions, and extensions.

Gadouleau, Maximilien and Riis, Søren (2015) 'Memoryless computation : new results, constructions, and extensions.', Theoretical computer science., 562 . pp. 129-145.


In this paper, we are interested in memoryless computation, a modern paradigm to compute functions which generalises the famous XOR swap algorithm to exchange the contents of two variables without using a buffer. In memoryless computation, programs are only allowed to update one variable at a time. We first consider programs which do not use any memory. We study the maximum and average number of updates required to compute functions without memory. We then derive the exact number of instructions required to compute any manipulation of variables. This shows that 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 the memoryless computation framework. We then 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.

Item Type:Article
Keywords:Memoryless computation, Models of computation, Computational difficulty, Symmetric group, Theory of data, Combinatorics.
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2015 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:18 September 2014
Date deposited:19 October 2015
Date of first online publication:28 September 2014
Date first made open access:28 March 2016

Save or Share this output

Look up in GoogleScholar