4 ms·
No, could be proven by the transitivity of computability under composition. Provided the function <(,) is computable for all typeof(f) and typeof(g).
by zardo 9y ago
No, could be proven by the transitivity of computability under composition.
Provided the function <(,) is computable for all typeof(f) and typeof(g).
- stcredzero 9y agoInteresting, thanks. So it should be possible to define f() and g() such that neither of those are computable, but the truth of f(x) < g(x) is computable, but not so much for f(x) < g(y). Could one construct a couple of monotonically increasing uncomputable functions with that known relationship?
- zardo 9y ago>So it should be possible to define f() and g() such that neither of those are computable, but the truth of f(x) < g(x) is computable, but not so much for f(x) < g(y). The difficulty is really just defining an uncomputable function that has a definite value for some domain, but this can be done. Let's call one h. f(x): -abs(h(x)) g(x): -f(x) Gives your second inequality.