Textbook in PDF format

The concept of an instruction sequence is a key concept in practice, but strangely enough it has as yet not come prominently into the picture in theoretical circles. 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. Moreover, in work on computer architecture, the viewpoint is usually taken that a program is in essence an instruction sequence. By contrast, in the theory of computation, different viewpoints on what is a program are usually taken. This state of affairs brought us to define a general notion of an instruction sequence, to subject it to a systematic and precise analysis, and to provide evidence for the hypothesis that the notion of an instruction sequence is relevant to diverse subjects from the theory of computation and the area of computer architecture. Many results of the work in question are brought together in this book with the aim to bring instruction sequences as a theme in computer science better into the picture. To put it otherwise, this book concerns instruction sequences, the behaviours produced by instruction sequences under execution, the interaction between these behaviours and components of the execution environment concerning the processing of instructions, the expressiveness of instruction sequences, and various issues relating to well-known subjects from computer science where we found that the notion of an instruction sequence is relevant. Most of the issues in question are of a computation-theoretic or computerarchitectural kind. They relate to subjects such as the halting problem, non-uniform computational complexity, instruction sequence performance and instruction set architecture. Some of the issues considered are somehow related to process algebra, namely remote instruction processing and instruction sequence producible processes. Some variations on instruction sequences of the usual kind, such as instruction sequences without a directional bias and probabilistic instruction sequences, are also considered. This book is primarily intended for researchers in computer science interested in instruction sequences as a theme in computer science. It is also meant to be suitable as supplementary reading in courses for graduate students and advanced undergraduate students in computer science. Instruction Sequences Instruction Processing Expressiveness of Instruction Sequences Computation-Theoretic Issues Computer-Architectural Issues Instruction Sequences and Process Algebra Variations on a Theme A Five Challenges for Projectionism B Natural Number Functional Units C Dynamically Instantiated Instructions D Analytic Execution Architectures