Set Theory · Application: Undecidability of Halting

Lesson 9

Nikolai Chukhin · Alexander S. Kulikov

Theorem (Turing, 1936). The halting problem is undecidable: there is no algorithm that, given a program \(P\) and its input \(x\), can determine in a finite number of steps whether \(P\) halts on \(x\).

Proof. Suppose we could write a Python method \(\texttt{is\_{halting}}\), which determines whether a program in the file \(\texttt{program\_{file}\_{name}}\) halts on input from the file \(\texttt{input\_{file}\_{name}}\). Below, we will show that this method cannot work correctly. To do so, we will write a simple function \(\texttt{paradox}\).

def is_halting(program_file_name, input_file_name):
    ...


def paradox(file_name):
    if is_halting(file_name, file_name):
        while True:
            pass

As shown, it halts on input \(\texttt{file\_{name}}\) if and only if the program \(\texttt{file\_{name}}\) does not halt when given itself as input. What happens if we save this code snippet in the file \(\texttt{paradox.py}\) and then call \(\texttt{paradox('paradox.py')}\)? If the program halts, then \[\texttt{is\_{halting}('paradox.py', 'paradox.py')}\] must return \(\texttt{False}\), which means that \(\texttt{paradox('paradox.py')}\) does not halt. And vice versa!◼

For the curious 🤓

There exist problems that are “more undecidable.” For example, writing a program that determines whether a given program halts on all inputs is impossible even if the original program has oracle access to the halting problem.