Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
With all due respect to others that have answered this questions, I have found Turing Machines (and finite state machines in general) to be extremely useful throughout my career. Here are some points to ponder:
Numbers are "just symbols": In college, one of my assignments was to build a TM to add two decimal numbers. For me, this assignment was truly mind-blowing as it helped me get my head around the concept that numbers were just strings of symbols that could be manipulated.
Abstraction: I find that when thinking about an algorithm, I can abstract away syntax of programming languages and focus on the structure of the algorithm itself; things like loops, decisions (if/then), accumulators, etc.
Finite State Machines: I find that many kinds of problems can be thought of in terms of finite state machines and transitions. So I ask questions like: "What are all of the possible states?", "What are the conditions that must obtain to go from one state to another?"
Numbers are "just symbols" tell that to the ratio of the radius of a circle to the length of one side of an inscribed regular triangle.
$\endgroup$
Jan 4, 2020 at 19:10
Algorithmic randomness concepts and other concepts in algorithmic information theory (AIT) are defined primarily in terms of Turing machines. (If you look at the textbooks in this area by Li & Vitanyi, Calude, Nies, or Downey & Hirschfeldt, you will see that Turing machines are pervasive and central.)
Now, I am not aware that AIT has direct uses, in the sense that you can, say, use the theory of algorithmic randomness to build a random number generator, but the results in AIT show very clearly what you can't do--e.g. you can't define an algorithm that can generate an infinite sequence that is random in any ideal sense. AIT therefore constrains and clarifies what it is that practical algorithms can do. To give another example, it clarifies what you can know about the power of compression algorithms, which essentially exploit lack of randomness in the same way that AIT defines lack of randomness.
What I suspect is that in the past there would have been slower progress in understanding randomness in practical senses, and in file compression algorithms, without the clear conceptual framework provided by basic results and concepts in AIT--even though those results and concepts have no direct practical applications. That is speculation on my part, but there can be subtle and nonobvious but important ways that ideas influence the development of knowledge, and I suspect this is one area where that is true.
(For the record, I am at the level of an advanced beginning student of AIT who has also studied practical random number generation a bit, with a long history with various aspects of CS. There may very well be practical applications of AIT of which I am unaware. I have seen no evidence of that, though. (My primary area of expertise has more to do with the "development of knowledge" point I made in the preceding paragraph.))
Maybe it's also worth noting concerning Turing oracle machines--machines that are provided with a superior source of information to draw upon, an "oracle"--that a mathematician involved with Turing-machine related areas, Robert Soare, has suggested in a journal article that online databases are analogous to oracles. I still don't think that has practical applications, however, and I'm not sure the analogy is anything more than just an analogy.
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 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.
