The "quality" of An Algorithm: A "better" Version of Turing-machine Addition M+n
We will see from the example below that the following addition-algorithm is "better" for computing m+n than the one specified above, at least from the quality standpoint of requiring (i) less space (fewer instructions: 4 versus 5 states), and (ii) less time (9 versus 16 steps). Whether or not the algorithm below is better than the above in terms of reliability is another question. Because it does not explore the 2nd number (i.e. "n") it cannot halt in a "non-standard" or fail-to-compute-correctly state.
We conclude from this example that although the algorithms result in the same output (end state) they perform differently. In fact there are many other possible algorithms . However comparisons and measurements of "quality" must be made relative to an a priori standard .
High-level description #1:
- Because the unary numbers to be added, e.g. m+n, are separated by a single blank the machine will hunt for this blank and fill it in. It will then move the head left to the blank at the left of the sum, move the head right once, erase the mark there, move the head right once again and halt. At the beginning a test is provided for the case of 0+n (and by implication, 0+0).
Formal description #3: The state table written in quadruple-form:
| state qj | Scanned symbol | Action | next state qk | state qn | Scanned symbol | Action | next state qk | |
| 1 | B | R | H | 1 | 1 | R | 2 | |
| 2 | B | P | 3 | 2 | 1 | R | 2 | |
| 3 | B | R | 4 | 3 | 1 | L | 3 | |
| 4 | B | R | H | 4 | 1 | E | 4 |
An example run of the algorithm:
| State qj | 1 | 2 | 3 | 4 | ||||||||||||||||||
| Scanned symbol | B | B | B | B | ||||||||||||||||||
| B-action | R | P | R | R | ||||||||||||||||||
| B-next state qk: | H | 3 | 4 | H | ||||||||||||||||||
| State qj | 1 | 2 | 3 | 4 | ||||||||||||||||||
| Scanned symbol | 1 | 1 | 1 | 1 | ||||||||||||||||||
| 1-Action | R | R | L | E | ||||||||||||||||||
| 1-next state qk: | 2 | 2 | 3 | 4 | ||||||||||||||||||
| Step | Instruction | Next Inst# | Total state | |||||||||||||||||||
| 0 | start | B | B | B | B | 1 | 1 | B | 1 | 1 | 1 | B | B | B | 1 | 11B111 | ||||||
| 1 | R | B | B | B | B | 1 | 1 | B | 1 | 1 | 1 | B | B | B | R | 2 | 11B111 | |||||
| 2 | R | B | B | B | B | 1 | 1 | B | 1 | 1 | 1 | B | B | B | R | 2 | 11B111 | |||||
| 3 | P | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | P | 3 | 111111 | |||||
| 4 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | L | 3 | 111111 | |||||
| 5 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | L | 3 | 111111 | |||||
| 6 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | L | 3 | B111111 | |||||
| 7 | R | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | R | 4 | 111111 | |||||
| 8 | E | B | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | E | 4 | B11111 | |||||
| 9 | R | B | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | R | H | 11111 |
Read more about this topic: Algorithm Examples
Famous quotes containing the words quality, version and/or addition:
“Our sense of duty must often wait for some work which shall take the place of dilettanteism [sic] and make us feel that the quality of our action is not a matter of indifference.”
—George Eliot [Mary Ann (or Marian)
“I should think that an ordinary copy of the King James version would have been good enough for those Congressmen.”
—Calvin Coolidge (1872–1933)
“As easy mayst thou fall
A drop of water in the breaking gulf,
And take unmingled thence that drop again,
Without addition or diminishing,
As take from me thyself and not me too.”
—William Shakespeare (1564–1616)