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 . 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
, 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 , which is always finite: outside of a finite number of positions, the string
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 consisting of two equal positive integers expressed in decimal form, separated by a comma. I will informally describe a Turing machine
to decide this language.
Step 1: checks that there is rpecisely one comma in the input string. If there is more than one comma, rejects.
Step 2: 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.)
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 , 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 . A Turing machine with inputs in
can be represented as a string in the language
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
of
will do for every Turing machine in
. Then each Turing machine is represented by a string in
. Or, better yet, we can just use the language
(provided it has at least two letters) by using
-tuples of letters of
to correspond to letters of
.
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
where
is a Turing machine that halts on
(over some fixed alphabet). This is undecidable.
The proof is an elegant self-referential argument. Let be a Turing machine that, given the input
, decides whether
halts on
. We will construct a contradiction.
Now define the modification of
. Given the input
, it first runs
to decide whether
halts on its own description
(i.e. runs
on
). If
accepts, then
goes into an infinite loop. If
rejects,
accepts.
So, the upshot is that halts on
if and only if
does not halt on
.
Taking , it follows that
halts on
iff
does not halt on
. 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 . 1) Test whether there is a solution of
among
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.
April 18, 2010 at 9:35 pm
GILA has become math blog lingo? That’s news to me 😛
April 22, 2010 at 5:00 am
Hmm… this is offkey,
but this will belong from a generally curious lay audience… !
You know how an arc of a circle subtends on the circumference, half the angle it subtends at the centre.
What is your take on solid angles? Do they follow the same property?
Or is it blasphemy to define ‘solid angles’ that way.
If so what would be the 3D invariant that obeys the above property of ‘2D’ (say instead of solid angle another well-defined measure based on geometry)
Bye
April 22, 2010 at 5:56 pm
Hm, I think it should be one-fourth though. I think the justification of the geometric fact in two dimensions you mentioned follows from the fact that the circumference of a circle is proportional to the radius (because the angle can be defined as the ratio of the arc subtended to the whole circle; apparently this is the only way to define solid angles). By contrast the area of the sphere is proportional to
. That said someone who actually knows geometry may want to correct me if I am saying something silly.
April 24, 2010 at 12:35 am
Thanks…
Hm, I think I am not convinced yet.
Let us take a specialized case.
The semicircle : 180* (asterisk for degree) at the centre i.e. straight line / diameter and 90* anywhere inside.
The hemisphere : solid angle of 2*pi at the centre AND SOLID ANGLE OF PI/2 on the surface?
How do we confirm this?
Trying to uncover this mine, I hit on an interesting thing… You know how we know the angles of a triangle sum up to 180 degrees.
Wonder what it is for the 4 solid angles for a tetrahedron… they don’t sum up to a constant.
Solid angles are different!
April 24, 2010 at 6:09 pm
Hm, perhaps you’re right – I see that my reasoning only works when the point for the angle is chosen to be in a particularly convenient location. Sorry I can’t be more helpful; I must have missed out on this bit of mathematical lore (and should probably pick it up whenever I find a book on geometry that I like).
April 24, 2010 at 12:53 am
In retrospect, the thing about tetrahedra isn’t special, any crystallographer would tell you that, but proving it out is probably cute.
There should be a family of tetrahedrons with that special property though (solid angles sum to a constant).
There’s a buzz about tetrahedral packing too… http://arxiv.org/abs/1001.0586
http://www.ams.org/news/math-in-the-media/mmarc-02-2010-media