Practical importance of Turing machines?

Question

I am an electrical engineer, and only had one CS course in college 26 years ago. However, I am also a devoted Mathematica user.

I have the sense that Turing Machines are very important in computer science. Is the importance only in the theory of computer science? If there are practical implications/applications what are some of them?

Answer 1

The importance of Turing machines is twofold. First, Turing machines were one of the first (if not the first) theoretical models for computers, dating from 1936. Second, a lot of theoretical computer science has been developed with Turing machines in mind, and so a lot of the basic results are in the language of Turing machines. One reason for this is that Turing machines are simple, and so amenable to analysis.

That said, Turing machines are not a practical model for computing. As an engineer and a Mathematica user, they shouldn't concern you at all. Even in the theoretical computer science community, the more realistic RAM machines are used in the areas of algorithms and data structures.

In fact, from the point of view of complexity theory, Turing machines are polynomially equivalent to many other machine models, and so complexity classes like P and NP can equivalently be defined in terms of these models. (Other complexity classes are more delicate.)

Answer 2

Turing machines were one of the early models for computation, that is they were developed when computation itself was not understood very well (around 1940). I want to focus on two aspects that (arguably) led to them being the preferred model back then, which led to being the most established and therefore eventually standard model.

1. Simplicity of proofs
   As a theoretic model, Turing machines have the charme of being "simple" in the sense that the current machine state has only constant size. All the information you need in order to determine the next machine state is one symbol and one (control) state number. The change to the machine state is equally small, adding only the movement of the machine head. That simplifies (formal) proofs considerably, in particular the number of cases to be distinguished.

   Compare this aspect with the RAM model (when not used in its minimalistic form): the next operation may be any of several operations, which may access any (two) registers. There are also multiple control structures.

2. Runtime and space usage
   There were (only) two major models of computation which emerged almost simultaneously with Turing Machines, namely Church's $\lambda$-calculus and Kleene's $\mu$-recursive functions. They answered the same question Turing did -- Hilbert's Entscheidungsproblem -- but lend themselves far less easily (if at all) to defining runtime and space usage. In a sense, they are too abstract to be thus related to more realistic machine models.

   For Turing machines, however, both notions are easily defined (and were in Turing's very first paper on his model, if I remember correctly). Since considerations of efficiency were soon very important for actually doing stuff, this was a definite advantage of Turing machines.

Thus, Turing machines have been established as the model of computation, which could be seen as a combination of historical "accident" and some of its key properties. Nevertheless, many models have been defined since and are avidly used, in particular in order to overcome the shortcomings of Turing machines; for instance, they are tedious to "program" (i.e. define).

I am not aware of any direct applications in practice. In particular, the practice of computation evolved in parallel to (and, in the beginning, mostly independently of) the theory of computation. Programming languages were developed without formal machine models. However, it is clear (in hindsight) that many advances in the practice of computation were enabled by theory.

Furthermore, keep in mind that the value a theoretical concept has had for practice should be measured by considering all descendants, that is follow-up work, results and new ideas made possible by that concept. And in that regard, I think it is fair to say that the concept of Turing machines (among others) has revolutionised the world.

Answer 3

The only reasonably practical application I can think of (in the sense that you might actually implement a Turing machine) is to prove that a language of some sort has sufficient power.

If you're designing some kind of programming language (or anything else that is meant to compute things), then you may want to ensure that it is Turing-complete (ie. capable of computing anything that is computable) by implementing a Turing machine in it.

Of course, you could also implement anything else that is Turing-complete (like C or combinatory logic), but sometimes a Turing machine is the easiest option.