Paper Info
Title
Primitive recursive functions versus partial recursive functions: comparing the degree of undecidability.
Abstract
Consider a decision problem whose instance is a function. Its degree of undecidability, measured by the corresponding class of the arithmetic (or Kleene-Mostowski) hierarchy hierarchy, may depend on whether the instance is a partial recursive or a primitive recursive function. A similar situation happens for results like Rice Theorem (which is false for primitive recursive functions). Classical Recursion Theory deals mainly with the properties of partial recursive functions. We study several natural decision problems related to primitive recursive functions and characterise their degree of undecidability. As an example, we show that, for primitive recursive functions, the injectivity problem is Pi^0_1-complete while the surjectivity problem is Pi_2-complete (omit superscripts from now on). We compare the degree of undecidability (measured by the level in the arithmetic hierarchy) of several primitive recursive decision problems with the corresponding problems of classical Recursion Theory. For instance, the problem does the codomain of a function have exactly one element? is Pi_1-complete for primitive recursive functions and belongs to the class [Delta_2 - (Sigma_1 UNION Pi_1)] for partial recursive functions. An important decision problem, does a given primitive recursive function have at least one zero? is studied in detail.
Year
Venue
Field
2016
arXiv: Logic in Computer Science
μ-recursive function,Successor function,Discrete mathematics,Primitive recursive function,Algorithm,Recursive language,Double recursion,μ operator,Grzegorczyk hierarchy,Primitive recursive arithmetic,Mathematics
DocType
Volume
Citations 
Journal
abs/1607.01686
0
PageRank 
References 
Authors
0.34
8
1
Name
Order
Citations
PageRank
Armando B. Matos100.68