Maurer Computers with Single-Thread Control

Article type: Research Article

Authors: Bergstra, Jan A. | Middelburg, Cornelis A.

Affiliations: Programming Research Group, University of Amsterdam, P.O. Box 41882, 1009 DB Amsterdam, the Netherlands. E-mail: {J.A.Bergstra,C.A.Middelburg}@uva.nl

Abstract: We investigate basic issues concerning stored threads and their execution, building upon Maurer's model for computers and the thread algebra of Bergstra et al. We show among other things that a single thread can control the execution on a Maurer machine of any executable finite-state thread stored in the memory of the Maurer machine. We also relate stored threads with programs as considered in the program algebra of Bergstra et al. The work is intended as a preparation for the development of a formal approach to model micro-architectures and to verify their correctness and anticipated speed-up results.

Keywords: Maurer computer, thread algebra, stored thread, execution, control thread, program algebra

Journal: Fundamenta Informaticae, vol. 80, no. 4, pp. 333-362, 2007