Precise Specification of Turing-machine Algorithm M+n
As described in Algorithm characterizations per the specifications of Boolos-Burgess-Jeffrey (2002) and Sipser (2006), and with a nod to the other characterizations we proceed to specify:
- (i) Number format: unary strings of marked squares (a "marked square" signfied by the symbol 1) separated by single blanks (signified by the symbol B) e.g. “2,3” = B11B111B
- (ii) Machine type: Turing machine: single-tape left-ended or no-ended, 2-symbol { B, 1 }, 4-tuple instruction format.
- (iii) Head location: See more at “Implementation Description” below. A symbolic representation of the head's location in the tape's symbol string will put the current state to the right of the scanned symbol. Blank squares may be included in this protocol. The state's number will appear with brackets around it, or sub-scripted. The head is shown as state #2, to the right of the second-from-left “1”:
- Example: B111B111B or B1121B111B
- (iii) Location of “the program”: This program will be in the finite state machine's TABLE and appear there in quadruple (4-tuple) format, suitably coded so the finite state machine can interpret them (see Footnote: Coding instructions for the finite state machine).
- (iv) The program: Boolos-Burgess-Jeffrey (2002) do not offer us one, however, we can devise one. We will note that it is not be as efficient as it could be; however, it works. See “Formal Description” below. (A “better” program will be found in the second example.)
Per the discussion of Sipser (2006) (p. 157) we will provide the three levels of description:
High-level description:
- The computation m+n adds two blocks of unary marks (strokes) to produce a single block that represents their sum. At the start the blocks are separated by a single blank. The machine will hunt for this blank and fill it in. This solid block of marks constitutes the sum+1. The machine will hunt for the far-right end of the sum and erase one (the extra) far-right mark. Finally, it will proceed to the left end and halt with the head on the left-most mark.
Implementation description:
- Implementation specification:
- (a) Initial number format: The numbers n and m will be represented as close-packed blocks of unary marks, where number “0” = no mark and no blank, “1” = 1 mark, etc. The numbers n and m will be separated by a single blank, both from each other and any other parameters that happen to be on the tape:
- Example: 2+3 = B11B111B
- Example: 0+3 = B111B
- (b) Initial head location, initial state: Case m>0: Initially the machine will be scanning the leftmost 1 on the tape, e.g. parameter m. Case m=0: If parameter m is 0, or both m and n are 0, then the head will be where a mark would be if there were to be a mark, i.e. to the left of the spacer-blank. The initial state will be “1”:
- Example: 2+3 = B111B111B
- Example: 0+3 = BB1111B
- (c) Successful computation – number format at Halt: The machine will halt on a single block of marks that represent the sum in the conventional sense. This will be true for m+0 and 0+n. In the case of 0+0 the sum will be “null”, neither blank nor mark.
- Example: 5 = B11111B
- Example: 0 = BB
- (d) Successful computation – head location at Halt: The machine will halt scanning the left-most 1 in the block that represents the sum:
- Example: 2+3 = 5 = B1k1111B
- Example: 2+0 = 2 = B1k1BB
- Example: 0+3 = 3 = BB1k11B
- Example: 0+0 = 0 = BkB
- (e) Unsuccessful computation: The machine will never halt or will halt in some non-standard configuration:
- Example: Bk11111B, or B11k111B, or B11111kB, etc.
- Implementation description
-
- State 1: Test for 0+n and by implication 0+0; if the head starts over a blank square, move the head once right and halt. If the tape is marked move the tape right once and go to state 2.
- State 2: If the tape is blank then the head has arrived at the space-blank between the two integers. Print a mark, then go to state 3. If the tape is marked, continue the hunt for a blank by moving the head to the right and looping through state 2.
- State 3: State "2 & B" has previously found the spacer blank and filled it in with a mark. While the tape is marked continue moving the head to the right while hunting for the blank to the right of the right-most number “n”. When the head finds this blank to the right of “”" (state 3 & 0), move the tape head left once and go to state 4.
- State 4: If the scanned square is marked, then the head is at the far right end of the sum. Erase this extra mark, then loop back to 4. The head will now be on a blank so move the head left once and jump to state 5.
- State 5: Hunt for the left end of the sum: while the scanned square is marked, move the head left and loop to state 5. When the head reaches the far left end it will be on a blank. Move the tape right once to be over the left-most mark and halt.
Formal description:
The state table written in (unreduced) 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 | L | 4 | 3 | 1 | R | 3 | |
| 4 | B | L | 5 | 4 | 1 | E | 4 | |
| 5 | B | R | H | 5 | 1 | L | 5 |
Sample "run" of the Turing-machine program: The program has been turned on its side; time runs down the page. The position of the head is high-lighted yellow. The "complete configuration" or the "total machine/system state" (in the context of Blass-Gurevich's "evolution of the state") is shown in the far-right column -- the instruction-number (finite-state machine's "state") is the number inside the brackets to the right of the scanned symbol (rather than a subscript to the right, for technical reasons):
| State qj | 1 | 2 | 3 | 4 | 5 | ||||||||||||||||||
| Scanned symbol | B | B | B | B | B | ||||||||||||||||||
| B-action | R | P | L | L | R | ||||||||||||||||||
| B-next state qk: | H | 3 | 4 | 5 | H | ||||||||||||||||||
| State qj | 1 | 2 | 3 | 4 | 5 | ||||||||||||||||||
| Scanned symbol | 1 | 1 | 1 | 1 | 1 | ||||||||||||||||||
| 1-Action | R | R | R | E | L | ||||||||||||||||||
| 1-next state qk: | 2 | 2 | 3 | 4 | 5 | ||||||||||||||||||
| 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 | R | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | R | 3 | 111111 | ||||||
| 5 | R | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | R | 3 | 111111 | ||||||
| 6 | R | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | R | 3 | 111111 | ||||||
| 7 | R | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | R | 3 | 111111B | ||||||
| 8 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | 1 | B | B | B | L | 4 | 111111 | ||||||
| 9 | E | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | B | E | 4 | 11111B | ||||||
| 10 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | B | L | 5 | 11111 | ||||||
| 11 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | B | L | 5 | 11111 | ||||||
| 12 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | B | L | 5 | 11111 | ||||||
| 13 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | B | L | 5 | 11111 | ||||||
| 14 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | B | L | 5 | 11111 | ||||||
| 15 | L | B | B | B | B | 1 | 1 | 1 | 1 | 1 | B | B | B | B | L | 5 | B11111 | ||||||
| 16 | R | B | B | B | 0 | 1 | 1 | 1 | 1 | 1 | B | B | B | B | R | H | 11111 |
(NOTE: The reader may find the equivalent Post-Turing machine program easier to read and simulate. In this example the head moves; just reverse L and R for the case when the tape moves):
| Instruction #: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Instruction: | J0 | R | J1 | P | R | J1 | L | E | L | J1 | R | H |
| Jump-to #: | 11 | 2 | 5 | 9 |
Read more about this topic: Algorithm Examples
Famous quotes containing the word precise:
“I know if I wake up cold,
and go out into the clear spring night,
still dark and precise with stars,
I will feel the wind coming down hard
like his hand, in fever, on my forehead.”
—Stanley Plumly (b. 1939)