Decidability results for primitive recursive algorithms (Q1399975): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 17:01, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decidability results for primitive recursive algorithms |
scientific article |
Statements
Decidability results for primitive recursive algorithms (English)
0 references
30 July 2003
0 references
In this paper the notion of trace is used to extend \textit{T. Coquand}'s [C. R. Acad. Sci., Paris, Sér. I 314, 489-492 (1992; Zbl 0749.68052)] constructive proof of the obstination theorem of Colson to the case when mutal recursion is allowed. As a by-product an algorithm is obtained that computes the value of a primitive recursive combinator applied to integers (that are ``lazy'' in the sense that arguments might be undefined).
0 references
primitive recursion
0 references
decidability
0 references
trace
0 references
obstination theorem
0 references
mutal recursion
0 references
primitive recursive combinator
0 references