Does... Not... Compute!

When a function is not computable, it can bring a big headache to any programmer! That is why it is necessary for us to determine whether a function is computable or not. From what I was able to observe, a function is deemed non-computable when it has a definition that prompts it to return a value even when an inner function that was called inside does not halt.

To be able to determine properly if a function is non-computable, we need to reduce it to what we already know to be non-computable: our favourite function, halt().

Let us look at the following example:

def is_bigger_than_five(f, v)
    """
    Return True iff f(v) returns an int that is bigger than 5
    """
    #code here

    return True

At simple sight, we can tell that, if f(v) does not stop, then the function should return False. To be sure, we need to reduce it to halt in the following way:

def halt(f, i)

    def is_life(g, v)
        """
        Return True iff f(v) returns "life"
        """
        #code here

        return True

    def f_prime(x)
        """
        Ignore the argument x, call f with the fixed argument i (the one passed into halt)
        """

        f(i)

        return "life"

    return is_life(f_prime, v)

From the following, we can conclude:

• If f(i) halts, then is_life(f_prime, v) is True
• If f(i) does not halt, then is_life(f_prime, v) is False

Therefore, is_life() is not computable!