# Practical importance of Turing machines?

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?

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.)

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.

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.

Turing machine is a mathematical model of computation. Its benefits are :-

1. Check Decidability If TM cannot solve a problem in countable time then there could not be any algorithm which could solve that problem (That is the problem is undecidable).

For a decision problem if its TM halt in countable time for all finite length inputs then we can say that the problem could be solved by an algorithm in countable time.

2. Classify Problem TM helps to classify decidable problems into classes of Polynomial Hierarchy.

Suppose we found that the problem is decidable. Then out target become how efficiently we can solve it. The efficiency been calculated in number of steps, extra space used , length of the code/size of the FSM.

3. Design and Implement Algorithm for Practical Machines TM helps to propagate idea of algorithm in other practical machines. After the successful check of 1,2 criteria we can use our practical devices/computers to design and implement algorithm.

• Turing machines do not let you "check decidability"; they just give a definition of what decidability is. Classification of problems is perfectly possible using other models of computation, such as random access machines. Algorithms that work on Turing machines are rarely suited to other machine models, since Turing machine algorithms involve large amounts of tape-shuffling that doesn't occur elsewhere. – David Richerby Dec 24 '13 at 13:40
• TM gives definition of decidablity. Right. To check decidablity are we not take help of TM? "Classification of problems is perfectly possible using other models of computation." Right but we can also do it using TM. While implementing algorithm you have to be certain about the hardness of that problem. – Subhankar Ghosal Jan 25 '14 at 14:02

Turing machines are good mind exercise with little practical use. There is no harm in not having one. All applications of a Turing machine are either intuitive or a matter of religion because they cannot be proved or refuted.

• "All applications of a Turing machine are either intuitive or a matter of religion [...]" And, thus, the entire fields of computability theory and complexity theory were dismissed in fourteen words. – David Richerby Jun 3 '15 at 11:53
• These was not aimed to dismiss those theories. All I was saying was that the applications of a Turing machine are either obvious, can be understood intuitively or require belief without proves. – Valery Gavrilov Oct 22 '15 at 1:59
• "a matter of religion because they cannot be proved or refuted." Um, what? The most generous interpretation of this I can cook up is that you're referring to the Church-Turing thesis, but every specific application of this can indeed be proven (just go through the tedious work of designing the appropriate Turing machine; or, just write an appropriate algorithm in your favorite programming language and use the usual equivalence), and CT isn't an application, just a way of simplifying the exposition of proofs (and if one seriously doubts an application of it, one can always give a formal proof). – Noah Schweber Oct 22 '18 at 14:07
• Also I don't understand how "can be understood intuitively" is a drawback. All of mathematics can be understood intuitively; does that mean mathematics is just a mind exercise with little practical use? – Noah Schweber Oct 22 '18 at 14:08