Decidability results for primitive recursive algorithms (Q1399975): Difference between revisions

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).