A Rice-like theorem for primitive recursive functions

2015/03/17 by Mathieu Hoyrup, Hoyrup, Mathieu
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #F.1.1 #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.LO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1503.05025

arxiv created 2015/03/17 · openalex publication_date 2015/03/17 · arxiv updated 2015/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide an explicit characterization of the properties of primitive recursive functions that are decidable or semi-decidable, given a primitive recursive index for the function. The result is much more general as it applies to any c.e. class of total computable functions. This is an analog of Rice and Rice-Shapiro theorem, for restricted classes of total computable functions.

Related

• Primitive recursive functions versus partial recursive functions: comparing the degree of undecidability
• A Characterization of Turing Machines that Compute Primitive Recursive Functions
• Intensional Kleene and Rice Theorems for Abstract Program Semantics
• Formalizing computability theory via partial recursive functions
• Total Recursion over Lexicographical Orderings: Elementary Recursive Operators Beyond PR