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