This is the first part of the Turing Machine series. For your convenience you can find other parts using the links below:
Part 1 — Addition
Part 2 — Checking if a word is a repetition
Part 3 – Checking palindromes
Part 4 — Subtraction
Part 5 — Twice as many ones as zeroes
In this post I show very simple addition algorithm for Turing Machine.
For testing the algorithm I use this page.
States:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
q0 - looking for the beginning, no carry q1 - looking for the beginning, with carry q2 - looking for digit of first number, no carry q3 - looking for digit of first number, with carry q4 - 0 from first number, looking for boundary between numbers q5 - 1 from first number, looking for boundary between numbers q6 - 2 from first number, looking for boundary between numbers q7 - 0 from first number, looking for digit of second number q8 - 1 from first number, looking for digit of second number q9 - 2 from first number, looking for digit of second number q10 - 0 in sum, looking for end of second number q11 - 1 in sum, looking for end of second number q12 - 2 in sum, looking for end of second number q13 - 3 in sum, looking for end of second number q14 - 0 in sum, looking for a place to write q15 - 1 in sum, looking for a place to write q16 - 2 in sum, looking for a place to write q17 - 3 in sum, looking for a place to write |
The input looks like this:
|
1 |
$aaaaaaa%bbbbbbbbb^.................... |
a is a digit of first number, b is a digit of second number, $ indicates left side of the input, % indicates boundary between numbers, ^ indicates right side of the input. Numbers are written “left to right” which means that 2 is written as 01. The result will appear on the right side after ^
Transition table in the form of character on the tape, current state, new character for the tape, new state, direction (R/L):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
$,q0,$,q2,R %,q0,%,q0,L ^,q0,^,q0,L 0,q0,0,q0,L 1,q0,1,q0,L $,q1,$,q3,R %,q1,%,q1,L ^,q1,^,q1,L 0,q1,0,q1,L 1,q1,1,q1,L 0,q2,$,q4,R 1,q2,$,q5,R %,q2,%,q7,R 0,q3,$,q5,R 1,q3,$,q6,R %,q3,%,q8,R 0,q4,0,q4,R 1,q4,1,q4,R %,q4,%,q7,R 0,q5,0,q5,R 1,q5,1,q5,R %,q5,%,q8,R 0,q6,0,q6,R 1,q6,1,q6,R %,q6,%,q9,R %,q7,%,q7,R 0,q7,%,q10,R 1,q7,%,q11,R %,q8,%,q8,R 0,q8,%,q11,R 1,q8,%,q12,R ^,q8,^,q15,R %,q9,%,q9,R 0,q9,%,q12,R 1,q9,%,q13,R ^,q9,^,q16,R 0,q10,0,q10,R 1,q10,1,q10,R ^,q10,^,q14,R 0,q11,0,q11,R 1,q11,1,q11,R ^,q11,^,q15,R 0,q12,0,q12,R 1,q12,1,q12,R ^,q12,^,q16,R 0,q13,0,q13,R 1,q13,1,q13,R ^,q13,^,q17,R 0,q14,0,q14,R 1,q14,1,q14,R .,q14,0,q0,L 0,q15,0,q15,R 1,q15,1,q15,R .,q15,1,q0,L 0,q16,0,q16,R 1,q16,1,q16,R .,q16,0,q1,L 0,q17,0,q17,R 1,q17,1,q17,R .,q17,1,q1,L |