Python is a Turing machine

The Turing machine, invented by Alan Turing in 1937², is a simple mathematical model that aims to represent the notion of an algorithm, which we discuss in detail in Section 2.2. This machine is one of the most relevant tools in computer science, since its simplicity allows powerful results to be obtained, such as the undecidability of the halting problem (Proposition 3.24), from which we can delve into the main question of our work: the incompleteness of mathematics. However, this formal power has a drawback, which we will see from a simple example (Example 2.11): defining simple programs in this model is complex and tedious.

This drawback is what motivates this chapter: in Section 2.3 we will prove the equivalence between computer programs (in our case, Python programs, which we explore in Section 2.1) and Turing machines. This will allow us to view a Python program as a representation of a Turing machine, eliminating the main drawback while retaining the mathematical power already mentioned.

It is important to emphasize that the results presented here are perfectly generalizable to any Turing-complete programming language. However, we chose to use this language for its ease of understanding and use.

Both the equivalence result we prove in this chapter and the observation above are especially interesting, as they bear a strong relation to the Church–Turing thesis, which we briefly discuss in Section 2.4.

2.1 #Python Programs

Python³ is a high-level, interpreted, object-oriented, open-source programming language, widely used today for a great variety of applications. One of its main characteristics is its readability and ease of use: anyone experienced in other languages will be able to understand and write Python programs with great ease.

Using Python, we can write a great variety of programs. For the purpose of our study, we focus on a specific class of programs: those that have exactly one character string as input and one character string as output. We call them SISO programs (from Single Input–Single Output; see Definition 2.2)⁴. Shortly, we will see that this class is not restrictive: these types of programs are as expressive as any other program. In fact, in this work we use the terms "program" and "SISO program" interchangeably, and in both cases we refer to a SISO-type Python program.

Note that in the previous definition a computer system $C$ is specified but not defined explicitly. We can think of $C$ as any computer system, with any software and hardware configuration, and with as much memory as necessary.

We may also ask what we mean when we refer to a program as "syntactically correct," since this will depend on several factors, such as the version of Python installed on $C$, as well as the operating system, architecture, etc. It is possible that a program runs on one system $C$ and fails or even produces a different output on another system $C'$. However, as we will see later, we use these programs as representations of Turing machines. The programs we present here are architecture- and memory-independent, and the proofs in this work are independent of all these characteristics.

We also need to define the output of a Python program.

In other words, the output of a program is the character string returned by its main function if it does so, and is undefined otherwise.

When defining the Python programs we use in this work, we focus on using character strings (also called strings) as input and output, and avoid using other Python objects that are not strings. Initially, we might think this imposes a limitation on the Python programs we can write, but this is not really the case. To see this, it suffices to observe that any object in Python can be properly encoded as a character string. There are native libraries that allow this, such as pickle.⁶ An example is shown in Program 2.1. The function function_with_encoded_object is a main function.

import pickle
from base64 import b64decode, b64encode
 
def function_with_encoded_object(encoded: str) -> str:
decoded = pickle.loads(b64decode(encoded.encode('ascii')))
return str(decoded)
 
adjacencies = {1: 2, 3: 4, 5: 3, 4: 2}
adjacencies_encoded = b64encode(pickle.dumps(adjacencies)).decode('ascii')
function_with_encoded_object(adjacencies_encoded)

pickle.dumps serializes the object to bytes, not to str. We use Base64 to encode those bytes as an ASCII string and decode them again before calling pickle.loads. The function also returns a string, so both its input and its output satisfy the SISO definition.

In summary, we have seen that the SISO condition for a Python program is not really a restriction. However, this class of problems will be very convenient for us, as we will see later.

2.2 #Turing Machines

Turing machines, first described by Alan Turing in 1936², are abstract and simple computational devices created to help investigate which problems can be computed. The "automatic machines"—as Turing called them in 1936—were specifically designed to compute real numbers. These machines were not named "Turing machines" until 1937, when Alonzo Church⁷ reviewed Turing's original publication. Today they are considered one of the fundamental models of computation theory, as they are the mathematical representation of an algorithm⁸.

Before understanding how these machines work, we need a few preliminary definitions.

The first definition presented by Turing in 1936² differs from the one in Definition 2.5. However, both are equivalent.

The above definition is somewhat abstract, and we can visualize it better in Figure 2.1. In it, we see the three "physical" parts of the machine: the control unit, the head, and the tape. The tape contains cells, each of which can store one symbol. Initially, the symbols are those of the input alphabet, but as the machine executes instructions the work alphabet can be used. These symbols include a blank symbol, denoted $\sqcup$, occupying all tape positions that do not encode the input word. The head can move left and right along the tape (or stay in place), informing the control unit of the symbols it reads. The symbol pointed to by the head is called the scanned symbol. The head can replace the scanned symbol with any other from the work alphabet, including the blank symbol. The control unit sends transitions to the head and changes between states based on the symbols read by the head.

It is important to clarify that a Turing machine does not really have any "control unit" or "head": it is a mathematical description. What we have done is provide an intuitive specification of how the algorithm represented by such a machine is executed.

To describe the machine at each moment, we need the concept of configuration.

All that remains is to specify the notion of "computation step" mentioned above. At each step, we apply a transition and change the configuration of the machine. This is what we call the computation process, which we formalize next.

In short, we see that the machine, depending on its current state and the scanned symbol, executes a certain transition defined in $\delta$, which tells it which state to move to, which symbol to replace the scanned one with, and which movement to perform on the tape.

An important note regarding undefined transitions. When describing a transition function, we define only the transitions for the states $q \in Q$ and symbols $b \in B$ for which they are defined. Otherwise, we may assume that $\delta(q, b) = \emptyset$. You can see this in Example 2.11, which we discuss in detail later.

We introduce a graphical notation for the transition function. We define it by means of a directed graph: we represent states as nodes (one for each state) and transitions as directed arcs.

The initial state is symbolized, in addition to the definition of the machine, by an arrow pointing to the state (it is not an arc, since it does not come from any node):

For each transition $\delta(q,b)=(p,c,M)$, we insert a directed arc connecting the nodes corresponding to states $q$ and $p$ as follows:

If we have several transition functions between the same two states ($\delta(q,b)=(p,c,M)$ and $\delta(q,b')=(p,c',M')$), we place several lines on the arc to symbolize this:

Finally, we also indicate final states by double-circling the node:

We observe that a Turing machine, given an input, can:

• halt and accept,
• halt and reject, or
• not halt (loop).

The machine halts when it reaches a configuration for which no transition is defined. When this happens, we can define an output from the symbols remaining on the tape.

Having defined which words a given machine accepts, we introduce the concept of language. A language is nothing more than a set of words.

Let us make all the concepts we have introduced precise through an example.

Once we have described precisely what a Turing machine is, we proceed to prove the most important result of this chapter (Theorem 2.23), which we anticipated in the introduction: the equivalence between the Turing machines just presented and the Python programs we defined in Section 2.1.

2.3 #Equivalence

Our goal now is to understand why Turing machines have the same computational power as Python programs. In other words, we want to show that the problems we can solve in both are the same.¹²

To prove the equivalence between both models of computation, we use the concept of simulation. It is common for different computational models to simulate one another. An example is the Java Virtual Machine (JVM), which is an abstract model capable of executing any Java program¹³. Another example is the Linux operating system, which can run the JVM. Therefore, a Linux computer can execute any Java program. This is possible through the chain of simulations:

We use the notation $A \leadsto B$ to indicate that $A$ simulates $B$. The fact that $A$ simulates $B$ simply means that it is possible to perform the computation procedure of $B$ using exclusively the computation procedure of $A$.

We proceed to prove the equivalence shown by means of the chain of simulations in Figure 2.6.

The work we do in this section is arduous, and we need to introduce several computational models to reach our goal. However, once we prove all the simulations, we will know that all of them are equivalent, and we can use whichever model we prefer as convenient.

The first computational model we study is obtained by adding more tapes and heads to the Turing machine we defined in Section 2.2¹⁴.

This definition is intuitive and expected. We simply incorporate more tapes and heads. From now on, we also use the term "single-tape Turing machine" to refer to the Turing machine we defined first.

One might think that these machines have more computational power than single-tape ones, but they are equivalent. It is evident that a multi-tape machine simulates a single-tape machine (Definition 2.5 is the same as Definition 2.12 for $k=1$). In Proposition 2.13 we see that the converse also holds.

The details of that construction — the work alphabet, the auxiliary states, and every clause of $\widetilde{\delta}$ — are as follows.