# 2 Decidability and enumerability

Here we go over some basic notions that will be crucial later.

## 2.1 Functions

As I imagine anyone reading this is aware (although it’s totally cool if you’re not… that’s why it’s called learning), a function $f:\Delta\rightarrow\Gamma$ is a rule $f$ that takes something from its domain $\Delta$ and turns it into something from its co-domain $\Gamma$. We will be dealing exclusively with total functions, which means that $f$ is defined for every element in $\Delta$. Or, more plainly, we can use anything in $\Delta$ as an argument for $f$ and have it make sense. This is contrasted with the notion of partial functions, which can have elements of the domain that $f$ isn’t designed to handle. We will not be using partial functions at any point in this book (or so it promises).

So, given a function $f:\Delta\rightarrow\Gamma$, some definitions:

The range of a function is the subset of the $\Gamma$ that $f$ can possibly get to from elements of $\Delta$, ie: $\{f(x)|x\in\Delta\}$. In other words, the range is the set of all possible outputs of $f$.

$f$ is surjective iff for every $y\in\Gamma$ there is some $x\in\Delta$ such that $f(x)=y$. Equivalently, $f$ is surjective iff every member of its co-domain is a possible output of $f$ iff its co-domain and its range are identical. This property is also called onto.

$f$ is injective iff for it maps every different element of $\Delta$ to a different element of $\Gamma$. Equivalently, $f$ is injective iff $x\neq y$ implies that $f(x)\neq f(y)$. This property is also called one-to-one because it matches everything with exactly one corresponding value.

$f$ is bijective iff it is both surjective and injective. Because $f$ is defined for every element of $\Delta$ (total), can reach every member of $\Gamma$ (surjective) and matches each thing to exactly one other thing (injective), an immediate corollary of this is that $\Delta$ and $\Gamma$ have the same number of elements. This is an important result that we will use quite often when discussing enumerability.

## 2.2 Effective decidability, effective computability

Deciding is the idea of determining whether a property or a relation applies in a particular case. For example, if I ask you to evaluate the predicate “is red” against the term “Mars”, you would say yes. If I gave you the predicate “halts in a finite number of steps” to the computer program $\texttt{while (true);}$ you would probably say no. In either case you have just decided that predicate.

Computing is the idea of applying a function to an argument and figuring out the result is. If I give you the function $f(x)=x+1$ and the argument $x=3$ you would compute the value $4$. If I give you the function $f(x)=\text{the number of steps a computer program }x\text{ executes before halting}$ to the argument of the same computer program as above, you would conclude that the result is infinite. In both cases you have just computed that function.

What effectiveness comes down to is the notion of whether something can be done by a computer. Effective decidability is the condition that a property or relation can be decided by a computer in a finite number of operations. Effective computability is the condition that the result of a function applied to an argument can be calculated by a computer in a finite number of operations. For each notion, consider the two sets of two examples above. In each, the first is effectively decidable/computable and the second is not, for reasons I hope will eventually be clear.

This raises an obvious questions: what is a computer? Or, more to the point, what can computers do exactly? For our purposes we will be using a generalized notion of computation called a Turing machine (named for their inventor, Alan Turing). Despite its name, a Turing machine is not actually a mechanical device, but rather a hypothetical one. Imagine you have an infinite strip of tape, extending forever in both directions. This tape is divided up into squares, each square containing either a zero or a one. Imagine also that you can walk up and down and look at the square you’re standing next to. You have four options at this point (and can decide which to do take based on whether you’re looking at a zero or a one, as well as a condition called the “state” of the machine): you can either move to the square to your left, move to the square on your right, change the square you’re looking at to a zero, or change it to a one. It may surprise you, but the Turing machine I have just described is basically a computer, and can execute any algorithm that can be run on today’s state-of-the-art machines.

In fact, throughout the history of computability theory, whenever a new model has been developed of what could be done algorithmically by a computer (such as $\lambda$-calculus, $\mu$-calculus, and even modern programming languages) it has turned out that each of these notions were equivalent to a Turing machine, as well as each other. Thus, Alan Turing and Alonzo Church separately came up with what is now called the Church-Turing thesis (although the book only deals with Turing, hence “Turing’s thesis”):

Turing thesis: the numerical functions that are effectively computable in an informal sense (ie: where the answer can be arrived at by a step-by-step application of discrete, specific numerical operations, or “algorithmically”)  are just those functions which are computable by a properly programmed Turing machine. Similarly, the effectively decidable properties and relations are just the numerical properties and relations which are decidable by a suitable Turing machine.

Of course we are unable to rigorously define an “intuitive” or “informal” notion of what could be computed, so Turing’s thesis could never be formally proven, however all attempts to disprove it have been thoroughly rebuked.

You might wonder, however, about just how long it might take such a simple machine to be able to solve complex problems. And you would be right to do so: Turing machines are notoriously hard to program, and take an enormous number of steps in order to solve most interesting problems. If we were to actually use such a Turing machine to try and get a useful answer to a question (as opposed to, say, writing a C++ program) it could very realistically take lifetimes to calculate. By what right, then, do we call this “effective”? Another objection to be raised might have to do with the idea of an infinite storage medium, which violates basic engineering principles of modern computer architectures.

Both of these objections can be answered at once: when we discuss computability, we are not so much interested in how practical it is to run a particular program. What interests us is to know what is computable in principle, rather than in practice. The reason for this is simple: when we discover a particular problem that cannot be solved by a Turing machine in a finite number of steps, this result is all the more surprising for the liberal attitude we’ve taken towards just how long we will let our programs run, or how much space we will allow them to take up.

One final note in this section. The way we’ve defined Turing machines, they operate on zeroes and ones. This of course reflects how our modern computers represent numbers (and hence why the Turing thesis refers to “numerical” functions, properties and relations). So how then can we effectively compute functions or decide properties of other things, such as truth values or sentences? This is simple. We basically encode such things into numbers and then perform numerical operations upon them.

For example, most programming languages encode the values of $\texttt{True}$ and $\texttt{False}$ as $1$ and $0$, respectively. We can do the same thing with strings. An immediate example is ASCII encoding of textual characters to numeric values which is standardized across virtually all computer architectures. Later in the book we will learn another, more mathematically rigorous way to do the same.

The rest of this chapter is about the enumerability and effective enumerability of sets, but I’m going to hold off on talking about those until next time.