1
$\begingroup$

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?

1 Answers 1