Skip to main content
Armando Matos's user avatar
Armando Matos's user avatar
Armando Matos's user avatar
Armando Matos
  • Member for 10 years, 11 months
  • Last seen more than 10 years ago
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
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
Loading…
Loading…
Loading…
awarded
revised
Loading…
awarded
Loading…
1
2