Decidability results for primitive recursive algorithms (Q1399975)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Decidability results for primitive recursive algorithms |
scientific article; zbMATH DE number 1957333
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Decidability results for primitive recursive algorithms |
scientific article; zbMATH DE number 1957333 |
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
