Use reduction to show that the following function is not computable, where P is any python program that takes a single input x:
sotrue(P) = true, if P(x) returns true for every value of x,
sotrue(P) = false, otherwise (if P(x) returns False or does not halt for at least one value of x)
The proof is proof by contradiction, and the goal is to find a way to compute halt, given a supposed algorithm for sotrue(P). Assuming that soTrue can be computed, I want to reach the contradiction that halt is computable. Here is the algorithm I created:
def halt (f, i): def sotrue(P): ...code for sotrue goes here... def ff(x) f(i) return true return soTrue(ff)
So halt(f, i) computes halt! This is a contradiction since halt is known to not be computable! By contradiction, sotrue(P) is also not computable.
MY QUESTION IS: The algorithm I made seems too simple to be true. Could anyone point out if there is some problem with my algorithm or suggest a way to include the case when P(x) returns False since my proof does not include it, but rather is based on the "does not halt" part of the problem?