Relative Constructibility via Generalised Sequential Algorithms

Abstract

We modify Gurevich's definition of sequential algorithms, so that it becomes amenable to computation with arbitrarily large sets on a sufficiently intuitive level. As a result, two classes of abstract algorithms are obtained, namely generalised sequential algorithms (GSeqAs) and generalised sequential algorithms with parameters (GSeqAPs). We derive from each class a relative computability relation on sets which is analogous to the Turing reducibility relation on reals. We then prove that the relative computability relation derived from GSeqAPs is equivalent to the relative constructibility relation in set theory.

47 pages, 3 tables. An error was found in the motivating example concerning abstract state machines. In light of this, the first section was reworked and our results reframed