2006: Sipser's Assertion and His Three Levels of Description
- For examples of this specification-method applied to the addition algorithm "m+n" see Algorithm examples.
Sipser begins by defining '"algorithm" as follows:
- "Informally speaking, an algorithm is a collection of simple instructions for carrying out some task. Commonplace in everyday life, algorithms sometimes are called procedures or recipes (italics in original, p. 154)
- "...our real focus from now on is on algorithms. That is, the Turing machine merely serves as a precise model for the definition of algorithm .... we need only to be comfortable enough with Turing machines to believe that they capture all algorithms" ( p. 156)
Does Sipser mean that "algorithm" is just "instructions" for a Turing machine, or is the combination of "instructions + a (specific variety of) Turing machine"? For example, he defines the two standard variants (multi-tape and non-deterministic) of his particular variant (not the same as Turing's original) and goes on, in his Problems (pages 160-161), to describes four more variants (write-once, doubly infinite tape (i.e. left- and right-infinite), left reset, and "stay put instead of left). In addition, he imposes some constraints. First, the input must be encoded as a string (p. 157) and says of numeric encodings in the context of complexity theory:
- "But note that unary notation for encoding numbers (as in the number 17 encoded by the uary string 11111111111111111) isn't reasonable because it is exponentially larger than truly reasonable encodings, such as base k notation for any k ≥ 2."(p. 259)
van Emde Boas comments on a similar problem with respect to the random access machine (RAM) abstract model of computation sometimes used in place of the Turing machine when doing "analysis of algorithms": "The absence or presence of multiplicative and parallel bit manipulation operations is of relevance for the correct understanding of some results in the analysis of algorithms.
". . . here hardly exists such as a thing as an "innocent" extension of the standard RAM model in the uniform time measures; either one only has additive arithmetic or one might as well include all reasonable multiplicative and/or bitwise Boolean instructions on small operands." (van Emde Boas, 1990:26)
With regards to a "description language" for algorithms Sipser finishes the job that Stone and Boolos-Burgess-Jeffrey started (boldface added). He offers us three levels of description of Turing machine algorithms (p. 157):
- High-level description: "wherein we use ... prose to describe an algorithm, ignoring the implementation details. At this level we do not need to mention how the machine manages its tape or head."
- Implementation description: "in which we use ... prose to describe the way that the Turing machine moves its head and the way that it stores data on its tape. At this level we do not give details of states or transition function."
- Formal description: "... the lowest, most detailed, level of description... that spells out in full the Turing machine's states, transition function, and so on."
Read more about this topic: Algorithm Characterizations
Famous quotes containing the words assertion, levels and/or description:
“What causes adolescents to rebel is not the assertion of authority but the arbitrary use of power, with little explanation of the rules and no involvement in decision-making. . . . Involving the adolescent in decisions doesn’t mean that you are giving up your authority. It means acknowledging that the teenager is growing up and has the right to participate in decisions that affect his or her life.”
—Laurence Steinberg (20th century)
“The country is fed up with children and their problems. For the first time in history, the differences in outlook between people raising children and those who are not are beginning to assume some political significance. This difference is already a part of the conflicts in local school politics. It may spread to other levels of government. Society has less time for the concerns of those who raise the young or try to teach them.”
—Joseph Featherstone (20th century)
“The Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a “global village” instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacle’s present vulgarity.”
—Guy Debord (b. 1931)