-5
$\begingroup$

[Edited to provide better context.]

In a comment on meta, JɛffE suggested that this would be a good topic for a question to ask here.

why is a Turing machine defined as a 5-tuple?

$\endgroup$
10
  • 8
    $\begingroup$ It is one thing to ask a question where you carefully explain what your already understand and what your question is motivated by. It is completely different thing to copy and paste someone else's comment on meta and just say "somebody said I should ask this". This question is not a real question, and I have voted to close it as such. It is your job as the poster to motivate and explain the question, properly capitalize, and in general put in at least a small morsel of effort. $\endgroup$ Aug 9 '12 at 18:35
  • 4
    $\begingroup$ @vzn: I suspect that if JɛffE had ever been inclined to ask this question, he would have given some background as to the foundations of mathematics and its possible role in informing the theory of computation, in order to give an appropriate background to motivate the question. For questions like this which look elementary, some amount of reflective context is necessary in order to keep them from being elementary. By not providing such context yourself, you're basically asking people to transform the question into something interesting first, which will tend to make the answers subjective. $\endgroup$ Aug 9 '12 at 19:35
  • 6
    $\begingroup$ @vzn: The question you are comparing this to, which was answered by Terry Tao is very differently phrased! Note how much effort the OP has put into the question to explain what the OP wants to understand. $\endgroup$ Aug 9 '12 at 19:38
  • 7
    $\begingroup$ @vzn: we cannot force you to entertain alternative models which fit the observations you have made, nor give you our experience with internet fora. We can only try to help to teach you how to ask a constructive question, and occasionally spend time trying to derive a constructive question from what you ask as a show of good faith. But in a world with so many questions, the tastiest ones are the ones seasoned with thought and motivation; and if you try to serve a frankfurter to gourmets, you sell why your particular frankfurter is worth their time, when they've got steaks in the pan. $\endgroup$ Aug 9 '12 at 20:45
  • 5
    $\begingroup$ to anyone who has spent any time at all to think about it, the phrase Jeff used was a shorthand for "why is the 5-tuple that Turing used sufficient to capture the notion of computation". asking this question properly would require you to cite the definition, clarify what you understand as motivation for each element in it, and tell us where you are stuck/why you think there are alternative choices. what you are doing is good old trolling. $\endgroup$ Aug 9 '12 at 22:57
7
$\begingroup$

Short meta preamble — Despite my misgivings (in particular, despite the comment on meta, I don't really think that this question is parallel to the question of why one should define topologies in terms of open sets), I think it may be important for the sake of the exercise and in particular as a point of empiricism to see if we can squeeze out a meaningful answer to this particular question.


We have to recall that the theory of computation began a few decades after mathematicians and logicians became quite keen on formalization, and in particular on simple, universal foundations for mathematics. In particular, when Turing defined his machines, people had recently been fretting about the best way to define ordered pairs in terms of sets. This sort of pre-occupation with minutiae probably strikes some of us as a little bit funny today, but it was the context in which definitions were set out.

As I hint in my comment above about groups — that although they are sometimes described as an ordered pair $(G,\ast)$ consisting of a set $G$ and some binary operator $\ast$, most people talk about $G$ itself as though it were the group — the notion that a Turing machine is a tuple is really beside the point; the role served by the tuple description is just to say that the machine is characterized by a collection of mathematical objects which have some relationships to one another. Furthermore, whether it is a 5-tuple, or a 7-tuple, depends on how you want to present the particular mathematical pieces. It makes a lot of sense to lump some of them together, as I argue below, so that (if you care about tuples) you can have some sort of argument as to the "best" arity of the tuple.

  • The set of states $Q$ is simple enough and could stand on its own, but doesn't really have any meaning on its own either, without e.g. the transition function alongside it to give it the semantics of the state of a "machine" which depends on "time".

  • The initial state, and the halting states, of the machine are just special elements of $Q$. These can be supplied separately (with the proviso that they are elements of $Q$), or we might say that $Q$ is not merely a set but some more exotic object in which the distinguished elements are supposed to be given. For instance, perhaps $Q$ is a pointed set in which the initial state is an intrinsically special element, so that we could easily describe the unions of languages by joins of nondeterministic Turing machines which accept those languages. Perhaps some other clever special roles could be given to accept and reject states; or perhaps those could just be states designated specially by the transition function, rather than along with $Q$ or separately on their own.

  • The alphabet on which the machine acts can again stand on its own, and it makes an enormous amount of sense to consider this again as a pointed set, where the blank symbol is the special element, rather than supplying that blank symbol separately.

  • The tape is some function from a set such as $\mathbb N$ to the alphabet in which all but finitely many symbols are blank; so the tape immediately has some relation to the alphabet as a pointed set.

  • Finally, the transition function is impossible to define without the set of states, the alphabet, and the tape — but it is what gives them meaning as a model of computation by giving some sort of sense of evolution via repeated application.

Recognizing that this is what we care about in the definition of a Turing machine, the only thing that a tuple (of any arity) serves to do is to present them all together, in definite positions so that (if your foundations of mathematics are so thoroughly set-theoretic that you would be constitutionally unable to distinguish the number zero from the empty set) you can tell which is supposed to be the set of states $Q$ and which is supposed to be the transition function.

Indeed, if you want to describe Universal Turing Machines, in which a machine can read an encoding of another machine, some encoding must be used; and so describing a Turing machine as a tuple of some sort is a reasonable conceit. But does this mean that a Turing machine is really "a tuple", as opposed to being presentable (really, encodable) as a tuple? Not meaningfully so. They might be presented just as well or better in terms of categories, or some class of mathematical structures of which Turing machines are the first interesting exemplar.

Mathematical objects, Turing machines included, derive their meaning from what they do. What tuples do is present several things at once; they are a data structure. What Turing machines do is allow us to express a robust notion of computability through the relationships of several related mathematical structures, and through our understanding of how to apply those relationships to things that we care about.

$\endgroup$
5
  • $\begingroup$ [thinking this over, guess my real question was, why does JeffE think this is an interesting question? & if he wont say, does anyone else know what he's talking about?] $\endgroup$
    – vzn
    Aug 13 '12 at 22:48
  • $\begingroup$ @vzn: If I had to guess, I imagine that he took a look at the MO topology question, thought of what an analogue of might be for a fundamental question about CS; and then imagined (without much detail) that someone might ask why this particular definition for universal computation might be important. He may not have specifically wondered why Turing machnes are 5- (or 7-) tuples, nor why this suffices to define a robust notion of computation; he probably just imagined that someone might wonder this, and that they might wonder e.g. whether the alphabet on its own is really important. $\endgroup$ Aug 14 '12 at 1:41
  • $\begingroup$ @vzn: I don't expect that JeffE was doing anything more than fishing for something broader than what is typically accepted here (but might be appropriate) by comparison to simple-but-profound questions on other SE fora. As you may gather, I disagree with him about the profundity of this question -- except inasmuch as I value philosophy of mathematics. But much of CS is intensely application-driven, to the point that most people are disinterested in philosophical backdrop; so this question really was a non-starter I think. For myself, at least it was precise enough to respond in a clear manner. $\endgroup$ Aug 14 '12 at 1:49
  • $\begingroup$ thought initially maybe there was academic debate on how to define a TM & seriously really didnt exactly expect it to blow up in my face quite the way it did. it seemed an allusion to some funky alternative I hadnt heard of... something deeper... he says I havent studied enough to understand... huh. is that true of everyone else on here? your answer is erudite but surely not what he was getting at, right? looks like the jokes still on me I guess... blame the victim.. I guess everyone else was "smart" at least enough to ignore it... no asking about the emperors clothes or trying them on =) $\endgroup$
    – vzn
    Aug 14 '12 at 2:11
  • 2
    $\begingroup$ @vzn: An ongoing controversy would either be so public that you could find it on Google, or so technical that you wouldn't be so penalized for asking about it -- the downvoting is a symptom of the lack of that controversy. (But if you had been thinking about it for a while yourself, you might have stimulated interest if you raised acute concerns.) The audience here is interested in questions with definite technical dimensions. If the problem isn't subtle, obscure, surprisingly difficult, or profound -- and if you can't convince others that it's one of these -- it probably doesn't belong here. $\endgroup$ Aug 14 '12 at 2:31

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