Understanding a computer program that shows halting problem is unsolvable

Question

Wikipedia puts the following program code as an example of a computer program that shows why the halting problem is unsolvable:

I can follow the argument that if such a program $g$ exists /is well defined then we get a contradiction and so the totally computable function $halts$ can't exist. However I don't understand what the program $g$ does. I dont understand the defintion of $g$ to the point where I can't even execute the first two or three steps of it by hand. I have almost zero knowledge about programming languages and probably that's what I am lacking. I already know the proof of impossibility of solving the halting problem by enumerating all Turing machines and using a diagonalization argument, however I still want to understand the computer programming language version of the proof as it looks very concise. I d be grateful of someone can explain to me what $g$ really does

Answer 1

Let us consider a slightly adjusted version of g.

def g():
    doesHalt = halts(g)
    if doesHalt:
        loop_forever()
        return True 
    else:
        return True

Now, let us go through each line step by step.

1. 'def g()'. This defines a function called 'g' which takes zero arguments (a function 'def g(a)' is a function called 'g' which takes a single argument called 'a', a function 'def g(a, b)' is a function called 'g' which takes two arguments called 'a' and 'b' and so on). We can call this function in our code by just writing 'g()' and by calling we mean that we execute the code that is defined in the function 'g'.

Let us provide a few examples in the Python programming language (since the code in the proof is basically python code). I suggest that you execute the code yourself by using a jupyter notebook or any other environment of your choice.

def g():
    print("Hello World")

g()

If we execute the above code, then it prints 'Hello world'. Notice that we are calling a function called 'print' which takes a single argument as an input. In our case we have provided a string 'Hello World'. Let us write a function that calls another function that calls the printing function for us.

def loop_forever():
    print("Hello World")

def g():
    loop_forever()

g()

The above does yield in the same result as the first implementation. We call the function 'g'. Within that function we call another function called 'loop_forever'. The function 'loop_forever' prints 'Hello World' by calling the function 'print'. Notice that we have not defined the function 'print' but it is defined somewhere in Python itself. We ignore the implementation at this point in time and just assume that it prints the provided string to the console (which it does; try it).

Now, let as adjust the function 'loop_forever' as follows.

def loop_forever():
    while 1 == 1:
        print("Hello World")

The statement in the second line is called a 'while loop'. It executes everything after the ':' which is indented as long as the statement in between the 'while' and the ':' is true. In our case the statement $1 == 1$ is always true (the $==$ is a python operator which tests if the right hand side is equal to the left hand side and returns 'true' if they are equal and 'false' otherwise). What will happen if we call the function 'loop_forever'? It will print 'Hello World' forever. The function does not hold.

If we take a look at the compiled code, then the compiler usually compiles the above to the following.

def loop_forever():
    a = (1 == 1)
    while a:
        print("Hello World")

The statement '$1 == 1$' is assigned to a variable called 'a'. The while statements runs as long as the variable 'a' is true which is always the case in our implementation.

Most compilers are quite clever and usually would compile the above to the following.

def loop_forever():
    while True:
        print("Hello World")

Since the statement 'True' is trivially always true, we could implement our initial implementation as follows.

def loop_forever():
    while True:
        print("Hello World")

def g():
    doesHalt = halts(g)
    if doesHalt:
        loop_forever() 
    else:
        return True

Now, let us consider the second line of the function 'g'.

2. The statement 'doesHalt = halts(g)' assigns the return value of the function 'halts(g)' to a variable called 'doesHalt'.

Let us consider the next six lines. This is called an 'if-else-statement'. It reads as follows: If the variable 'doesHalt' is 'true', then execute 'loop_forever'. If the variable 'doesHalt' is 'false', then just return the value 'True'.

We have two cases.

1. The variable 'doesHalt' is 'true',
2. The variable 'doesHalt' is 'false'.

If the first case occurs, then the function 'halts' must have returned true with 'g' as an input argument. If the second case occurs, then the function 'halts' must have returned 'false'.

How do we implement the function 'halts(g)'? It appears that this is not possible in the 'real world' for general input functions. The only way to determine whether a general function does or does not halt is to actually execute it. The problem is, if the function does not halt then it would run forever. In theoretial computer science the function 'halts' is an oracle function that is defined as a black-box function. We just assume that it returns 'true' if the function we want to test does hold, and 'false' otherwise.

Now, by definition the function 'halts(g)' only returns 'true' if the function 'g' does halt, BUT then the function 'loop_forever' will be executed since 'doesHalt' is 'true' and 'loop_forever' executes a while loop that never stops, thus the function 'g' does never stops running. It never holds. A contradiction.

The argument for the second case is similar. If 'doesHalt' is 'false', then the function 'halts(g)' must have returned 'false'. By definition this means that 'g' does never hold, but since 'doesHalt' is 'false', the 'else'-case is executed which just returns 'True'. The function 'g' halts. A contradiction.

Answer 2

Per the poster's comments, I think the point of issue is the following:

Why are we allowed to use $g$ inside the definition of $g$?

This is indeed quite weird at first glance, and the brevity of this proof stems from the "under-the-hood" work of making this sort of definition acceptable being taken for granted. The relevant mathematical result, which says that this is in fact possible, is the recursion theorem. This is a bit technical, and the proof is quite slippery despite being short, but basically it says that in a precise sense we may in fact assume during the construction of a program that we already know the code of the program we're constructing.

Here's a bit of detail. Taking for granted only that Python is Turing-complete (in the appropriate sense), one instance of the recursion theorem says the following:

There is some Python program $p$ such that the Python program $f_p$ = "Ask $\mathsf{halts}$ whether program $p$ halts, and loop if the answer is affirmative and halt if the answer is negative" has the same behavior as $p$ itself.

This is because the "program transformation" function sending $p$ to $f_p$ is total computable! The idea then is that this $p$ (which incidentally is not unique) behaves as if it is self-referential in the appropriate precise sense.