Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

First and Second Order Recursion on Abstract Data Types

Xu J., Zucker J.

Fundamenta Informaticae

2005

Vol. 67, nr 4

377--419

This paper compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system of ``abstract computational procedures" based on a least fixed point operator, and Tucker and Zucker's system 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 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.