Proofs based on diagonalization help reveal the limits of algorithms(quantamagazine.org)

    def is_even (n):
        return n % 2 == 0

    def is_even (n):
        return n % 2 == 0

    def collatz (n):
        i = 0
        while n != 1:
            i += 1
            if n % 2 == 0:
                n = n // 2
            else:
                n = 3 * n + 1
        return i

    def collatz_is_even (n):
        return is_even(collatz(n))

    def proofs (X):
        # Does a breadth-first search through proofs in first order logic
        # from axiom system X. Will yield proofs in order.
        ...

    def found_boolean_seq (code):
        # If proof proves that <code> returns a function seq which always
        # returns a Boolean when passed a natural number, will return code
        # as a string.
        #
        # Otherwise it returns None.
        ....

    def boolean_seqs (X):
        # A list that will include every function that X proves defines a
        # boolean sequence. All functions that X can prove this about will
        # be somewhere in the sequence.
        #
        # This returns them as closures.
        # 
        for proof in proofs(X):
            code = found_boolean_seq(proof)
            if code is None:
                yield lambda n: False
            else
                yield eval(code, {})

    def boolean_seq (X, n):
        # Returns the n'th boolean sequence from boolean_seqs.
        #
        # This returns it as a closure.
        i = 0
        for f in boolean_seqs(X):
            i += 1
            if i == n:
                return f

    def diagonalize (X):
        # Returns a sequence that disagrees with every other one on our list.
        def inner (n):
            return not boolean_seq(X, n)(n)
        return inner

    # Do some work to set up the axiom system X
    ...

    # And return the diagonalized sequence.
    diagonalize(X)