Why is the Turing Machine a popular model of computation?

Question

I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we consider a "tape", and a machine head writing symbols, changing state, shifting the tape back and forth?

What is the underlying significance? A DFA is elegant - it seems to capture precisely what is necessary to recognize the regular languages. But the Turing machine, to my novice judgement, is just a clunky abstract contraption.

After thinking about it, I think the most idealized model of computation would be to say that some physical system corresponding to the input string, after being set into motion, would reach a static equilibrium which, upon interpretation equivalent to the the one used to form the system from the original string, would correspond to the correct output string. This captures the notion of "automation", since the system would change deterministically based solely on the original state.

Edit:

After reading a few responses, I've realized that what confuses me about the Turing machine is that it does not seem minimal. Shouldn't the canonical model of computation obviously convey the essence of computability?

Also, in case it wasn't clear I know that DFAs are not complete models of computation.

Thank you for the replies.

Answer 1

Well, a DFA is just a Turing machine that's only allowed to move to the right and that must accept or reject as soon as it runs out of input characters. So I'm not sure one can really say that a DFA is natural but a Turing machine isn't.

Critique of the question aside, remember that Turing was working before computers existed. As such, he wasn't trying to codify what electronic computers do but, rather, computation in general. My parents have a dictionary from the 1930s that defines computer as "someone who computes" and this is basically where Turing was coming from: for him, at that time, computation was about slide rules, log tables, pencils and pieces of paper. In that mind-set, rewriting symbols on a paper tape doesn't seem like a bad abstraction.

OK, fine, you're saying (I hope!) but we're not in the 1930s any more so why do we still use this? Here, I don't think there's any one specific reason. The advantage of Turing machines is that they're reasonably simple and we're decently good at proving things about them. Although formally specifying a Turing machine program to do some particular task is very tedious, once you've done it a few times, you have a reasonable intuition about what they can do and you don't need to write the formal specifications any more. The model is also easily extended to include other natural features, such as random access to the tape. So they're a pretty useful model that we understand well and we also have a pretty good understanding of how they relate to actual computers.

One could use other models but one would then have to do a huge amount of translation between results for the new model and the vast body of existing work on what Turing machines can do. Nobody has come up with a replacement for Turing machines that have had big enough advantages to make that look like a good idea.

Answer 2

You are asking several different questions. Let me briefly answer them one by one.

What is so important about the Turing machine model?

During the infancy of computability theory, several models of computation were suggested, in various contexts. For example, Gödel, who was trying to understand to which proof systems his incompleteness theorem applies, came up with the formalism of general recursive functions, and Church came up with the $\lambda$ calculus as an attempt at paradox-free foundations for mathematics. Turing himself was motivated by a problem of Hilbert, who asked for a "purely mechanical process" for determining the truth value of a given mathematical statement.

At the time, Turing's attempt at defining computability seemed as the most satisfactory. It eventually turned out that all models of computation described above are equivalent – they all describe the same notion of computability. For historical reasons, Turing's model came out as the most canonical way of defining computability. The model is also very rudimentary and so easy to work with, compared to many other models including the ones listed above.

The usual computer science teaches Turing machines as the definition of computability, and then uses them also to explore complexity theory. But algorithms are analyzed with respect to a more realistic model known as the RAM machine, although this issue is usually swept under the carpet as a secret for the cognoscenti.

Aren't DFAs a better model?

This was the original motivation behind Rabin and Scott's famous paper, Finite automata and their decision problems:

Turing machines are widely considered to be the abstract prototype of digital computers; workers in the field, however, have felt more and more that the notion of a Turing machine is too general to serve as an accurate model of actual computers. It is well known that even for simple calculations it is impossible to give an a priori upper bound on the amount of tape a Turing machine will need for any given computation. It is precisely this feature that renders Turing's concept unrealistic.

In the last few years the idea of a finite automaton has appeared in the literature. These are machines having only a finite number of internal states that can be used for memory and computation. The restriction of finiteness appears to give a better approximation to the idea of a physical machine. Of course, such machines cannot do as much as Turing machines, but the advantage of being able to compute an arbitrary general recursive function is questionable, since very few of these functions come up in practical applications.

It turned out, however, that whereas Turing machines are too strong, DFAs are too weak. Nowadays theoreticians prefer the notion of polynomial time computation, though this notion is also not without its problems. That said, DFAs and NFAs still have their uses, chiefly in compilers (used for lexical analysis) and network devices (used for extremely efficient filtering).

Isn't the Turing machine model too limited?

The Church–Turing thesis states that Turing machines capture the physical notion of computability. Yuri Gurevich has led an attempt at proving this thesis, by formulating a more general class of computation devices known as abstract state machines and proving that they are equivalent in power to Turing machines. Perhaps these machines are analogous to your idealized model.

Answer 3

The underlying significance is about the idea of Turing-equivalence. The exact model isn't important, as long as it is Turing-equivalent. But it's better to use a simpler model so you could prove equivalence to other models easier.

More exactly, it's better to make it easier to simulate this model in other models, as we know most of the advanced programming languages are Turing-equivalent (with certain assumptions about memory addresses) and can be used to simulate other models.

There are other models, such as the lambda calculus and (string rewriting) grammars. But it's easier to define time and space constraints in a Turing machine. You could also use a programming language such as Brainfuck, but it requires unnecessary work to for example redefine the symbols to get a logically trivial modification sometimes.

So, the Turing machine seemed to be quite appropriate to me if you have to learn a single model for everything. But if you are going to learn multiple models anyway, I see nothing wrong to learn lambda calculus for the idea of Turing-equivalence, Brainfuck for proving other models Turing-equivalent, and practical programming languages (better with accessible stack and no hidden variables) for time / space constraints, and only consider the Turing machine a tool to prove these things equivalent if nobody is bothered to find a way around it. This naturally happens if you didn't start with learning the underlying theory first, but only did it when you found them useful.

Answer 4

I'd like to respond to this part of the question, added in an edit:

"Shouldn't the canonical model of computation obviously convey the essence of computability?"

One of the remarkable things that Turing did in his original paper -- the one which introduced what we now call "Turing machines" -- was that he constructed a single Turing machine that can simulate every other Turing machine. Once this "universal Turing machine" is built, it works by making an input tape which has two independent features: first, an encoding of the Turing machine $T$ that one wishes to simulate; then, a copy of the input tape that one would have inserted into the Turing machine $T$, if one happened to have $T$ sitting around. In semimodern jargon: first, one inserts a program which the universal Turing machine compiles; then, one inserts the input which the universal Turing machine runs using the compiled program.

That's one of the essences of computability: Whatever general notion of computability one has in mind, there should be a single machine which does it all. That's exactly what a universal Turing machine does. It's also what modern computers do (subject to the physically unrealistic idealization of having infinite memory).

Another way of putting this, which directly addresses your concern that Turing machines are not minimal, is that they are just as minimal as they can be, subject to the requirement that they describe a general notion of computability for which there exists a universal machine.

Answer 5

Turing Machines are not meant to be used literally; programming in them is something one would only do once as an exercise, to understand how they work.

They are specifically not made to "do" anything. They do not need to be minimal, they do not need to be comfortable to work with.

They are simply a model of a machine you could build, which would be as expressive and powerful as any other machine you could ever build in the physical universe (as far as we know today).

They were defined by Turing the way they are for these main reasons:

• To be able to prove that they encompass any and all algorithm we could ever think of.
• To work on the halting problem / decision problem.
• To be able to reduce any other machine/language to this one.

Would it have been possible to pick another language? For sure! Any of the turing complete languages we know today could have been used. But it would have been much harder to build the theoretical groundwork on a more complex machine.

I would argue that they are not even a "popular model of computation"; nobody would ever compute anything with a Turing Machine. It is a purely theoretical concept, made by theoretic computer scientists, for t.c.s's.

Answer 6

Why is it popular, maybe the most popular? You must remember that Turing inevented this "machine" a lot of years before electronic computers. The TM is operated with a paper, a pen, a rubber and last but not least, a human brain. So everybody is able to run a "computation" with this machine. Everybody means a person who never learned computers, programming langages. It is simple to use. When you think it about, you discover a paradox: this machine is a assembly of almost nothing but you can operate everything. To my opinion the paradox of "almost-nothing/versus/everything" is the reason why it is popular. I would notice that the TM does not explicitly explain recursion, teh TM only deals with "jump". That feature (explicitly talking about recursion) may be a source of headhache for rookies, for instance in lambda-calculus the concept of Y-combinator is almost un-understandable; More precisely, the TM is popular because the paradox of "almost-nothing/versus/everything" without the recursion headhache.