The program that cannot exist

In the previous chapter, we mentioned that Turing machines and Python programs are equivalent in terms of the "problems" they can solve. In this chapter, we will formally define the notion of a problem and delve into one of the central axes of computation theory: decidability (Section 3.1).

Next, we will introduce the universal machine (Section 3.2), a concept Turing introduced when presenting his model of computation². This machine will help us find undecidable problems (Section 3.3). Finally, we will introduce the concept of reduction (Section 3.5), which will allow us to find even more undecidable problems.

We will do all of this to deduce the main result of this chapter: the undecidability of the Halting Problem (Section 3.6). This problem is extremely relevant, not only historically, but because it will be one of the pillars of the main proof of this work, which we will carry out in Chapter 5.

3.1 #Decidable problems

We begin, as anticipated, by precisely defining what a problem is.³⁴

A problem is nothing more than a function that maps inputs to outputs, which we call solutions. Any problem can be reduced to this terminology, no matter how complex it may be. Let us see the first description of a problem.

Let us define the input and output sets of Problem 3.2. The input to our problem is a graph $G$, which is nothing more than a set of vertices $V$ and an adjacency matrix $A$ representing its edges ($G = (V, A)$). As output, we will have a set of $n$ paths in $G$, $\pi_1, \pi_2, \ldots, \pi_n$ (it is possible that a graph has none, one, or several Hamiltonian cycles). We can specify the paths as ordered subsets of $V$.

To prove the results of our work, we will use a subset of problems: those whose output is only yes or no. We will call them decision problems.

Any computational problem can be "transformed" into a decision problem by asking about the existence of solutions. An example of this is Problem 3.4.

This problem is a decision problem, since it does not explicitly ask which Hamiltonian cycles are present in a given graph, but rather whether a Hamiltonian cycle exists in it. Evidently, these problems are more restrictive than general computational problems, but they are of much greater interest when discussing which problems can be computed, as we will see later.

In the case of decision problems, it makes sense to speak of their complement.

On some occasions, we will use the notation C- to refer to the complementary problem: given a problem $\textsc{Problem}$, we will call $\textsc{C-Problem}$ its contrary problem.

To continue, it is necessary to comment on some particularities of Python programs for dealing with problems. As we well know, programs only accept strings as input and strings as output. We can think of a Python program $P$ as a function

where $S$ is the set of all possible strings in Python. Depending on the version of Python, this set will be larger or smaller.⁷

For a computer to solve a problem, we will need to encode the inputs and solutions of the problem in a format it can understand: character strings (strings). As shown in Proposition 3.6, for any problem we can assume that inputs and solutions are encoded as strings.

This is not a restriction: inputs and solutions can be encoded as character strings. We must, however, keep in mind that there may be inputs that are not a correct encoding of an input to the original problem. In such a case, we will assign the solution no to that input.

We see an example of this in Problem 3.7. This problem will have a certain encoding associated with its inputs and solutions. Observe that this problem is identical to Problem 3.2, and we can translate the inputs and solutions of one and the other knowing the chosen encoding.

In the case of decision problems, the solutions will always be yes and no. Note that no will be the solution both for negative instances of the problem and for incorrect encodings.

From here on, all problems will have character strings as inputs and solutions.

Next, we will make precise the relationship between programs and problems that we have been intuiting since Chapter 2.

A computational problem describes what we want to solve. A program describes the particular way of computing the solution to a problem.

It is very important to note that, in the previous definition, it is necessary that $P$ halt for all inputs. Or, equivalently, if $P$ loops for some input, it does not solve $F$. This condition can be relaxed, giving rise to semi-decidable problems (see Section 3.4).

In the case of decision problems, this characteristic of "solving" leads us to the definition of computability.

Let us see a simpler problem than Problem 3.2. Problem 3.10 has as input a word over the alphabet $\{\texttt{a}, \texttt{b}\}$, and as solution yes in case the word has more $\texttt{a}$s than $\texttt{b}$s, and no otherwise or in the case of an incorrect encoding. For this problem, the encoding is incorrect if the input is a character string that does not form a word over the alphabet $\{\texttt{a}, \texttt{b}\}$.

Evidently, $\textsc{MoreAsThanBs}$ is a decision problem. Now we must ask ourselves whether this problem is decidable. The answer is affirmative, and it is demonstrated in detail in Proposition 3.11.

If we want to know whether the problem is decidable, we must write a program that solves it and never loops, and that takes incorrect encodings into account. This is precisely what the following program does:

import utilities
 
def more_as_than_b(word):
# check whether the encoding is correct (i.e. over {'a', 'b'}); if not, return 'no'
if not utilities.in_alphabet(word, {'a', 'b'}):
return 'no'
 
if word.count('a') > word.count('b'):
return 'yes'
 
return 'no'

We explain the program briefly. In the more_as_than_b function we see the program's main function, which accepts a word as input. We check that the word belongs to the alphabet $\{\texttt{a}, \texttt{b}\}$ using the in_alphabet function from the utilities library (which we import at the top of the file). If the word does not belong to the alphabet, we return no, since the encoding is incorrect. If it belongs to the alphabet, we check whether it has more $\texttt{a}$s than $\texttt{b}$s. If so, it returns yes; otherwise, it returns no. We see some of the program's outputs in the table below.

Since we have found a program more_as_than_b.py that decides $\textsc{MoreAsThanBs}$, the problem $\textsc{MoreAsThanBs}$ is decidable.

A note regarding our definition of decidability. Normally, in computation theory courses, this definition is made with respect to Turing machines. However, having proved the equivalence with Python programs in Chapter 2, we can define it directly in terms of programs. According to the definition of Turing machines, however, we could also prove that $\textsc{MoreAsThanBs}$ is decidable: it suffices to observe that the machine $M_{\#a>\#b}$ from Example 2.11 decides the problem, since it never loops and accepts the words that have more $a$s than $b$s.

3.2 #Universality

In Section 2.3 we saw how we can simulate a Turing machine using a Python program. But is it possible to simulate a Python program using a Python program? The answer is yes, and it should not be surprising, since many of the operations we execute day to day on our computers involve this type of simulation.

For example, when we run any Python program, we are executing the Python interpreter, which is a program in itself.

This idea of "programs that execute programs" may seem obvious, but it was truly revolutionary, and is the reason personal computers are the norm today, even fitting in our pockets. Perhaps the most incredible thing a computer can do is run anything — not simply a fixed set of programs preinstalled by the manufacturer.⁸

To understand how this can be possible in the case of a Python program, we must understand the operation of the native exec function⁹. If we try it in the interpreter:

>>> exec("print('resultado:', 11+2)")
resultado: 13

We see how we pass a Python statement to exec in the form of a string, and it executes it. In fact, observe how it executed the sum $11 + 2$, and did not simply print 11+2.

We can take this one step further: inside exec we can insert several lines and even define functions, variables, etc.

>>> exec("def hola(nombre):\n\tprint(f'Hola, {nombre}')\nhola('TFG')")
Hola, TFG

Once we know this, we can create the following program:

import utilities
 
def universal_machine(program, input):
# this defines the functions in 'program', but does not execute them yet
try:
exec(program)
except Exception as excepcion:
return 'error: ' + str(excepcion)
 
# extract a reference to the main function, which is defined locally
main = utilities.extract_main(program, locals())
 
# invoke the function
return main(input)

Let us see what Listing 3.2 does. First, we see that the main function accepts two parameters: a program and an input, both strings. We execute the program defined in program, as we explained above. This line is inside a try-except block since the program may be ill-defined, in which case an exception is raised. We catch this exception, since according to the Definition 2.2 definition, the program must not raise any exception. If there is an exception, we return a string with the error details.

If there is no error, exec(program) will execute successfully, and the functions defined in program will be accessible from the universal_machine function. In particular, all definitions from program will be accessible from locals(). We take advantage of this to extract a reference to the main function of program, which we finally execute with the input.

We have managed to create a Python program that is capable of executing another program. This will allow us to execute any of the problems we have created, simply by passing the program as a string. In the utilities library we find the read function, which given a path to a file returns its contents as a single string.

Some examples of execution of universal_machine.py are specified in the following table.

In the first row we can see that, when inserting an invalid program as input, the output of universal_machine.py will be an error. In the second row, we execute the program more_as_than_b.py with the input abaab. The result is exactly as expected (observe the first row of the $\textsc{MoreAsThanBs}$ output table above).

In the third row, we use the code of more_as_than_b.py itself as input to itself. This makes sense, since a program, as we have commented, is nothing more than a string. Remember that Listing 3.1 treats inputs outside the alphabet $\{\texttt{a}, \texttt{b}\}$ as an incorrect input, and that is why the output is no. We modify this in Listing 3.3, in which we accept any input and count its number of $\texttt{a}$s and $\texttt{b}$s. We see how, in the fourth row, the output is yes, since in this case the encoding is correct.

def more_as_than_b_v2(word):
if word.count('a') > word.count('b'):
return 'yes'
 
return 'no'

In the fifth row, we use Listing 3.4. This program always returns yes, regardless of the input we pass. Evidently, this program is the one that decides Problem 3.12 (that is, $\textsc{Yes}$ is decidable).

def si(input):
# always returns 'yes'
return 'yes'

In the sixth and last row we see how universal_machine.py can execute any Python program, even Listing 2.2, which simulates Turing machines. As input to the program we pass the encoding of a Turing machine and the input. Here, the output describes an accepting final configuration.

This ability of programs to execute themselves is extremely interesting and is a characteristic that will cause us many problems, as we will see in Section 3.3.

We call a machine universal if it is capable of simulating any Turing machine, since Turing introduced this concept in his famous publication². By the equivalence result (Theorem 2.23), we see that Listing 3.2 is, indeed, a universal machine (something we could intuit from the program's name).

As we saw at the beginning, the concept of universality is a constant in the computers we use: the hardware is universal, because it can be used to execute any Turing machine, just as an operating system is, since it can compile programs that simulate Turing machines. The Python interpreter is also universal for this same reason, as is the Java virtual machine. Even a program itself (Listing 3.2) can be universal.

3.3 #Undecidable problems

In Section 3.1 we showed how to prove that a problem is decidable, which is straightforward: it suffices to find a program that decides it. However, proving that a problem is not decidable is much more complicated. In this section we will find several undecidable problems.

Let us begin with the $\textsc{Universal}$ problem.¹⁰ Clearly, it is a decision problem, since it returns yes or no. In this section, we will prove that writing a program that decides $\textsc{Universal}$ is impossible. If it were possible to do so, we see in the table below the possible outputs it would have.

In the first row we see how, for incorrect encodings, the program returns no. The following rows are evident, and similar to those of the universal_machine.py table.

We will introduce two more problems. The first of them, $\textsc{Diagonal}$, can be obtained from $\textsc{Universal}$ (Problem 3.13) with $I = P$.

If a program that decides this problem existed, we see in the following table the possible outputs it would have.

The first three outputs require no further explanation. However, let us focus on the last one: what would be the result of executing diagonal.py with the code of diagonal.py?

It seems that both yes and no are correct answers — it suffices to look at the definition of Problem 3.14. Taking $I$ as diagonal.py and $P$ as the same program, then if $P(I) = \texttt{yes}$, the program will return yes, whereas if $P(I) = \texttt{no}$, then the program will return no.

At this point we should suspect that things are not going to go well. Let us finish this "recursive circus" with one last problem, $\textsc{C-Diagonal}$.¹¹ If a program that decides it existed, c_diagonal.py, we see its possible outputs in the table below.

We repeat the same question we asked ourselves for the case of $\textsc{Diagonal}$ (Problem 3.14). What output would a hypothetical program that solves it have, if it uses itself as input? In this case, this question is precisely what shows us that writing such a program is impossible. This tells us that the $\textsc{C-Diagonal}$ problem is not decidable. Let us see a more precise proof of this fact.

We have just found our first undecidable problem: $\textsc{C-Diagonal}$. This fact is of special relevance since, from it, we can prove that $\textsc{Universal}$ is not decidable either.

from universal import universal
 
def diagonal(program):
return universal(program, program)

from diagonal import diagonal
 
def c_diagonal(program):
output = diagonal(program)
 
if output == 'yes':
return 'no'
else:
return 'yes'

We can see the chain of problems we used in Proposition 3.17 in the figure below.

Proving the undecidability of $\textsc{Universal}$ has been a long process, which required other problems. It would be possible to demonstrate this result using a single program, but, using Turing's own words, "[such a] proof, although perfectly sound, [would have] the disadvantage that it may leave the reader with the feeling that 'there must be something wrong'"².

We have already proved that two of the three problems in the chain above are not decidable. The following result will allow us to prove that the last one is not decidable either.

from d import d
 
def c_d(input):
output = d(input)
 
if output == 'yes':
return 'no'
else:
return 'yes'

By Corollary 3.19, knowing that $\textsc{C-Diagonal}$ (Problem 3.15) is undecidable (Proposition 3.16), we have that $\textsc{Diagonal}$ (Problem 3.14) is undecidable.

Knowing that these problems are not decidable is very useful, since it allows us to prove what we seek in this chapter: that the Halting Problem, which we will introduce in Section 3.6, is not decidable either.

To be able to prove this, however, we must use a new tool, which we will develop in Section 3.5. Before that, we will comment on another class of problems: those that "almost" are decidable.

3.4 #Semi-decidable problems

In Definition 3.9, we required that the program halt for each input in order to say that the problem is decidable. If we relax this condition we obtain a new category of problems.

It is clear that every decidable problem is semi-decidable. The converse is not true. We will see an example of this later, in Problem 4.25.

We will not delve into the notion of semi-decidable problem, since it will not be necessary for our study. When necessary, we will refer to the definition specified here.

3.5 #Reductions

In Section 3.3, we used some problems to be able to solve others or to prove that they cannot be solved (see the chain-of-problems figure above). In computation theory, this intuition is formalized in the concept of reduction. When we say that "$F$ reduces to $G$", we mean that "$F$ can be solved if $G$ can be solved".

We call the program $P_G$ whose existence we assume an oracle, following Turing’s oracle-machine terminology.¹³

Intuitively, if we can reduce $F$ to $G$, it is because $G$ is at least as "hard" as $F$, or, reciprocally, $F$ is at least as "easy" as $G$. This intuition is captured in the following proposition.

This proposition allows us to prove that a problem is decidable (or not) from another. This allows us to proceed in several ways. First, if we want to know that a problem $F$ is easy, it suffices to find a decidable problem $G$ to which $F$ reduces, $F \leq_T G$. Then, $F$ will be decidable.

On the other hand, we can prove that a problem $G$ is hard. It suffices to have an undecidable problem $F$ such that $F \leq_T G$. Then, $G$ will not be decidable either.

Let us see a first example of reduction. In Section 3.3 we already saw that $\textsc{Diagonal}$ (Problem 3.14) and $\textsc{Universal}$ (Problem 3.13) are both undecidable. Suppose we only know that $\textsc{Diagonal}$ is undecidable. Then, we will be able to prove the undecidability of $\textsc{Universal}$ through a simple reduction.¹⁴ Observe the following program.

from universal import universal  # oracle
 
def diagonal(program):
output = universal(program, program)
 
if output == 'yes':
return 'yes'
else:
return 'no'

It is straightforward to verify that diagonal_to_universal.py is a reduction of $\textsc{Diagonal}$ to $\textsc{Universal}$. Indeed, the program diagonal_to_universal.py solves $\textsc{Diagonal}$ assuming the existence of a program universal.py that solves $\textsc{Universal}$.

3.6 #The Halting Problem

Given a program $P$ and an input $I$, we have asked what the output of such a program is. Now, we are going to ask whether the program halts.

This problem, of recognizing whether a program halts given an input, is known as the Halting Problem. There are several reasons why we study it: first, this problem has practical application. If it were decidable, we could write an algorithm that, for any program, would check whether it is capable of terminating. Evidently, not all programs halt: some of them are designed to run indefinitely, as is the case with web servers or an operating system.

On the other hand, this problem has special historical relevance. It was one of the first problems to be proved uncomputable, and is one of the seeds of computation theory.

In our case, however, studying this problem will allow us to deduce the central result of this work.

Before talking about this problem, we must remember that the notion of halting that Turing defined is related to machines of the same name: a Turing machine, given an input, can halt and accept, halt and reject, or loop.

In our case, we will say that a Python program $P$ halts on input $I$ if the output $P(I)$ is defined, according to the Definition 2.2 definition. A program could, in this way, fail to halt for many reasons: it could enter an infinite loop, raise an exception, or return an object that is not a string. In the last two cases, it may seem counterintuitive to say that the program has not halted: after all, the program halts when it raises an exception or returns an object that is not a string. In these cases, it is better to think that the program has "frozen": it is not executing more code, but it cannot terminate satisfactorily. In this sense, the program "has not halted".

We are now in a position to present the formulation of the problem.

We ask whether this problem is decidable. The answer is negative, and expected given all the problems of this style that we have already proved undecidable (Problem 3.13, Problem 3.14, Problem 3.15).

import utilities
from universal_machine import universal_machine
 
def universal_machine_halting(encoded_input):
(program, input) = utilities.UAM(encoded_input)
output = universal_machine(program, input)
 
if output == 'yes':
return 'yes'        # halts
else:
utilities.loop_forever()  # loops forever

import utilities
from halts import halts  # oracle
 
def universal_to_halting(program, input):
encoded_input = utilities.MAU(program, input)
universal_machine_halting = utilities.read('universal_machine_halting.py')
 
return halts(universal_machine_halting, encoded_input)

In the previous proof we used a new technique: creating a new program from another. Specifically, we modify Listing 3.2, the universal machine in Python that we introduced in Section 3.2, to create a universal machine that halts for positive outputs and loops for any other output.

Next, we will introduce a new halting problem, simpler than the $\textsc{Halts}$ problem already stated.¹⁵

Since it is a "simpler" problem, it need not initially be undecidable. To prove it, we must perform a "trick": ignore the input.

import utilities
from universal_machine import universal_machine
 
def ignore_input(ignored_input):
program = utilities.read('disk/program.txt')
input_str = utilities.read('disk/input.txt')
return universal_machine(program, input)

For this, we use Listing 3.11. This program, instead of executing the input ignored_input, executes the universal machine on a program and an input stored on disk. Specifically, it uses as program the one stored in disk/program.txt, and as input the one stored in disk/input.txt.

Once we know how ignore_input.py works, it is straightforward to find a reduction of $\textsc{Halts}$ to $\textsc{HaltsOnEmpty}$.

import utilities
from halting_on_empty import halting_on_empty  # oracle
 
def halting_to_halting_on_empty(program, input):
utilities.write('disk/program.txt', program)
utilities.write('disk/input.txt', input)
 
return halting_on_empty(utilities.read('ignore_input.py'))

To conclude, we introduce a prediction task: $\textsc{GuessConsistent}$.¹⁶

Unlike an ordinary decision problem, this task does not specify a unique correct answer for every input: either answer is allowed for a looping program. We seek a total computable predictor that agrees with every program that does halt. Even with this freedom, no such predictor exists.

import utilities
from guess_consistent import guess_consistent  # assumed total predictor
 
def modify_guess_consistent(program):
utilities.write('disk/program.txt', program)
utilities.write('disk/input.txt', program)
 
output = guess_consistent(utilities.read('ignore_input.py'))
 
if output == 'yes':
return 'no'
else:
return 'yes'

The decision problem $\textsc{HaltsOnEmpty}$ and the prediction task $\textsc{GuessConsistent}$ will be central to the proof of two variants of the main result of this work, in Chapter 5. As a summary, the table below is provided with all the problems presented in this chapter.

3.7 #Summary