Format:
Online-Ressource (XVI, 229 p, digital)
ISBN:
9789491216657
,
1283634473
,
9781283634472
Series Statement:
Atlantis Studies in Computing 2
Content:
Introduction -- Instruction Sequences -- Instruction Processing -- Expressiveness of Instruction Sequences -- Computation-Theoretic Issues -- Computer-Architectural Issues -- Instruction Sequences and Process Algebra -- Variations on a Theme -- Appendix A: Five Challenges for Projectionism -- Appendix B: Natural Number Functional Units -- Appendix C: Dynamically Instantiated Instructions -- Appendix D: Analytic Execution Architectures.
Content:
This book demonstrates that the concept of an instruction sequence offers a novel and useful viewpoint on issues relating to diverse subjects in computer science. Selected issues relating to well-known subjects from the theory of computation and the area of computer architecture are rigorously investigated in this book thinking in terms of instruction sequences. The subjects from the theory of computation, to wit the halting problem and non-uniform computational complexity, are usually investigated thinking in terms of a common model of computation such as Turing machines and Boolean circuits. The subjects from the area of computer architecture, to wit instruction sequence performance, instruction set architectures and remote instruction processing, are usually not investigated in a rigorous way at all.
Note:
Description based upon print version of record
,
Instruction Sequences for Computer Science; Preface; Contents; List of Tables; 1 Introduction; 2 Instruction Sequences; 2.1 Single Pass Instruction Sequence Algebra; 2.1.1 Primitive instructions; 2.1.2 Constants, operators and equational axioms; 2.1.3 The initial model; 2.1.4 Structural congruence; 2.2 Basic Thread Algebra; 2.2.1 Constants, operators and equational axioms; 2.2.2 Recursion; 2.2.3 Regular threads; 2.2.4 The projective limit model; 2.2.5 Thread extraction for instruction sequences; 2.2.6 Behavioural equivalence of instruction sequences; 2.3 Instruction Sequence Notations
,
2.3.1 The instruction sequence notation2.3.2 The instruction sequence notation; 2.3.3 Inter-translatability of; 2.3.4 Additional instruction sequence notations; 3 Instruction Processing; 3.1 Basics of Instruction Processing; 3.1.1 Services and service families; 3.1.2 Use, apply and reply; 3.1.3 Recursion; 3.1.4 Example; 3.1.5 Elimination; 3.1.6 Properties; 3.1.7 Relevant use conventions; 3.1.8 The extended projective limit model; 3.1.9 Abstraction; 3.2 Functional Units and Services; 3.2.1 The concept of a functional unit; 3.2.2 A Boolean register functional unit
,
3.2.3 A natural number register functional unit3.2.4 A natural number stack functional unit; 3.2.5 A natural number counter functional unit; 3.3 Functional Unit Related Additional Instructions; 3.3.1 Indirect absolute jump instructions; 3.3.2 Indirect relative jump instructions; 3.3.3 Double indirect jump instructions; 3.3.4 Returning jump and return instructions; 3.3.5 Dynamically instantiated instructions; 4 Expressiveness of Instruction Sequences; 4.1 Basic Expressiveness Results; 4.2 Jump-Free Instruction Sequences; 4.3 Gotos and a Bounded Number of Labels; 4.3.1 Labels and gotos
,
4.3.2 A bounded number of labels4.4 The Jump-Shift Instruction and Finiteness Issues; 4.4.1 The jump-shift instruction; 4.4.2 An alternative thread extraction operator; 4.4.3 On finite-state execution mechanisms; 5 Computation-Theoretic Issues; 5.1 Autosolvability of Halting Problem Instances; 5.1.1 Functional units relating to Turing machine tapes; 5.1.2 Interpreters; 5.1.3 Autosolvability of the halting problem; 5.2 Non-uniform Computational Complexity; 5.2.1 Instruction sequences acting on Boolean registers; 5.2.2 The complexity class
,
5.2.3 The non-uniform super-polynomial complexity hypothesis5.2.4 Splitting instruction sequences; 5.2.5 The complexity class; 5.2.6 Super-polynomial feature elimination complexity hypotheses; 6 Computer-Architectural Issues; 6.1 Instruction Sequence Performance; 6.2 Load/Store Instruction Set Architectures; 6.2.1 Maurer machines; 6.2.2 Strict load/store Maurer ISAs; 6.2.3 Reducing the operating unit size; 6.2.4 Thread powered function classes; 7 Instruction Sequences and Process Algebra; 7.1 Process Algebra; 7.1.1 Algebra of communicating processes; 7.1.2 Process extraction for threads
,
Proposition 7.2.
Additional Edition:
ISBN 9789491216640
Additional Edition:
Buchausg. u.d.T. ISBN 978-94-91216-64-0
Language:
English
DOI:
10.2991/978-94-91216-65-7
Bookmarklink
