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.