Turing Machine for addition

Last Updated : 22 Feb, 2023





Prerequisite - Turing Machine

A number is represented in binary format in different finite automata. For example, 5 is
represented as 101. However, in the case of addition using a Turing machine, unary format is
followed. In unary format, a number is represented by either all ones or all zeroes. For
example, 5 will be represented by a sequence of five zeroes or five ones: 5 = 1 1 1 1 1 or 5 = 0
0 0 0 0. Lets use zeroes for representation.
A Turing machine can be designed to perform addition by using its tape to represent the
numbers to be added and its states to control the addition process. Here's a high-level
description of the process:
1. The two numbers to be added are placed on the tape, separated by a blank symbol.
2. The Turing machine starts at the leftmost digit of the first number and moves to the right,
one digit at a time, checking the value of each digit.
3. If a digit is 0, the machine writes a 0 in the corresponding position of the sum. If it's 1, it
writes a 1.
4. If both digits are 1, the machine writes a 0 and adds a carry of 1 to the next position.
5. When the Turing machine reaches the end of the input, it adds any remaining carry and
writes the result on the tape.

For adding 2 numbers using a Turing machine, both these numbers are given as input to the
Turing machine separated by a "c".

Examples - (2 + 3) will be given as 0 0 c 0 0 0:

Input : 0 0 c 0 0 0 // 2 + 3
Output : 0 0 0 0 0 // 5

Input : 0 0 0 0 c 0 0 0 // 4 + 3
Output : 0 0 0 0 0 0 0 // 7

Approach used -
Convert a 0 in the first number in to X and then traverse entire input and convert the first blank
encountered into 0. Then move towards left ignoring all 0's and "c". Come the position just
next to X, and repeat the same procedure until the time we get a "c" instead of X on returning.
Convert the c into blank and addition is completed.

Steps -

Step-1: Convert 0 into X and go to step 2. If symbol is "c" then convert it into blank(B), move
right and go to step 6.

Step-2: Keep ignoring 0's and move towards right. Ignore "c", move right and go to step 3.

Step-3: Keep ignoring 0's and move towards right. Convert a blank (B) into 0, move left and
go to step 4.

Step-4: Keep ignoring 0's and move towards left. Ignore "c", move left and go to step 3.

Step-5: Keep ignoring 0's and move towards left. Ignore an X, move right and go to step 1.

Step-6: End.
 Turing machine for subtraction | Set 1
Last Updated : 12 May, 2022





Prerequisite - Turing Machine Problem-1: Draw a Turing machine which subtract two
numbers. Example:

Steps:
 Step-1. If 0 found convert 0 into X and go right then convert all 0's into 0's and go right.
 Step-2. Then convert C into C and go right then convert all X into X and go right.
 Step-3. Then convert 0 into X and go left then convert all X into X and go left.
 Step-4. Then convert C into C and go left then convert all 0's into 0's and go left then convert
all X into X and go right and repeat the whole process.
 Step-5. Otherwise if C found convert C into C and go right then convert all X into B and go
right then convert 0 into 0 and go left and then stop the machine.
 Here, q0
shows the initial state and q1, q2, q3, q4, q5are the transition states and q6shows the final state.
And X, 0, C are the variables used for subtraction and R, L shows right and left. Problem-
2: Draw a Turing machine which subtract two numbers m and n, where m is greater than n.

Steps:
 Step-1. If 0 found convert all 0's into 0's and go right then convert C into C and go right
 Step-2. If X found then convert all X into X and go right or if 0 found then convert 0 into X
and go left and go to next step otherwise go to 5th step
 Step-3. Then convert all X into X and go left then convert C into C and go left
 Step-4. Then convert all 0's into 0's and go left then convert B into B and go right then
convert 0 into B and go right and repeat the whole process
 Step-5. Otherwise if B found convert B into B and go left then convert all X into B and go
left then convert C into B and go left and then stop the machine.
 Here, q0 shows the
initial state and q1, q2, q3, q4, q5are the transition states and q6shows the final state. And B, X,
0, C are the variables used for subtraction(m>n) and R, L shows right and left and B variable is a
input symbol. See for - Turing Machine for subtraction | Set 2

Turing Machine for subtraction | Set 2

Last Updated : 29 Oct, 2022





Prerequisite – Turing Machine, Turing machine for subtraction | Set 1 A number is represented
in binary format in different finite automatas like 5 is represented as (101) but in case of
subtraction Turing Machine unary format is followed . In unary format a number is represented
by either all ones or all zeros. For example, 5 will be represented by a sequence of five ones 5
= 1 1 1 1 1 or 0 0 0 0 0. Lets use zeros for representation. For subtraction of numbers using a
Turing Machine, both these numbers are given as input to the Turing machine separated by a
“c”. Example – (3 – 4) or (4 – 3) will be given as 0 0 0 c 0 0 0 0
Input: 0 0 0 c 0 0 0 0 // (3 - 4) or (4 - 3)
Output: 0 // (1)
Approach used – Convert a 0 in the first number into X and then move to the right, keep
ignoring 0’s and “c” then make the first 0 as X and move to the left . Now keep ignoring 0’s,
X’s and “c” and after finding the second zero repeat the same procedure till all the zeros on the
left hand side becomes X .Now move right and convert the last X encountered into B(Blank).
Steps – Step 1 – Convert 0 into X and move right then goto step2 . If symbol is “c” then
ignore it with moving to the right and go to step 6 .
Step 2 – Keep ignoring 0’s and move right . Ignore “c”, move right and goto step 3 .
Step 3 – Keep ignoring X and move right . Convert the first 0 encountered as X and move left
and goto step 4 .
 Step 4 – Keep ignoring all X’s and “c” to the left and goto step 5 .
Step 5 – Keep moving left with ignoring 0’s and when the first X is found then ignore it and
move right, and goto step 1 .
Step 6 – Keep ignoring all the X’s and move to the right . Ignore the first 0 encountered and
move to the left then goto step 7 .
Step 7 – Convert the X into B ( Blank ) and goto step 8 .

Step 8 – End .

Construct a Turing Machine for language L = {wwr | w ∈ {0, 1}}

Last Updated : 12 Aug, 2024





The language L = {wwres | w ∈ {0, 1}} represents a kind of language where you use only 2
character, i.e., 0 and 1. The first part of language can be any string of 0 and 1. The second part is
the reverse of the first part. Combining both these parts a string will be formed. Any such string
that falls in this category will be accepted by this language. The beginning and end of the string
are marked by a $ sign. For example, if the first part w = 1 1 0 0 1 then the second part wr = 1 0
0 1 1. It is clearly visible that wr is the reverse of w, so the string 1 1 0 0 1 1 0 0 1 1 is a part of a
given language. It can also be said that the strings which are palindrome of even length will be
accepted by this language.
Examples:
Input : 0 0 1 1 1 1 0 0
Output : Accepted
Input : 1 0 1 0 0 1 0 1
Output : Accepted
Input: 0 1 0
Output: Not Accepted
Basic Representation

Appro
ach 1: Two Pointers
Start from the beginning of the input tape. If the symbol is 0, replace it with Y and move right, or
if it's 1, replace it with X and move right.
Once at the end of the string, move back to the position next to the symbol replaced at the
beginning and repeat the process.
In the new state, check if the symbol at the corresponding position from the end matches the one
at the beginning. If they match, continue; otherwise, reject the string.
Move left and repeat the process until the entire string is processed.
If all symbols match as expected, accept the string.
Assumption: We will replace 0 by Y and 1 by X.
Approach Used - First check the first symbol, if it's 0 then replace it by Y and by X if it's 1.
Then go to the end of string. So last symbol is same as first. We replace it also by X or Y
depending on it. Now again come back to the position next to the symbol replace from the
starting and repeat the same process as told above. One important thing to note is that since wr is
reverse of w of both of them will have equal number of symbols. Every time replace a nth
symbol from beginning of string, replace a corresponding nth symbol from the end.
 Step-1: If symbol is 0 replace it by Y and move right, Go to state Q2 If symbol is 1 replace it
by X and move right, Go to state Q1
 Step-2: If symbol is 0 replace it by 0 and move right, remain on same state If symbol is 1
replace it by 1 and move right, remain on same state
------------------------------------------------------------------- If symbol is X replace it by X and
move right, Go to state Q3 If symbol is Y replace it by Y and move right, Go to state Q3 If
symbol is $ replace it by $ and move right, Go to state Q3
 Step-3: If symbol is 1 replace it by X and move left, Go to state Q4 If symbol is 0 replace it
by Y and move left, Go to state Q5
 Step-4: If symbol is 1 replace it by 1 and move left If symbol is 0 replace it by 0 and move
left Remain on same state
 Step-5: If symbol is X replace it by X and move right If symbol is Y replace it by Y and
move right Go to state Q0
 Step-6: If symbol is X replace it by X and move right If symbol is Y replace it by Y and
move right Go to state Q6 ELSE Go to step 1
 Step-7: If symbol is X replace it by X and move right, Remain on same state If symbol is Y
replace it by Y and move right, Remain on same state If symbol is $ replace it by $ and move
left, STRING IS ACCEPTED, GO TO FINAL STATE Q7

Another solution for the given problem:

If we look at the problem ,it is nothing but an even palindrome so the following is an another

checks that the language L = {wwr | w ∈ {0, 1}} is a palindrome or not.

solution for the given language. Here I have consider Blank as B. The following turing machine

 Step 1- if first symbol is "0" then it replace by the blank symbol goes to the right till it finds
the blank and by checking that the symbol is blank or not .
 Step2- after getting the last symbol go to the one step left and check that symbol it is "0" or
not and
 step3- if the last symbol is "0" then replace it with blank symbol and keep going left until it
find the blank symbol
 step4- after finding the left most blank symbol go one step right and check it "0" or "1"
 Step 5- if we get "1" then replace it by the blank symbol and goes to the right until it find the
blank symbol.
 Step 6- if it find the blank symbol then take one step left and check that symbol is "1" or
not .If it is "1" then replace it with the blank symbol.
 step7- after replacing it goes to the left and find the blank symbol after finding the blank
symbol take one step right and check if the symbol is "1" or "0"
 Step 8- repeat the above steps until the whole string become blank.
 Construct a Turing Machine for language L = {0n1n2n | n≥1}
Last Updated : 08 May, 2018





Prerequisite - Turing Machine The language L = {0n1n2n | n≥1} represents a kind of language
where we use only 3 character, i.e., 0, 1 and 2. In the beginning language has some number of 0's
followed by equal number of 1's and then followed by equal number of 2's. Any such string
which falls in this category will be accepted by this language. The beginning and end of string is
marked by $ sign. Examples -
Input : 0 0 1 1 2 2
Output : Accepted

Input : 0 0 0 1 1 1 2 2 2 2
Output : Not accepted
Assumption: We will replace 0 by X, 1 by Y and 2 by Z Approach used - First replace a 0 from
front by X, then keep moving right till you find a 1 and replace this 1 by Y. Again, keep moving
right till you find a 2, replace it by Z and move left. Now keep moving left till you find a X.
When you find it, move a right, then follow the same procedure as above. A condition comes
when you find a X immediately followed by a Y. At this point we keep moving right and keep on
checking that all 1's and 2's have been converted to Y and Z. If not then string is not accepted. If
we reach $ then string is accepted.
 Step-1: Replace 0 by X and move right, Go to state Q1.
 Step-2: Replace 0 by 0 and move right, Remain on same state Replace Y by Y and move
right, Remain on same state Replace 1 by Y and move right, go to state Q2.
 Step-3: Replace 1 by 1 and move right, Remain on same state Replace Z by Z and move
right, Remain on same state Replace 2 by Z and move right, go to state Q3.
 Step-4: Replace 1 by 1 and move left, Remain on same state Replace 0 by 0 and move left,
Remain on same state Replace Z by Z and move left, Remain on same state Replace Y by Y
and move left, Remain on same state Replace X by X and move right, go to state Q0.
 Step-5: If symbol is Y replace it by Y and move right and Go to state Q4 Else go to step 1
 Step-6: Replace Z by Z and move right, Remain on same state Replace Y by Y and move
right, Remain on same state If symbol is $ replace it by $ and move left, STRING IS
ACCEPTED, GO TO FINAL STATE Q5
 Construct a Turing machine for L = {aibjck | i*j = k; i, j, k ≥ 1}
Last Updated : 13 Jun, 2024





Prerequisite – Turing Machine

In a given language, L = {aibjck | i*j = k; i, j, k ≥ 1}, where every string of 'a', 'b' and 'c' has a
certain number of a's, then a certain number of b's and then a certain number of c's. The
condition is that each of these 3 symbols should occur at least once. 'a' and 'b' can occur
however many times, but the occurrences of 'c' must be equal to the product of occurrences of
'a' and occurrences of 'b'. Assume that string is ending with '$'.

Examples -

Input: a a b b b c c c c c c
Here a = 2, b = 3, c = 2 * 3 = 6
Output: NOT ACCEPTED

Input: a a b b c c c
 Here a = 2, b = 2, c = 3 but c should be 4 (c=2*2 must be 4 but here c=3)
Output: NOT ACCEPTED

Approach used - Scan the input from the left.

1. First, replace an 'a' with 'X' and move 1 step right. Then skip all the a's and move right.
2. When the pointer reaches the first 'b' stop. Replace one 'b' with 'Y', then move right
skipping all intermediate b's and corresponding to the replaced 'b' now replace one 'c' with
'Z' and move left.
3. Now move towards the left skipping all 'Z' and 'b' in the way.
4. When the pointer reaches the most recent 'Y' move right.
5. If the pointer is pointing at 'b' then repeat steps 2 to 4, else if the pointer is pointing at 'Z'
then move towards left while replacing all 'Y' to 'b' and skipping all a's.
6. When the pointer comes to the most recent 'X' move one step right.
7. If the pointer is still pointing to 'a' then repeat all the above steps, else if the pointer is at 'y'
then move towards right skipping all 'y' and 'Z'.
8. When $ is reached then move left. The string is ACCEPTED.
 Construct a Turing Machine for language L = {ww | w ∈ {0,1}}
Last Updated : 29 Oct, 2021





The language L = {ww | w ∈ {0, 1}} tells that every string of 0's and 1's which is followed by
Prerequisite - Turing Machine

itself falls under this language. The logic for solving this problem can be divided into 2 parts:

1. Finding the mid point of the string

2. After we have found the mid point we match the symbols

Example - Lets understand it with the help of an example. Lets string 1 0 1 1 0 1, so w = 1 0 1

and string is of form (ww).
The first thing that we do is to find the midpoint. For this, we convert 1 in the beginning into Y
and move right till the end of the string. Here we convert 1 into y.

Now our string would look like Y 0 1 1 0 Y. Now move left till, find a X or Y. When we do so,
convert the 0 or 1 right of it to X or Y respectively and then do the same on the right end. Now
our string would look like Y X 1 1 X Y. Thereafter, convert these 1's also and finally it would
look like Y X Y Y X Y.

At this point, you have achieved the first objective which was to find the midpoint. Now
convert all X and Y on the left of midpoint into 0 and 1 respectively, so string becomes 1 0 1 Y
X Y. Now, convert the 1 into Y and move right till, find Y in the beginning of the right part of
the string and convert this Y into a blank (denoted by B). Now string looks like Y 0 1 B X Y.

Similarly, apply this on 0 and x followed by 1 and Y. After this string looks like Y X Y B B B.
Now that you have no 0 and 1 and all X and Y on the right part of the string are converted into
blanks so our string will be accepted.

Assumption: We will replace 0 by X and 1 by Y.

Approach Used -
The first thing is to find the midpoint of the string, convert a 0 or 1 from the beginning of the
string into X or Y respectively and a corresponding 0 or 1 into X or Y from the end of the
string. After continuously doing it a point is reached when all 0's and 1's have been converted
into X and Y respectively. At this point, you are on the midpoint of the string. So, our first
objective is fulfilled.
Now, convert all X's and Y's on the left of the midpoint into 0's and 1's. At this point the first
half the string is in the form of 0 and 1. The second half of the string is in the form of X and
Y.

Now, start from the beginning of the string. If you have a 0 then convert it into X and move
right till reaching the second half, here if we find X then convert it into a blank(B). Then
traverse back till find an X or a Y. We convert the 0 or 1 on the right of it into X or Y
respectively and correspondingly, convert its X or Y in the second half of string into a
blank(B).

Keep doing this till converted all symbols on the left part of the string into X and Y and all
symbols on the right of string into blanks. If any one part is completely converted but still
some symbols in the other half are left unchanged then the string will not be accepted. If you
did not find an X or Y in the second half for a corresponding 0 or 1 respectively in the first
half. Then also string will not be accepted.

Examples:

Input : 1 1 0 0 1 1 0 0
Output : Accepted

Input : 1 0 1 1 1 0 1
Output : Not accepted

 Step-1:
If the symbol is 0 replace it by X and move right
If the symbol is 1 replace it by Y and move right,
Go to state Q1 and step 2
---------------------------------------------
If the symbol is X replace it by X and move left or
If the symbol is Y replace it by Y and move left,
Go to state Q4 and step 5

 Step-2:
If the symbol is 0 replace it by 0 and move right, remain on the same state
If the symbol is 1 replace it by 1 and move right, remain on the same state
---------------------------------------------
If the symbol is X replace it by X and move left or
 If the symbol is Y replace it by Y and move left or
If the symbol is $ replace it by $ and move left, Go to state Q2 and step 3

 Step-3:
If symbol is 0 replace it by X and move left, or
If symbol is 1 replace it by Y and move left,
Go to state Q3 and step 4

 Step-4:
If the symbol is 0 replace it by 0 and move left, remain on the same state
If the symbol is 1 replace it by 1 and move left, remain on the same state
---------------------------------------------
If the symbol is X replace it by X and move right or
If the symbol is Y replace it by Y and move right,
Go to state Q0 and step 1

 Step-5:
If symbol is X replace it by X and move left or
If symbol is Y replace it by Y and move left
Go to state Q4 and step 6

 Step-6:
If symbol is X replace it by 0 and move left, remain on same state
If symbol is Y replace it by 1 and move left, remain on same state
- - - - - - - - - -- - - - - - - - - - --
If symbol is $ replace it by $ and move right
Go to state Q4 and step 7

 Step-7:
If symbol is 0 replace it by X and move right, go to state Q6 and step 8
If symbol is 1 replace it by Y and move right, go to state Q7 and step 9
- - - - - - - - - -- - - - - - - - - - --
If symbol is B replace it by B and move left, STRING ACCEPTED, GO TO FINAL
STATE Q9
 Step-8:
If symbol is 0 replace it by 0 and move right, remain on same state
If symbol is 1 replace it by 1 and move right, remain on same state
If symbol is B replace it by B and move right, remain on same state
- -- - - - - - - - - - - - - - - - - - -
If symbol is X replace it by B and move left
Go to state Q8 and step 10

 Step-9:

If symbol is 0 replace it by 0 and move right, remain on same state

If symbol is 1 replace it by 1 and move right, remain on same state
If symbol is B replace it by B and move right, remain on same state
- -- - - - - - - - - - - - - - - - - - -
If symbol is Y replace it by B and move left
Go to state Q8 and step 10

 Step-10:
If symbol is 0 replace it by 0 and move left, remain on same state
If symbol is 1 replace it by 1 and move left, remain on same state
If symbol is B replace it by B and move left, remain on same state
- -- - - - - - - - - - - - - - - - - - -
If symbol is Y replace it by Y and move right or
If symbol is X replace it by X and move right
Go to state Q5 and step 7
 Construct Turing machine for L = {an bm a(n+m) | n,m≥1}
Last Updated : 31 May, 2018





L = {an bm a(n+m) | n,m≥1} represents a kind of language where we use only 2 character, i.e., a and
b. The first part of language can be any number of "a" (at least 1). The second part be any
number of "b" (at least 1). The third part of language is a number of "a" whose count is sum of
count of a's in first part of string and count of b's in second part of string . Any such string which
falls in this category will be accepted by this language. The beginning and end of string is
marked by $ sign. Examples:
Input : a a b b b a a a a a // n=2, m=3
Output : Accepted

Input : a a b a a a a // n=2, m=1

Output : Not accepted
Approach used -
1. Convert "a" in first part into "X" and then move right ignoring all intermediate symbols.
When "a" is encountered just after "b" then convert it into "Z" and move left and stop at the
position just next to "X". Repeat the above procedure.

2. When all a's in first part have been converted then apply the same process on second part.
Convert "b" into "Y" and "a" into "Z" in the third part.

When entire first and second part has been converted and if third part is also converted then
string will be accepted else not. Steps - Step-0: Convert "a" into "X", move right and go to state
1. If symbol is "b", ignore it, move right and go to state-4. Step-1: If symbol is "a", ignore it and
move right, remain on same state. If symbol is "b", ignore it, move right and go to state-2. Step-
2: If symbol is "Z", ignore it and move right, remain on same state. If symbol is "b", ignore it
and move right, remain on same state and if symbol is "a", convert it into "Z", move left and go
to state-3. Step-3: If symbol is "Z", ignore it and move left, remain on same state. If symbol is
"b", ignore it and move left, remain on same state. If symbol is "a", ignore it and move left,
remain on same state, and if symbol is "X", ignore it and move right, go to state-0. Step-4: If
symbol is "b", ignore it and move left, go to state 5, and if symbol is "Z", ignore it and move left,
go to state-5. Step-5: Convert "b" into "Y", move right and go to state 6, and if symbol is "Z",
ignore it and move right, go to state-8. Step-6: If symbol is "Z", ignore it and move right, remain
on same state. If symbol is "b", ignore it and move right, remain on same state, and if symbol is
"a", convert it into "Z", move left and go to state-7. Step-7: If symbol is "Z", ignore it and move
left, remain on same state. If symbol is "b", ignore it and move left, remain on same state, and if
symbol is "Y", ignore it and move right, go to state-5. Step-8: If symbol is "Z", ignore it and
move right, remain on same state, and if symbol is "$", ignore it and move left, go to state-9.

Step-9: Strin g ACCEPTED