Decidability results for primitive recursive algorithms (Q1399975): Difference between revisions
From MaRDI portal
Latest revision as of 10:11, 30 July 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