Computable Execution Traces

Abstract

This paper gives an execution trace set based account of computability by imposing restrictions on sets of arbitrary sequences of objects, based on a supplied stock of unary tests and binary operations. This account of finite control computability provides a highly general, top down perspective on computability. We prove equivalence with the Turing machine model, under appropriate assumptions, and show how finite control computability can be used to provide a unified account of computability across multiple levels of abstraction.