Haulting problem

The haulting problem is a question in theoretical computer science: given a program and an input, will the program eventually halt when run with that particular input? It is mathematically impossible to write a general algorithm that solves this for all possible programs, as proven by Alan Turing in 1936. The proof is based on contradiction (see liar’s paradox).

Example

h takes two arguments i from g and tries to determine whether or not i(i) haults. g waits for h to make its determination, then does the exact opposite: if i(i) haults, loop forever; if i(i) doesn’t hault, return.

If g was passed to itself (g(g)), it is impossible for h to determine whether or not g haults.

def g(i):
    if h(i, i) == True:
        while True:
            pass
    else:
        return