This is the fifth part of the Turing Machine series. For your convenience you can find other parts in the table of contents in Part 1 – Addition

Today we check whether a string has exactly twice as many ones as zeroes.

States:

q0 - looking for the beginning
q1 - looking for 0
q2 - have 0, looking for end
q3 - looking for first 1
q4 - looking for second 1
q5 - checking for no 1
qyes - matches

The input looks like this:

$011$

Transition table:

$,q0,$,q1,R
^,q0,^,q0,L
0,q0,0,q0,L
1,q0,1,q0,L

0,q1,^,q2,R
1,q1,1,q1,R
^,q1,^,q1,R
$,q1,$,q5,L

0,q2,0,q2,R
1,q2,1,q2,R
^,q2,^,q2,R
$,q2,$,q3,L


0,q3,0,q3,L
1,q3,^,q4,L
^,q3,^,q3,L

0,q4,0,q4,L
1,q4,^,q0,L
^,q4,^,q4,L

^,q5,^,q5,L
$,q5,$,qyes,R

This is the fourth part of the Turing Machine series. For your convenience you can find other parts in the table of contents in Part 1 – Addition

Today we subtract two numbers. This is very similar to addition so should be pretty readable.

States:

q0 - looking for the beginning, no borrow
q1 - looking for the beginning, with borrow
q2 - looking for the first number digit, no borrow
q3 - looking for the first number digit, with borrow
q4 - 0 from the first digit, looking for boundary, no borrow
q5 - 1 from the first digit, looking for boundary, no borrow
q6 - 1 from the first digit, looking for boundary, with borrow
q7 - 0 from the first digit, looking for the second number digit, no borrow
q8 - 1 from the first digit, looking for the second number digit, no borrow
q9 - 1 from the first digit, looking for the second number digit, with borrow
q10 - 0 in the difference, looking for the end of the second number, no borrow
q11 - 1 in the difference, looking for the end of the second number, no borrow
q12 - 1 in the difference, looking for the end of the second number, with borrow
q13 - 0 in the difference, looking for the end of the second number, with borrow
q14 - 0 in the difference, looking for a place to write, no borrow
q15 - 1 in the difference, looking for a place to write, no borrow
q16 - 1 in the difference, looking for a place to write, with borrow
q17 - 0 in the difference, looking for a place to write, with borrow

The input looks like this:

$aaaa%bbb^

Transition table:

0,q0,0,q0,L
1,q0,1,q0,L
^,q0,^,q0,L
%,q0,%,q0,L
$,q0,$,q2,R

0,q1,0,q1,L
1,q1,1,q1,L
^,q1,^,q1,L
%,q1,%,q1,L
$,q1,$,q3,R

0,q2,$,q4,R
1,q2,$,q5,R

0,q3,$,q6,R
1,q3,$,q4,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

0,q7,%,q10,R
1,q7,%,q12,R
%,q7,%,q7,R

0,q8,%,q11,R
1,q8,%,q10,R
%,q8,%,q8,R

0,q9,%,q12,R
1,q9,%,q13,R
%,q9,%,q9,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,1,q1,L

0,q17,0,q17,R
1,q17,1,q17,R
.,q17,0,q1,L

This is the third part of the Turing Machine series. For your convenience you can find other parts in the table of contents in Part 1 – Addition

Today we check if given word w is a palindrome. First, we add delimiters at the beginning and at the end. Next, we check first character from the left, go to the end and check if the last character matches. Then we go to the beginning and repeat.

States:

q0 - start
q1 - a in buffer
q2 - b in buffer
q3 - add $ at the end
q4 - return to begin
q5 - checking first character from the left
q6 - going to the end with a
q7 - going to the end with b
q8 - checking a as the last character
q9 - checking b as the last character
q10 - success

The input looks like this:

abba

Transition table:

a,q0,$,q1,R
b,q0,$,q2,R

a,q1,a,q1,R
b,q1,a,q2,R
.,q1,a,q3,R

a,q2,b,q1,R
b,q2,b,q2,R
.,q2,b,q3,R

.,q3,$,q4,L

a,q4,a,q4,L
b,q4,b,q4,L
$,q4,$,q5,R

a,q5,$,q6,R
b,q5,$,q7,R
$,q5,$,q10,R

a,q6,a,q6,R
b,q6,b,q6,R
$,q6,$,q8,L

a,q7,a,q7,R
b,q7,b,q7,R
$,q7,$,q9,L

a,q8,$,q4,L
$,q8,$,q10,L

b,q9,$,q4,L
$,q9,$,q10,L

This is the second part of the Turing Machine series. For your convenience you can find other parts in the table of contents in Part 1 – Addition

Today we check if given word w is of a form w = xx. Idea is: first I add delimiters ^ to the word boundary. Next, I use $ to cut one character at a time from the prefix and from the suffix of the word. Finally, I know where is the center of the word, so I can compare characters one by one.

States:

q0 - start
q1 - a in buffer
q2 - b in buffer
q3 - aa in buffer
q4 - ab in buffer
q5 - ba in buffer
q6 - bb in buffer
q7 - last a in buffer
q8 - last b in buffer
q9 - time to place $
q10 - time to place ^
q11 - looking for $ to the left to push
q12 - getting first character to the left
q13 - rewriting a with $ while going left
q14 - rewriting b with $ while going left
q15 - going to the left boundary ^ to rewrite
q16 - going to the left boundary ^ to compare words
q17 - looking for $ to the right to push
q18 - getting first character to the right
q19 - rewriting a with $ while going right
q20 - rewriting b with $ while going right
q21 - going to the right boundary ^ to rewrite
q22 - comparing from the left ^
q23 - looking for a in the word on the right
q24 - looking for b in the word on the right
q25 - have the word center, looking a on the right
q26 - have the word center, looking b on the right

q_fail - failure
q_ok - word is correct

The input looks like this:

aabbaabb

Transition table:

a,q0,^,q1,R
b,q0,^,q2,R

a,q1,$,q3,R
b,q1,$,q4,R

a,q2,$,q5,R
b,q2,$,q6,R

a,q3,a,q3,R
b,q3,a,q4,R
.,q3,a,q7,R

a,q4,a,q5,R
b,q4,a,q6,R
.,q4,a,q8,R

a,q5,b,q3,R
b,q5,b,q4,R
.,q5,b,q7,R

a,q6,b,q5,R
b,q6,b,q6,R
.,q6,b,q8,R

.,q7,a,q9,R

.,q8,b,q9,R

.,q9,$,q10,R

.,q10,^,q11,L

a,q11,a,q11,L
b,q11,b,q11,L
$,q11,$,q12,L

a,q12,$,q13,R
b,q12,$,q14,R
$,q12,$,q16,L

$,q13,a,q15,L

$,q14,b,q15,L

a,q15,a,q15,L
b,q15,b,q15,L
$,q15,$,q15,L
^,q15,^,q17,R

a,q17,a,q17,R
b,q17,b,q17,R
$,q17,$,q18,R

a,q18,$,q19,L
b,q18,$,q20,L
$,q18,$,q_fail,L

$,q19,a,q21,R
$,q20,b,q21,R

a,q21,a,q21,R
b,q21,b,q21,R
$,q21,$,q21,R
^,q21,^,q11,L


a,q16,a,q16,L
b,q16,b,q16,L
$,q16,$,q16,L
^,q16,^,q22,R

a,q22,^,q23,R
b,q22,^,q24,R
$,q22,$,q_ok,R

a,q23,a,q23,R
b,q23,b,q23,R
$,q23,$,q25,R

a,q24,a,q24,R
b,q24,b,q24,R
$,q24,$,q26,R

$,q25,$,q25,R
a,q25,$,q16,L
b,q25,b,q_fail,R

$,q26,$,q26,R
a,q26,a,q_fail,R
b,q26,$,q16,L

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:

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:

$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):

$,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