I’ve decided to bow to imaginary public pressure and do a post in a different vein, which should be accessible to anyone, and which will belong to my own GILA—for those not immersed in the know of math blog lingo, that’s generally interested lay audience—series. (OK, so I just have a new interest and need some excuse for breaking my previous promises.) So, we’re going to do a bit of theoretical computer science.

Turing machines

For theoretical computer science, we need a notion of an algorithm. One could readily agree that adding two decimal numbers via the elementary school procedure, sorting integers via mergesort, and the sieve of Eratosthenes are all algorithms. In particular, anything that can be written in a programming language should qualify as one. However, this intuitive notion needs to be made precise if one wishes to use it in a mathematical sense.

It is widely agreed (the Church-Turing thesis) that the appropriate notion of algorithm is given by Turing-computability.

First of all, we will describe what a problem is. To us, it will be represented simply as a string of characters belonging to a fixed finite alphabet {\mathcal{A}}. For instance, there is the problem of testing whether two integers are equal can be represented as follows one has a string over the alphabet {\{0,1,\dots, 9\} \cup \{,\} \cup \{blank\}}, where the separator {,} is used to separate the two integers. Then, the (rather trivial) problem of testing whether two integers are equal becomes a question about whether a certain string has a certain property. Or, equivalently, whether it belongs to a certain language, which is a collection of strings over a fixed alphabet. In practice, we will generally speak of languages rather than problems.

A Turing machine is a device used to simulate an algorithm. Informally, a Turing machine has the following parts:

1) A finite set of states

2) Designated start states, reject, and accept states. This says where to start and whether the Turing machine says “yes” or “no.”

We also need a way for the machine to interact with the input. One should think of the input as being represented on a doubly infinite tape on which the Turing machine is attached. It has a way from moving between cells of this tape, though it can only read and write on the cell it is currently on.

3) A transition function that, to a state and a character in the tape alphabet (which may be larger than, but always at least contains, the alphabet of the input strings) yields a new state and a direction (left or right), and an output character

Here’s how a Turing machine behaves upon receiving an input string {s \in \mathcal{A}^{\mathbb{Z}}}, which is always finite: outside of a finite number of positions, the string {s} ihas blank symbols. It starts in the start state on the initial character. Then, on each step, it uses the transition function to decide what its new state is going to be and whether it moves left or right. It uses the transition function to change the character on the old square as well.

If the Turing machine ever reaches the accept state, we say that it accepts; if it reaches the reject state it rejects; otherwise it loops forever.

So, notice that a Turing machine is finitistic: its memory is contained in the finite set of states that it has. However, it can write (and consequently store information) on the tape that it can access. In this way the Turing machine has a way of storing arbitrarily large quantities of information that it can access over time; in this way it differs from a finite automaton.

Now, let’s relate the concept of a Turing machine to problems, whcih we phrase as languages. A language is Turing decidable if there is a Turing machine that accepts all strings in the language and rejects all strings not in the language. (Note that the Turing machine is not allowed to loop forever on anything.)

Here is an example of a Turing machine. Consider the language {L} consisting of two equal positive integers expressed in decimal form, separated by a comma. I will informally describe a Turing machine {M} to decide this language.

Step 1: {M} checks that there is rpecisely one comma in the input string. If there is more than one comma, rejects.

Step 2: {M} finds the first character before the comma, and crosses it off but remembers it. (Remember, it does have a fixed finite memory, but this memory can be chosen arbitrarily large at the outset.) {M} finds the first character after the comma and tests if they are the same. If not, reject. If yes, cross this one off and keep going.

Step 3: At each point, find the first uncrossed character before the comma, cross it off, and remember it. Find the first uncrossed character after the comma, cross it off, and compare with the previous one. If unequal, reject. If equal, repeat.

Step 4: If not rejected after everything is crossed off, accept.

It’s very easy to see that all this can ber done by a Turing machine, though I’m not a masochist and will not actually write out the states and transition function. Note that I let the Turing machine “cross off” letters; as we said, it’s allowed to use a larger (but fixed) tape alphabet than the original input alphabet. (One doesn’t actually have to extend the tape alphabet provided one isn’t working with some trivial alphabet, but this is not the point.)

Admittedly, this was rather uninteresting. Nevertheles, this language cannot be defined by a finite automaton: this is an easy application of the pumping lemma, and is left as an exercise.

Unsolvable problems

So, we saw an example of how Turing machines are quite a bit more powerful than finite automata, and how they can be described. But, in fact, not every language is Turing decidable. In fact, a language was simply defined as a subset of the set of strings over the alphabet {\mathcal{A}}, and there are uncountably many of them. By contrast, a Turing machine is finistic in nature, and one easily sees that there are countably many of them. As a result, there are Turing-undecidable languages.

We can actually exhibit one though. Fix an alphabet {\mathcal{A}}. A Turing machine with inputs in {\mathcal{A}} can be represented as a string in the language {\mathcal{A}} augmented by a fixed number of symbols (e.g. symbols to designate that something is a state, a symbol for left, right, etc.). If we number each of the states decimally, one finite extension {\mathcal{B}} of {\mathcal{A}} will do for every Turing machine in {\mathcal{A}}. Then each Turing machine is represented by a string in {\mathcal{B}}. Or, better yet, we can just use the language {\mathcal{A}} (provided it has at least two letters) by using {k}-tuples of letters of {\mathcal{A}} to correspond to letters of {\mathcal{B}}.

This is sort of a technical point that I don’t want to get hung up on, but it is more generally possible to represent programs via their Godel numbering: each program corresponds to a unique natural number.

Theorem 1 Consider the language consisting of all {(M, w)} where {M} is a Turing machine that halts on {w} (over some fixed alphabet). This is undecidable.

 

The proof is an elegant self-referential argument. Let {N} be a Turing machine that, given the input {M,w}, decides whether {M} halts on {w}. We will construct a contradiction.

Now define the modification {N'} of {N}. Given the input {M}, it first runs {N} to decide whether {M} halts on its own description {M} (i.e. runs {N} on {M,M}). If {N} accepts, then {N'} goes into an infinite loop. If {N} rejects, {N'} accepts.

So, the upshot is that {N'} halts on {M} if and only if {M} does not halt on {M}.

Taking {M = N'}, it follows that {N'} halts on {N'} iff {N} does not halt on {N'}. This is absurd, and a contradiction. Consequently the halting problem is unsolvable.

If the halting problem were solvable, and we had an algorithm to solve it, we could decide whether Fermat’s last theorem is true by testing whether the following program halts:

Let {N=1}. 1) Test whether there is a solution of {x^n+y^n=z^n} among {1 \leq x,y,z \leq N, 3 \leq n \leq N}

2) If there is, break and halt

3) If not, go back to step 1

So, there’s GILA 1. There will be more to come.