7
$\begingroup$

I have followed two famous book on "Automata and Formal Language Theory":

  1. Micheal Sipser's book
  2. Jeffrey Ullman and John Hopcroft's book

in both books, tuple level definition of Turing machine differs with each other. Although abstract level working are same but details are different. Why there is not any standard definition? Even some other books have explained the Turing machine in different way.

When we try to measure time complexity of same algorithm on these machines, exact time also differs. Why the authors/scientist have not agreed upon one standard definition?

$\endgroup$
3
  • 2
    $\begingroup$ Mathematical definitions come in flavors. You get to pick your favorite, and that is a good thing. As long as everything is clearly stated, no one gets hurt. $\endgroup$ Jun 25 '15 at 14:51
  • $\begingroup$ I agree with André Souza Lemos. Furthermore, one can argue that if the definitions are not the same, they could choose differents name. Indeed, I think there is a connection with essence/accident theory (en.wikipedia.org/wiki/Essence). We can consider that what is different in the two definitions is meaningless and that what is meaningful in each definition is also in the other definition, so it's normal to keep the same name. $\endgroup$
    – François
    Jun 25 '15 at 15:15
  • $\begingroup$ it would be better if you wrote out the defns and detailed how they are "different" . the basic answer is that they're all Turing equivalent and also the speed differences are within "inconsequential" P (polynomial)-time differences. $\endgroup$
    – vzn
    Jun 25 '15 at 20:21
12
$\begingroup$

There is no standard definition since it is uncommon to use the details of the definition of Turing machine. In contrast to other definitions in mathematics, Turing machines are complicated objects whose definition is unwieldy to use directly. Instead, we invoke the Church–Turing hypothesis and describe Turing machines by giving algorithms rather than listing tuples. At this point, the exact definition of Turing machine is unimportant.

A similar situation occurs in other cases, of which I will describe two: number systems and forcing.

Number systems, especially the real numbers, have several different constructions. If you look at books containing a construction of the real numbers, you are likely to see different constructions, in some cases vastly different ones (for example, Dedekind cuts versus Cauchy sequences). However, from the point of view of the user, all we care about is that the real numbers we construct satisfy the field axioms as well as being complete and Archimedean (the exact meaning of these terms is unimportant). We almost never get to use the actual underlying definitions.

Forcing is an important proof technique in set theory. Forcing can be defined in several different ways, the most popular being forcing relations and Boolean-valued models. (A less popular one is modal logic.) These methods are all equivalent, but the formal development can be somewhat different. All of these methods lead to the same proofs in set theory, but there is no "official" one. Which one you choose to present in a set theory textbook or course depends on your personal taste.

The exact definition of Turing machine does matter if you're interested in exact resource consumption, say, how many steps does it take to solve a certain problem. Since all reasonable definitions of Turing machines result in the same running times up to constant factors, and since we don't usually care about constant factors per se, the exact definition doesn't matter and yields the same results.

The same situation occurs when proving other theorems in which the Church–Turing hypothesis cannot be used. For example, when proving Cook's theorem that SAT is NP-complete, we really need to refer to the definition of Turing machine; but the construction will work for many different definitions, in much the same way. We pick one definition arbitrarily and stick to it, knowing that using any other variant will result in a slightly different yet still valid proof.

$\endgroup$
1
5
$\begingroup$

This happens often; for instance, there are several definitions of finite automata around.

There are two things we are usually interested in in models of computation (and in TCS):

  1. computational power and
  2. cost measures.

If 1. is the same and 2. only differs insignificantly (complexity theorists would say, by a polynomial/polylogarithmic/constant/... factor), we may switch between (approximately) equivalent definitions.

The conditions can be proven formally, provided the models are formally defined. It may be an illustrative exercise for you to do this.

Why have different definitions then? Because one or the other proof may be easier, or one or the other concept more neatly described. Therefore, the goal of a course/book, the selection of topics, the author's didactic approach and taste may cause one definition to work better than another.

$\endgroup$
5
$\begingroup$

I will try to take a slightly different approach than the other answers, and examine in particular the standardisation issue.

It is a bit surprising that you wonder about this situation. The Hopcroft-Ullman book (I use the 1979 edition) gives two definitions of PushDown Automaton (PDA): acceptance by final state or by empty stack.

If you read the section on Turing Machines (TM) construction techniques (section 7.4 in 1979 edition), they explicitly state:

Designing Turing machines by writing out a complete set of states and a next-move function is a noticeably unrewarding task. In order to describe complicated Turing machine constructions, we need some "higher-level" conceptual tools.

The rest of the section, and the following sections, show all sorts of variations on the definition of a TM, extending or limiting the definition, that are all equivalent.

The point is that, for each problem at hand, we will choose the one definition that is best adapted too solving that problem. Of course, each of these definition could do in principle. But depending on the issue, some definitions will give you more perspicuity on a specific problem, and thus make the proofs easier.

Considering the case of Context-Free (CF) languages and grammars, there are many normal forms that have been defined: Chomsky Normal Form, Greibach Normal Form, Binary form. All can generate any CF language, and they could be seen as variations of CF grammar definition. It is good to have them coexist, because each as a role to play in some context. They are intertranslatable, but at cost.

If you try to analyze the cost/complexity of CF parsing they are not equivalent, and this is to be taken into account. This complexity issue is much more critical in the CF case than it is for TM, because CF parsers are used a lot in engineering situations, while TM are a purely theoretical tool. This does not prevent engineers using CF parsing from using various grammar forms for the same language, in some coordinated way, in order to take various issues into account.

In the case of CF languages, it can be a critical engineering issue, and it was thus to be expected that CF gramars, and their different forms would be normalized/standardized about as much as the size of wrenches or the diameter of electric wires. Actually it went as far as defining a precise syntax for writing CF grammars, the Backus Naur Form (BNF).

TM have few engineering applications that would justify normalization, and they have much greater potential variability (which is however partially taken into account by considering majors variations such as multi-tape, multi-head, ...). This explain that there was little pressure to adopt a standard form, given that mathematicians who use them are supposed to be technically mature enough to be careful when it can make a difference, such a counting precisely the number of moves. Even for complexity, the small variations in definitions often do not matter, because we consider only asymptotic complexity, and often asymptotic complexity up to a polynomial function.

It is quite common in mathematics (among other sciences) that different authors will choose different definitions, that are know to be equivalent (or equivalent in most context), depending on their taste, their view of applications, their vision of the problem structure, their pedagogical purposes, etc. Definitions also evolve with time as more gets known about a problem, and as perspectives change. The same goes for notations. This variability is an important source of progress and understanding. The Greeks were doing excellent mathematics, but it is a lot easier with modern concepts (e.g. variables), definitions and notations.

Standards are often seen as extremely convenient (cf wrenches and wire diameters). But they can also a factor of rigidity that prevent progress. Standardization is a double edged sword, so we must blunt it a little bit for safety. The various definitions are usually not quite identical, but close enough so that theories can develop more or less in the same way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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