Well, the second condition just means no provably total recursive function computes it in first place (or it is not provably a permutation).
-
-
-
The parenthetical should just say "or it is not provably surjective".
-
Polynomial time functions can be made provably total. But yes, 2nd condition says no provably surjective recursive function computes it.
-
Right, I was just saying "computes its inverse" is needlessly wordy compared to "computes it".
-
To code n which computes function f, we can easily associate code Inv(n) which computes f^{-1} (choosing, say, minimal preimages).
-
Ah, but all these things you post are half the time impossibilities anyway, I forgot…
-
Inv(f) will compute a permutation, but might not be provably total. I think most of my math-related noun phrases are possible.
-
In that case, I return to saying might as well just say "a permutation of N that is computable in polytime, but not provably (in ZFC) onto".
- 5 more replies
New conversation -
-
-
f(n) = n if the nth proof in ZFC is not a proof of Con(ZFC) and 1 otherwise? I'm pretty sure this is poly time
-
I mean no recursive function computes the inverse and is provably total, not that no recursive function provably computes the inverse.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.