patternModerate
Standard definition of Turing machine
Viewed 0 times
definitionturingmachinestandard
Problem
I have followed two famous book on "Automata and Formal Language Theory":
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?
- Micheal Sipser's book
- 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?
Solution
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.
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.
Context
StackExchange Computer Science Q#43919, answer score: 12
Revisions (0)
No revisions yet.