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: (more…)