Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
2  
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 at 14:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.