Execution trace sets for real computation

Abstract

Traditional models of computation and algorithms take a constructive approach, essentially considering a transition function over a given state space. Yet algorithms may also be considered in terms of the observed behaviour they generate. This paper marries these perspectives with a domain-independent, trace based account of computational and algorithmic processes. We focus on the model of real computation due to Blum, Shub and Smale [3] and provide a precise characterisation of the execution trace sets generated by their machines.