Decidability results for primitive recursive algorithms

DOI10.1016/S0304-3975(02)00732-6MaRDI QIDQ1399975zbMATH OpenOpenAlexFDO

Authors D. Massart

Publication date 30 July 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(02)00732-6

zbMATH Keywords

decidabilitymutal recursionobstination theoremprimitive recursionprimitive recursive combinatortrace

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20)

Review text

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

Recommendations

• On the asymptotic behaviour of primitive recursive algorithms
• scientific article; zbMATH DE number 55171
• A representation theorem for primitive recursive algorithms
• scientific article; zbMATH DE number 559098
• On list primitive recursion and the complexity of computing inf

Cites work

• A complete characterization of primitive recursive intensional behaviours
• A unary representation result for system \(T\)
• About primitive recursive algorithms
• Computing minimum with primitive recursion over lists
• scientific article; zbMATH DE number 4087627 (Why is no real title available?)
• scientific article; zbMATH DE number 55171 (Why is no real title available?)
• scientific article; zbMATH DE number 1229489 (Why is no real title available?)
• scientific article; zbMATH DE number 559098 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Intensional aspects of function definitions
• On the asymptotic behaviour of primitive recursive algorithms
• Sequential algorithms on concrete data structures
• The Inf function in the system \(F\)

Cited in

(9)

• Decidability and complexity analysis by basic paramodulation
• The efficiency of primitive recursive functions: a programmer's view
• A representation theorem for primitive recursive algorithms
• Decidable problems for powerful programs
• scientific article; zbMATH DE number 55171 (Why is no real title available?)
• scientific article; zbMATH DE number 559098 (Why is no real title available?)
• The decidable properties of subrecursive functions
• scientific article; zbMATH DE number 1916517 (Why is no real title available?)
• On the asymptotic behaviour of primitive recursive algorithms

This page was built for publication: Decidability results for primitive recursive algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1399975)