Execution Architectures for Program Algebra

Abstract

We investigate the notion of an execution architecture in the setting of the program algebra PGA, and distinguish two sorts of these: analytic architectures, designed for the purpose of explanation and provided with a process-algebraic, compositional semantics, and synthetic architectures, focusing on how a program may be a physical part of an execution architecture. Then we discuss in detail the Turing machine, a well-known example of an analytic architecture. The logical core of the halting problem — the inability to forecast termination behavior of programs—leads us to a few approaches and examples on related issues: forecasters and rational agents. In particular, we consider architectures suitable to run a Newcomb paradox system and the Prisoner’s Dilemma.