|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 2 van 4 gevonden artikelen
| Titel: |
First and Second Order Recursion on Abstract Data Types |
| Auteur: |
Jian Xu Jeffery Zucker |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 67 (2005) nr. 4 pagina's 377-419 |
| Jaar: |
2005-09-12 |
| Inhoud: |
This paper compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system ACP(A) of "abstract computational procedures" based on a least fixed point operator, and Tucker and Zucker's system μPR(A) based on primitive recursion on the naturals together with a least number operator. We prove a conjecture of Feferman that (assuming 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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 2 van 4 gevonden artikelen
| << vorige | volgende >> |