27
$\begingroup$

Recently in my CS class I've been introduced to the Turing Machine.

After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine.

I was completely unaware of the existence of computer tapes or how tapes and machines interacted until today. I still can't see why a machine would read tapes but a scanner is perhaps a closer conception to the Turing machine where paper is considered a tape and whatever goes inside of a scanner is whatever a Turing machine would do.

But in any case, isn't the idea of a Turing machine quite archaic? We have so many physical (rather than hypothetical) devices in our office or living room that seems to do what the Turing Machine does.

Can someone provide a better example drawing from reality so that the essential functionalities of this hypothetical conception is captured?

$\endgroup$
13
  • 1
    $\begingroup$ If you want to understand why a machine would read tapes, read up on the very early days of computing. E.g. you can see paper tapes in this photo of Colossus. $\endgroup$ Dec 3, 2014 at 10:05
  • 4
    $\begingroup$ Of course there are real Turing machines! Even one made out of Lego! $\endgroup$
    – john_leo
    Dec 3, 2014 at 11:20
  • 3
    $\begingroup$ Related question. Note that (finite) tapes where heavily used in computating until hard disks came along. $\endgroup$
    – Raphael
    Dec 3, 2014 at 11:54
  • 1
    $\begingroup$ The Chinese Room Argument (en.wikipedia.org/wiki/Chinese_room) might help with your understanding. I had the same issue with Touring machines when I first entered CS, and the Chinese Room was the bridge I needed to get there. Also, the point of a Tournig Machine is to allow mathematicians to continue proving interesting things about CS. Its not meant to be an actual computer. $\endgroup$ Dec 3, 2014 at 13:41
  • 3
    $\begingroup$ @slebetman This might be a a bit esoteric for someone just becoming familiar with Turing Machines, but the tape in a Turing Machine is not random-access; it's sequential access. It takes n shifts to get the head to a cell n spaces away. I mention this only because while the space of computable things doesn't change, the time needed to compute them does. Those kind of results (e.g., you can simulate a 2-tape machine with a 1-tape machine, you can simulate RAM with a 1-tape machine, etc., and with only polynomial time increase, etc.) are important exercises in computability courses. $\endgroup$ Dec 4, 2014 at 12:35

7 Answers 7

25
$\begingroup$

Turing machines are one of the "original" Turing-complete computation models, along with the $\lambda$ calculus and the recursively defined recursive functions. Nowadays in many areas of theoretical computer science a different model is used, the RAM machine, which is much closer to actual computers. Since both models are p-equivalent (they simulate each other with at most polynomial blow-up), from the point of view of questions like P vs. NP, both models are equivalent.

$\endgroup$
42
$\begingroup$

AFAIK the Turing Machine is modeled on the idea of a human with a pen and paper. The human has a certain state in the brain, looks at the paper like the machine looks at the tape, and writes something on the paper or moves to look at a different place, just as the machine does.

TM is archaic as Peano natural number arithmetic. TM is useless for practical computation, and it is of course not intended to be used for that. It is just a simple way to axiomatize computation so we can reason about what's computable and what isn't - just as Peano arithmetic is useful for defining from first principles what natural numbers are, and what are their properties - but it would be ridiculous to try to do arithmetic by manipulating Peano numbers by hand according to the theoretical definitions.

Just think how difficult it would be to prove different theorems from complexity and computability theory (e.g. prove that the Halting Problem is undecidable), if you had to prove them using the semantics of the C++ programming language instead of the Turing Machine. Your proofs would be ridiculous or impossible - as ridiculous as proving associativity of natural number multiplication by using the grade-school method applied to decimal integers as your definition of what multiplication is.

$\endgroup$
2
  • 6
    $\begingroup$ Nice answer. In Turing's original paper he even derived his definition of the machine from how a human would compute something. $\endgroup$
    – john_leo
    Dec 3, 2014 at 11:24
  • 1
    $\begingroup$ Re: C++, this may amuse: port70.net/~nsz/c/c%2B%2B/turing.pdf $\endgroup$ Dec 4, 2014 at 16:10
10
$\begingroup$

Imagine a newcomer to geometry asking:

Is there a physical analogy to the triangle?

Isn't the idea of a triangle quite archaic? We have so many physical (rather than hypothetical) shapes in our office or living room that seem to do what the triangle does.

What would you answer?

You might say that these questions reveal two fundamental misconceptions about triangles:

  1. "Triangles are purely hypothetical." Wrong! While they are mathematical entities, Platonic ideals, and hypothetical in that sense, triangles are real: we can actually construct them in the real world. Granted, what we construct will never be a perfect triangle, but our mathematical theory about them does apply to the real world, the laws we can derive do apply to shapes in the real world, the theory can be used as a basis for designing, constructing and measuring shapes in the real world; this is the reason the theory was developed in the first place.
  2. "Triangles are useless because they don't describe the shapes we normally use." Wrong! Describing actual shapes you find in the real world is not their purpose. If your whole office or living room doesn't contain a single triangle, that doesn't mean the concept of triangle is unrealistic or outdated and had better be replaced with something else. Their main purpose is as an elementary construct from which all more complex shapes can be constructed in principle - and for which we can therefore derive laws that apply to shapes in general. Reasoning about triangles allows us to reason about shapes in general. Your living room is subject to the same laws that we have derived for triangles, and our knowledge of these laws was used, directly or indirectly, to construct it. The living room probably doesn't have a single triangle in it, let alone a perfect one, but we don't care about finding triangles there; we can, however, build a description of the shapes in there by approximating them with triangles, and this - triangulation - is a popular and useful thing to do. So triangles are building blocks to help us think about shapes in general.

The same is true for Turing machines.

It's been so long since I was introduced to geometry, I really can't recall whether any newcomer actually has these misconceptions about triangles. But when it comes to Turing machines, I encounter these misconceptions all the time. So often, in fact, that there seems to be something fundamentally wrong with how they are usually taught. Perhaps a show and tell approach is in order!

So, for the sake of completeness:

  1. "Turing Machines are purely hypothetical." Wrong! While they are mathematical entities, Platonic ideals, and hypothetical in that sense, Turing Machines are real: we can actually construct them in the real world. Granted, what we construct will never be a perfect Turing Machine, but our mathematical theory about them does apply to the real world, the laws we can derive do apply to computation devices in the real world, the theory can be used as a basis for designing, constructing and measuring computation devices in the real world; this is the reason the theory was developed in the first place.
  2. "Turing Machines are useless because they don't describe the computing devices we normally use." Wrong! Describing actual computation devices you find in the real world is not their purpose. If your whole back office or home entertainment studio doesn't contain a single Turing Machine, that doesn't mean the concept of Turing Machine is unrealistic or outdated and had better be replaced with something else. Their main purpose is as an elementary construct from which all more complex computation devices can be constructed in principle - and for which we can therefore derive laws that apply to computation devices in general. Reasoning about Turing Machines allows us to reason about computation devices in general. Your computer hardware and software are subject to the same laws that we have derived for Turing Machines, and our knowledge of these laws was used, directly or indirectly, to construct them - even though they probably don't have a single Turing Machine in them. It's the laws we're interested in.
$\endgroup$
3
  • 1
    $\begingroup$ Could you extend this discussion on triangles to the case of tesseracts. I feel that triangles should be opposed to entities that are less obviously physical. $\endgroup$
    – babou
    Dec 10, 2014 at 12:07
  • 1
    $\begingroup$ I laughed when I read the question, because to me it appeared exactly as ridiculous as stating that triangles are archaic. Computer Science is fundamentally mathematics; it doesn't age and it doesn't become outdated. Very well-written answer; +1. $\endgroup$
    – Wildcard
    Dec 9, 2016 at 1:10
  • $\begingroup$ I don't see the relevance of a tesseract, but it might be an improvement to use some kind of procedure or machine, e.g. knitting or a knitting machine. A Turing machine doesn't really describe an object but a (configurable, stepwise) process. $\endgroup$ Jun 12, 2017 at 17:25
9
$\begingroup$

Many very different Turing complete computation model are physically realizable (up to considering infinity as standing for unboundedness). Thus that cannot the point for choosing a model.

The answer by @jkff is appropriate in remarking that the Turing Machine is intended as a theoretical device for the mathematical purpose of studying computability and provability (arising actually in the context of Hilbert's Entscheidungsproblem). But it is not quite accurate in the reasons for choosing a simple formalism.

Proving in principle the Halting problem is not that much harder with more advanced models. In fact, our "proofs" are often just construction of a solution. We do not go much into the actual (very tedious) arguments that these constructions are correct. But anyone who writes an interpreter for a Turing complete language does as much as any construction a universal machine. Well, C can be a bit intricate, and we might want to streamline it a bit for such a purpose.

The importance of having a simple model resides much more in the use that can be made of the model, than in establishing its properties (such as the Halting Problem, to take the example given by @jkff).

Typically, great theorem are often theorems that can be expressed very simply and are applicable to a wide range of problems. But they are not necessarily theorems that are easy to prove.

In the case of TM, the importance of simplicity is because many results are established by reducing the Halting Problem, or other TM problems, to problems we are interested in (such as ambiguty of Context-free languages), thus establishing inherent limitations to solving these problems.

In fact, though very intuitive (which is probably the main reason for its popularity), the TM model is often not simple enough for use in such proofs. That is one reason for the importance of some other, even simpler models, such as the Post Correspondence Problem, less intuitive to analyse, but easier to use. But this is because these computational models are often used to prove negative results (which goes back to the original Entscheidungsproblem).

However, when we want to prove positive results, such as the existence of an algorithm to solve some given problem, the TM is much too simplistic a device. It is much easier to consider mode advanced models such as the RAM computer, or an associative memory computer, or one of many other models, or even simply one of the many programming languages.

Then the TM model comes only as a reference point, in particular for complexity analysis, given the complexity of reducing these models to the TM model (usually polynomial).The simplicity of the TM model lends then much credibility to complexity measures (as opposed, to take an extreme example, to the reductions of Lambda-calculus).

In other words, the TM model is often too simplistic for designing and studying algorithms (positive results), and often too complex for studying computability (negative results).

But it seems to be at about the right place to serve as a central link to connect it all together, with the great advantage of being rather intuitive.

Regarding physical analogies, there is no reason to choose one model over another. Many Turing complete computation model are physically realizable (up to unboundedness for memory infinity), since there is no reason to consider a computer together with its software as less physical than a "naked" computer. After all, the software has a physical representation, which is part of the programmed computer. So, since all computation models are equivalent from that point of view, we might as well chose one that is convenient for the organization of knowledge.

$\endgroup$
9
  • $\begingroup$ Maybe that's an unsympathetic remark, but the first sentence isn't true since you can always go upwards. There are several models for hyper-computation which are Turing complete computation models but are not physically realizable. $\endgroup$
    – Nikolaj-K
    Dec 4, 2014 at 13:49
  • $\begingroup$ Thanks. I never thought of that, but I guess that can be right, as hypercomputation can always be weakened by some other means. How do you think this should then be stated, since I assume you understood what I meant to say? $\endgroup$
    – babou
    Dec 4, 2014 at 13:57
  • 1
    $\begingroup$ Yeah, it's not just stuff like non-deterministic or infinite time machines. A Turing machine which after step 7 of the computation turns into an elephant, eats a bowl of Spaghetti, builds another Turing machine and proceeds with step 8 of the original computation... is also a valid Turing complete computation model. Whatever, I don't think you should fix it. $\endgroup$
    – Nikolaj-K
    Dec 4, 2014 at 14:04
  • $\begingroup$ "Any Turing complete computation model is physically realizable.", well, no, quite the opposite, actually. In fact, no Turing complete model can ever be physically constructed, because we cannot construct anything infinite. So all "physically realized" computation models are at best Linear-Bounded Automata models or less. $\endgroup$ Dec 4, 2014 at 17:12
  • $\begingroup$ @RBarryYoung If you had the patience to read the whole answer, you may have noticed that in the last paragraph, I make it explicit that this is "up to unboundedness for memory infinity". The first sentence was intended as an introduction. Do you think improper not to give such a known fact in the introduction? It is true that trying to analyze in greater depth the role of the TM model opens my answer to more criticism. Did you see anything else that sems wrong with my answer? $\endgroup$
    – babou
    Dec 4, 2014 at 17:43
4
$\begingroup$

The physical analogy that Turing seems to have had in mind is a computer working out problems with pencil, paper, and eraser. You should understand that in 1936, a "computer" was a person employed to compute. Of course in 1936 most computers would have been using adding machines, but Turing doesn't mention these since they are inessential. Here is what he does say, with regard to the tape, in trying to justify that "the 'computable' numbers [i.e. those that a Turing machine could compute] include all numbers which would naturally be regarded as computable"

Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares.

Although computer is no longer a trade, the last time I checked, kids were still being taught to execute algorithms using pencil and paper as a storage medium. So, although this analogy may seems old-fashioned or even archaic, it is not yet obsolete.

For more see On computable numbers with an application to the entscheidungsproblem, especially sections 1 and 9.

$\endgroup$
1
  • $\begingroup$ Joe Weizenbaum used another physical analogy for explanation: tokens on a toilet paper roll. $\endgroup$
    – Jerry101
    Dec 4, 2014 at 23:46
1
$\begingroup$

@jkff has the idea about the Turing Machine is modeled on the idea of a human with a pen and paper is not entirely correct. But there are many situations where it can be considered correct.

Think about the human as a Turing machine under certain projection of the states. In other words, if you see a human only during his work hours, then during his work hours he performs certain tasks. These tasks are the basic tasks for the job.

If you don't care about his personal life, what he does at home, in his room etc.. Then you can consider this as projecting his transition function into a new transition function in which non-work-related states are ignored. In other words, you can skip over all the states and tasks that have nothing to do with your concern and perspective.

In this model, then the Turing machine is modeled after a human with a pen, paper doing a fixed task (ie view in a fixed perspective). The tape is what he writes down on the paper (ignoring all the papers or writing on some paper that he does not write for the task)

Now if you take into account other tasks that he does then what you have is you have a union of many Turing machines in a human. But then what if he changes his job and he does different task. Then his brain state changes to a different Turing machine when view under different perspective in different time frame.

If you want a good answer to your question, then I think Yuval Filmus answered it well. Use the RAM model. Stick with it.

$\endgroup$
0
$\begingroup$

I want to add two points, not mentioned in earlier examples, to supplement them.

  1. The Church-Turing thesis was made clear when Turing invented the Turing machine: It's valuable to have one or more concepts that means something roughly like "possible to calculate algorithmically, in principle". If a problem is not of this kind, then it's not the sort of thing that can be solved with a computer. Alonzo Church argued that his lambda calculus formalism captured just such a concept, but some of his peers (notable Kurt Gödel) were sceptical. Turing proposed a similar concept, defined in terms of (what we now call) a Turing machine, and proved that Turing machine computability was equivalent to lambda-calculus computability. This convinced sceptics such as Gödel that lambda calculus and Turing machines capture a basic, intuitive idea of what can be done with an algorithm. That's roughly the Church-Turing thesis. (I am not being very precise, and I'm ignoring debates about different versions of the C-T thesis and what the original version was.) The beauty of the idea of a Turing machine, as opposed to a purely mathematical formalism like the lambda calculus, is that everyone can see how simple its operation is partly because you can easily imagine something like it being physically implemented. Of course it is inefficient, but the obvious potential for physical realization is what makes it intuitively clear that anything that can be proved to be computed by a Turing machine, can be computed on any computer (if you have time and space for it), and that anything that can't be computed on a Turing machine, can't be computed on any of the computers we use today (putting aside some corner cases like computers with true random number generators).

  2. The idea of a Turing machine is absolutely central to algorithmic information theory, which, among other things, defines a variety of concepts of randomness that help to guide our understanding of randomness in some scientific and practical computing contexts. (Why is 110101010010011010 more random than 101010101010101010?) I discuss this in an answer to the related question mentioned above.

I would guess that there are other areas of research that have also benefited from the availability of the concept of a Turing machine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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