comment
Are there natural, small, and total recursive functions that are not primitive recursive?
Yes, I mean "total recursive", I'll edit the question, thanks!
comment
Are there natural, small, and total recursive functions that are not primitive recursive?
The problems you mention are not recursive, the question was about total and not PR functions. Do you know any?
comment
Are there natural, small, and total recursive functions that are not primitive recursive?
I was thinking in the definition of the function, A(0,n)=n+1, etc.
Loading…
Loading…
comment
"Rice (like) Theorem" for primitive recursive functions?
1) Isn't PR decidable very weak? It can't even answer if $f(0)=0$, where $f$ is the input function. 2) What is the relationship between the existence of discontinuous predicates and Rice-like PR theorems?
comment
"Rice (like) Theorem" for primitive recursive functions?
Very interesting! 2 questions:
revised
Is Kolmogorov complexity (KC) relevant for proof theory?
added 156 characters in body; edited title
Loading…
revised
Is Kolmogorov complexity (KC) relevant for proof theory?
added 156 characters in body; edited title
Loading…
Loading…
comment
"Rice (like) Theorem" for primitive recursive functions?
Given a TM M with index e define a PR function f(n) that outputs 1 if the computation M(0) halts in exactly n steps, and outputs 0 otherwise. The property P(f) holds iff the computation M(0) does not halt.
comment
"Rice (like) Theorem" for primitive recursive functions?
This is an interesting answer. In an eventual "Rice Theorem for PR functions" we have to clarify what a "quantified, nontrivial question" is. For instance, the following "$\exists n : f(0)=1+n$" is not such question because it is quantified and nontrivial, but decidable.
revised
"Rice (like) Theorem" for primitive recursive functions?
Shorter justification of the undecidability of the example.
Loading…
revised
"Rice (like) Theorem" for primitive recursive functions?
added 358 characters in body
Loading…
Loading…
awarded
revised
Equivalence of LOOP (primitive recursive functions) and of SRL (reversible transformations) programs
added 27 characters in body; edited title
Loading…
awarded