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)


        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?


Yes -- for most purposes it really is that simple. You're offloading all the real work to the (existing) proof that the halting problem is undecidable.

One quibble, however, is that I would understand the specification such that sotrue takes a program's (or function's) source code as input, whereas you're passing it a function object. I'm not sure off the top of my head what kind of reflection Python allows on function objects, but in most programming languages they are rather more opaque than the source code, so by assuming that sotrue can do something with a function object, you're making it particularly hard for sotrue to exist.

Your proof would be more convincing if you assume that sotrue accepts program text as its input (and similarly your halting decider works on program text). Then what you need to do in your reduction is to construct the text of a program that includes what you get as input but wraps it in a new main program that replaces its output with "true". Depending on how seriously you take this, you might end up needing to do some parsing in order to avoid name clashes in your generated wrapper code -- which can become fairly long and complex, but there's no doubt that it is possible to do such analysis in Python. So when what you're ultimately looking for a proof rather than an implementation you will be able to get away with just sketching as pseudocode what it has to do.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.