The concept of an instruction sequence is a key concept in the practice of computing. For instance, in much work on computer architecture, instruction sequences are under discussion. In spite of this, the notion of an instruction sequence has never been subjected to systematic and precise analysis. The concept of an instruction sequence has as yet not come prominently into the picture in the theory of computing. For instance, although it is often said that a program is an instruction sequence, this viewpoint on what is a program is not taken in any subarea of the theory of computation. However, if this characterization of a program has any value, it must be the case that it is somehow easier to understand the concept of an instruction sequence than to understand the concept of a program.
The first objective of the work on instruction sequences of which an enumeration is given at this website is to understand the concept of a program. The body of theory developed through the work in question is such that its use as a conceptual preparation for programming is now practically feasible. The notion of an instruction sequence appears in this work as a mathematical abstraction for which the rationale is based on the above-mentioned objective. In this capacity, instruction sequences constitute a primary field of investigation in programming comparable to propositions in logic and rational numbers in arithmetic. The structure of the mathematical abstraction at issue has been determined in advance with the hope of applying it in diverse circumstances where in each case the fit may be less than perfect.
Until now, the work on instruction sequences of which an enumeration is given at this website has, among other things, yielded an approach to computational complexity where program size is used as complexity measure, a contribution to the conceptual analysis of the notion of an algorithm, and new insights into such diverse issues as the halting problem, garbage collection, program parallelization for the purpose of explicit multi-threading and virus detection.The basis of all this work is an algebraic theory of single-pass instruction sequences, called program algebra, and an algebraic theory of mathematical objects that represent in a direct way the behaviours produced by instruction sequences under execution, called basic thread algebra.
The general aim of this website is to bring instruction sequences as a theme in computer science better into the picture. We try to achieve this by means of the following:
- an enumeration of the refereed papers, preprints, and other papers in which the results of the work done so far is presented;
- a brief description of the book in which a comprehensive survey of the results of a large part of the work done so far is given;
- an enumeration of some open questions originating from the work done so far;
- a brief description of the work on thread algebra, i.e. work on extensions of basic thread algebra.
Most refereed papers are freely available. For those that are not freely available, a preprint or postprint is in most cases provided.