Jian Xu:   MSc Thesis, August 2003.
Models of Computation on Abstract Data Types based on Recursive Schemes.

Abstract.   This thesis compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system ACP(A) of "abstract computational procedures" on A, and Tucker and Zucker's system μPR(A) of primitive recursive schemes on A together with the minimum number operator. We prove a conjecture of Feferman that (assuming A contains sorts for naturals numbers and arrays of data) the two systems are equivalent. The main step in the proof is showing the equivalence of both systems to a system Rec(A) of computation by an imperative programming language with recursive calls. The result provides a confirmation of a Generalised Church-Turing Thesis for computation on abstract data types.