This paper compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system ACP(A) of "abstractcomputational procedures" based on a least fixed point operator, and T...
详细信息
This paper compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system ACP(A) of "abstractcomputational procedures" based on a least fixed point operator, and Tucker and Zucker's system mu PR(A) based on primitive recursion on the naturals together with a least number operator. We prove a conjecture of Feferman that (assuming A contains sorts for natural 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 for a Generalized Church-Turing Thesis for computation on abstract data types.
The Universal Function Theorem (UFT) originated in 1930s with the work of Alan Turing, who proved the existence of a universal Turing machine for computations on strings over a finite alphabet. This stimulated the dev...
详细信息
The Universal Function Theorem (UFT) originated in 1930s with the work of Alan Turing, who proved the existence of a universal Turing machine for computations on strings over a finite alphabet. This stimulated the development of stored-program computers. Classical computability theory, including the UFT and the theory of semicomputable sets, has been extended by Tucker and Zucker to abstract many-sorted algebras, with algorithms formalized as deterministic While programs. This paper investigates the extension of this work to the nondeterministic programming languages While(RA) consisting of While programs extended by random assignments, as well as sublanguages of While(RA) formed by restricting the random assignments to booleans or naturals only. It also investigates the nondeterministic language GC of guarded commands. There are two topics of investigation: (1) the extent to which the UFT holds over abstract algebras in these languages;(2) concepts of semicomputability for these languages, and the extent to which they coincide with semicomputability for the deterministic While language. (C) 2006 Elsevier Inc. All rights reserved.
暂无评论