# Understanding a computer program that shows halting problem is unsolvable

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 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'.

1. 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.

• Thank you so much for the detailed answer. I am afraid it still doesn't fix my confusion. I guess my main problem is that we are defining a function g using itself which looks circular to me. I suppose that in python language, this means there is some recursion going, but doesn't a recursion need an initial value ?
– Amr
Oct 6, 2021 at 12:58
• I think my real question is, how can the function $g$ in it's code call something that has not yet been defined which is $g$
– Amr
Oct 6, 2021 at 13:10
• The function 'g' does not execute itself. It provides itself to the function 'halts' and the function 'halts' returns true or false. We do not know how 'halts' is implemented. As noticed in my answer, we can not even implement the function 'halts' for general input functions in the real world. This is a theoretical construct for proving things. If the function 'halts' actually executes 'g' then yes, this would be a recursion and the function 'halts' would never stop running. We assume that 'halts' magically knows if the provided function 'g' halts or not. Oct 6, 2021 at 13:11
• Yes I understand that the non implementability of halts will not let us execute g by hand. That's why I suggest the following, what if we replace halts by some other implementable function halts* that takes an input code and returns true if the program code has at most 5 lines and returns false otherwise. Then I think I still don't know how to execute g by hand
– Amr
Oct 6, 2021 at 13:16
• In other words, it appears to me that the algorithm g is not well defined. Of course that means I m missing something very obvious about programming languages...
– Amr
Oct 6, 2021 at 13:18

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.

• Thanks for the answer. David Scholz and Ian were patient enough to explain to me what I was missing in the chatroom
– Amr
Oct 6, 2021 at 19:56