Turing Machine: Features, Components, and Examples

Turing Machine Turing machine was invented in 1936 by Alan Turing. It is an accepting device which accepts Recursive Enumerable Language generated by type 0 grammar. There are various features of the Turing machine: It has an external memory which remembers arbitrary long sequence of input. It has unlimited memory capability. The model has a facility by which the input at left or right on the tape can be read easily. The machine can produce a certain output based on its input. Sometimes it may be required that the same input has to be used to generate the output. So in this machine, the distinction between input and output has been removed. Thus a common set of alphabets can be used for the Turing machine.

Turing Machine A Turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions. TM is more powerful than Pushdown Automata. Power of various machines is given as: FA DPDA NPDA Post Machine = Turing machine

Formal definition of Turing machine A Turing machine can be defined as a collection of 7 components: Q: the finite set of states : the finite set of input symbols : the tape symbol q0: the initial state F: a set of final states B: a blank symbol used as a end marker for input : a transition or mapping function. The mapping function shows the mapping from states of finite automata and input symbol on the tape to the next states, external symbols and the direction for moving the tape head. This is known as a triple or a program for Turing machine. (q0, a) (q1, A, R) That means in q0 state, if we read symbol 'a' then it will go to state q1, replaced a by X and move ahead right(R stands for right).

Example Construct TM for the language L ={0n1n} where n>=1. Solution: We have already solved this problem by PDA. In PDA, we have a stack to remember the previous symbol. The main advantage of the Turing machine is we have a tape head which can be moved forward or backward, and the input tape can be scanned. The simple logic which we will apply is read out each '0' mark it by A and then move ahead along with the input tape and find out 1 convert it to B. Now, repeat this process for all a's and b's. Now we will see how this turing machine work for 0011.

The simulation for 0011 can be shown as below: Now, we will see how this Turing machine will works for 0011. Initially, state is q0 and head points to 0 as: The move will be (q0, 0) = (q1, A, R) which means it will go to state q1, replaced 0 by A and head will move to the right as: The move will be (q1, 0) = (q1, 0, R) which means it will not change any symbol, remain in the same state and move to the right as:

The move will be (q1, 1) = (q2, B, L) which means it will go to state q2, replaced 1 by B and head will move to left as: Now move will be (q2, 0) = (q2, 0, L) which means it will not change any symbol, remain in the same state and move to left as: The move will be (q2, A) = (q0, A, R), it means will go to state q0, replaced A by A and head will move to the right as: The move will be (q0, 0) = (q1, A, R) which means it will go to state q1, replaced 0 by A, and head will move to right as:

The move will be (q1, B) = (q1, B, R) which means it will not change any symbol, remain in the same state and move to right as: The move will be (q1, 1) = (q2, B, L) which means it will go to state q2, replaced 1 by B and head will move to left as: The move (q2, B) = (q2, B, L) which means it will not change any symbol, remain in the same state and move to left as: Now immediately before B is A that means all the 0?s are market by A. So we will move right to ensure that no 1 is present. The move will be (q2, A) = (q0, A, R) which means it will go to state q0, will not change any symbol, and move to right as:

The move (q0, B) = (q3, B, R) which means it will go to state q3, will not change any symbol, and move to right as: The move (q3, B) = (q3, B, R) which means it will not change any symbol, remain in the same state and move to right as: The move (q3, ) = (q4, , R) which means it will go to state q4 which is the HALT state and HALT state is always an accept state for any TM. The same TM can be represented by Transition Diagram:

Basic Model of Turing machine The turning machine can be modeled with the help of the following representation. 1. The input tape is having an infinite number of cells, each cell containing one input symbol and thus the input string can be placed on tape. The empty tape is filled by blank characters. 2. The finite control and the tape head which is responsible for reading the current input symbol. The tape head can move to left to right.

Basic Model of Turing machine 3.A finite set of states through which machine has to undergo. 4. Finite set of symbols called external symbols which are used in building the logic of Turing machine

Language accepted by Turing machine The Turing machine accepts all the language even though they are recursively enumerable. Recursive means repeating the same set of rules for any number of times and enumerable means a list of elements. The TM also accepts the computable functions, such as addition, multiplication, subtraction, division, power function, and many more.

Example Construct a Turing machine which accepts the language of aba over = {a, b}. Solution: We will assume that on input tape the string 'aba' is placed like this: The tape head will read out the sequence up to the characters. If the tape head is readout 'aba' string then TM will halt after reading . Now, we will see how this Turing machine will work for aba. Initially, state is q0 and head points to a as:

The move will be (q0, a) = (q1, A, R) which means it will go to state q1, replaced a by A and head will move to right as: The move will be (q1, b) = (q2, B, R) which means it will go to state q2, replaced b by B and head will move to right as: The move will be (q2, a) = (q3, A, R) which means it will go to state q3, replaced a by A and head will move to right as: The move (q3, ) = (q4, , N) which means it will go to state q4 which is the HALT state and HALT state is always an accept state for any TM.

The same TM can be represented by Transition Table: States a b q0 (q1, A, R) q1 (q2, B, R) q2 (q3, A, R) q3 (q4, , N) q4 The same TM can be represented by Transition Diagram:

Example 1 Construct a TM for the language L = {0n1n2n} where n 1 Solution: L = {0n1n2n| n 1} represents language where we use only 3 character, i.e., 0, 1 and 2. In this, some number of 0's followed by an equal number of 1's and then followed by an equal number of 2's. Any type of string which falls in this category will be accepted by this language. The simulation for 001122 can be shown as below: Now, we will see how this Turing machine will work for 001122. Initially, state is q0 and head points to 0 as: 0 0 1 1 2 2 B

The move will be (q0, 0) = (q1, X, R) which means it will go to state q1, replaced 0 by A and head will move to the right as: X 0 1 1 2 2 B The move will be (q1, 0) = (q1, 0, R) which means it will not change any symbol, remain in the same state and move to the right as: X 0 1 1 2 2 B The move will be (q1, 1) = (q2, Y, R) which means it will go to state q2, replaced 1 by B and head will move to right as: X 0 Y 1 2 2 B

The move will be (q2, 1) = (q2, 1, R) which means it will not change any symbol, remain in the same state and move to right as: X 0 Y 1 2 2 B The move will be (q2, 2) = (q3, Z, R) which means it will go to state q3, replaced 2 by C and head will move to right as: X 0 Y 1 Z 2 B Now move (q3, 2) = (q3, 2, L) and (q3, Z) = (q3, Z, L) and (q3, 1) = (q3, 1, L) and (q3, Y) = (q3, Y, L) and (q3, 0) = (q3, 0, L), and then move (q3, X) = (q0, X, R), it means will go to state q0, replaced X by X and head will move to right as: X 0 Y 1 Z 2 B

The move will be (q0, 0) = (q1, X, R) which means it will go to state q1, replaced 0 by X, and head will move to right as: X X Y 1 Z 2 B The move will be (q1, Y) = (q1, Y, R) which means it will not change any symbol, remain in the same state and move to right as: X X Y 1 Z 2 B The move will be (q1, 1) = (q2, Y, R) which means it will go to state q2, replaced 1 by B and head will move to right as: X X Y Y Z 2 B

The move will be (q2, Z) = (q2, Z, R) which means it will not change any symbol, remain in the same state and move to right as: X X Y Y Z 2 B The move will be (q2, 2) = (q3, Z, L) which means it will go to state q3, replaced 2 by Z and head will move to left until we reached A as: X X Y Y Z Z B Immediately before B is A that means all the 0's are market by A. So we will move right to ensure that no 1 or 2 is present. The move will be (q2, y) = (q4, y, R) which means it will go to state q4, will not change any symbol, and move to right as: X X Y Y Z Z B

The move will be (q4, Y) = (q4, Y, R) and (q4, Z) = (q4, Z, R) which means it will not change any symbol, remain in the same state and move to right as: X X Y Y Z Z B The move (q4, X) = (q5, X, R) which means it will go to state q5 which is the HALT state and HALT state is always an accept state for any TM. X X Y Y Z Z B

Example 2 Design Turing Machine which accepts all strings of the form anbn for n>=1 and rejects all other strings. Solution: Let us consider a string a3b3 Algorithm: 1. Leftmost a will be changed to x 2. Rightmost b will be changed to y 3. Head will come back to first a B a a a b b b B B x a a b b y B B x a a b b y B B x a a b b y B B x x a b b b B B x x x b y y B

Transition Diagram a b x y B q0 (q1,x , R) (q4,y , N) q1 (q1,a , R) (q1,b , R) (q2,y, L) (q2,B, L) q2 (q3,y, L) q3 (q3,a, L) (q3,b, L) (q0,x, R) q4 q4 q4 q4 q4 q4 Transition Table

Example 2 Design Turing Machine for accepting the language {L= aibj | i<j} for n>=1 and rejects all other strings. Transition Diagram a b x y B q0 (q1, x , R) (q4, y , N) q1 (q1, a , R) (q1, b , R) (q2, y, L) (q2, B, L) q2 (q3, y, L) q3 (q3, a, L) (q3, b, L) (q0, x, R) q4 q4 q4 q4 (q5, y, N) (q5, B, N) q5 q5 q5 q5 q5 q5 Transition Table

Example 3 Design a Turing Machine to make a copy of string over {0,1} Solution: B 1 1 0 # B 0 B y 1 0 0 # 1 B B y y 0 0 # 1 1 B B y y x 0 # 1 1 0 B B y y x x # 1 1 0 0 Algorithm: 1. Copy the string after # symbol. 2. Read 1 or 0 from given string in given sequence and copy the same symbol after # symbol Means replace the blank symbol with input symbol. 3. Repeat step 2 till entire string gets copied after # symbol

0 1 # B x y q0 (q1, x, R) (q2, y, R) (q4, #, N) q1 (q1, 0, R) (q1, 1, R) (q1, #, R) (q3, 0, L) q2 (q2, 0, R) (q2, 1, R) (q2, #, R) (q3, 1, L) q3 (q3, 0, L) (q3, 1, L) (q3, #, L) (q0, x, R) (q0, y, R) q4 * q4 q4 q4 q4 q4 q4

Example 4 Design right shift Turing Machine over alphabet {0,1} Solution: A right shift Turing Machine will shift an input string right by 1 place. B 1 0 1 0 B B 1 0 1 0 B B 1 0 1 B 0 B 1 0 1 B 0 B 1 0 B 1 0 B 1 0 B 1 0 B 1 B 0 1 0 B 1 B 0 1 0 B B 1 0 1 0

B B 1 0 1 0 0 1 B q0 (q0 , 0, R) (q0 , 1, R) (q1 , B, L) q1 (q2 , B, R) (q3 , B, R) (q5 , B, N) q2 (q4 , 0, L) q3 (q4 , 1, L) q4 (q1 , B, L) q5 * q5 q5 q5

Example 5 Construct a TM for checking well formedness of parenthesis Solution: Consider the input as (()())() B ( ( ) ( ) ) ( ) B B ( x x ( ) ) ( ) B B ( x x x x ) ( ) B B x x x x x x ( ) B B x x x x x x x x B Algorithm: 1.In each cycle leftmost ) is written as x then head moves left to locate the nearer ( and it is changed to x 2. Repeat this procedure till all parenthesis get replaced with x.

B ( ( ) ( ) ) ( )B B ( x x ( ) ) ( )B B ( x x x x ) ( ) B B x x x x x x ( ) B B x x x x x x x x B ( ) x B q0 (q0 , ( , R) (q1, x , L) (q0 , x, R) (q2 , B, L) q1 (q0 , x , R) (q1 , x , L) q2 (q2 , x , L) (q3 , B , R) q3 * q3 q3 q3 q3

Example 6 Design Turing Machine to check whether a string over {a,b} contains equal number of a s and b s Algorithm: 1. Locate first a or b. 2. If it is a then locate b and rewrite them as x. 3. If it is b then locate a and rewrite them as x. 4. Repeat the steps 1 to 3 till every a or b is rewritten as x.

a b x B q0 (q1, x, R) (q2, x, R) (q0, x, R) (q4, B,N) q1 (q1, a ,R) (q3, x ,L) (q1, x ,R) q2 (q3, x ,L) (q2, B ,R) (q2, x ,R) q3 (q3, a , L) (q1, b ,L) (q3, x ,L) (q0, B ,R) q4 q4 q4 q4 q4

Example 7 Design TM that recognizes string containing aba as a substring

Example 8 Design Finite automata and corresponding turing machine for language L = {x {a,b}*|x ends with aba

Example 8 Design Turing Machine which recognizes palindromes over alphabet {a,b} Solution: Palindrome can be of following form wwR , wawR or wbwR E.g L = {a, b, aa, bb, aba , bab, aaa, bbb, abba, baab, abaaba, ..} Algorithm: 1. Match first character with last character and erase both characters. 2. Repeat step 1 till all characters get erased.

a b a a b a B B b a a b a B B b a a b B B B b a a b B B B B a a b B B B B a a b B B B B B a B B B B B a a B B B B B B a B B B B B B B B B B

B B B B B B B

Example 9 Design TM for reversing a string over an alphabet {0,1} Solution: copy the given string in reverse order to get reverse of given string B 0 1 1 B B 0 1 1 B B 0 1 x B B 0 1 x 1 B B 0 1 x 1 B B 0 x x 1 1 B B 0 x x 1 1 B B x x x 1 1 B B x x x 1 1 0 B B 0 x x 1 1 B B B B B B B B

B 1

Turing Machine as a Computer Function Turing machine can be used for computation. It can perform the several operations like addition, subtraction, multiplication and division. Number representation: The unary number system is often used while computing a function using Turing Machine. The unary system uses only one symbol. Representation of same decimal numbers in unary system is given below: Decimal Number Unary Number 0 B (blank symbol) 1 0 2 00 3 000 n 0 .n times 0

Example 1 Design Turing Machine to find 2 s complement of binary machine. Solution: The 2 s complement of binary number can be found by not changing bits from right end till the 1st one then complement all remaining bits. Example: 0 0 1 0 0 1 0 0 2 s complement is 11011100 No change Complement the bits 1. Locate the last bit (right most bit) 2. Move left till first 1. 3. Complement the remaining bits while moving left till blank symbol. Algorithm:

B 0 0 1 0 0 1 0 0 B B 0 0 1 0 0 1 0 0 B B 0 0 1 0 0 1 0 0 B 0 0 0 1 0 0 1 0 0 B B 0 0 1 0 0 1 0 0 B B 0 0 1 0 0 1 0 0 B B 0 0 1 0 1 1 0 0 B B 0 0 1 1 1 1 0 0 B B 0 1 0 1 1 1 0 0 B B 0 0 0 1 1 1 0 0 B B 1 1 0 1 1 1 0 0 B

0 1 B q0 (q0, 0 , R) (q0, 1 , R) (q1, B , L) q1 (q1, 0 , L) (q2, 1 , L) (q3, B , R) q2 (q2, 1 , L) (q2, 0 , L) (q3, B , R) q3* q3 q3 q3

Example 2 Design Turing Machine to compute proper subtraction of two unary numbers . The proper subtraction function f is defined as follows: f(m,n) = m-n if m>n else 0 Solution: Let us consider two numbers 4 (0000) and 2(00) We will take bigger number at left hand side and smaller number at right hand side on tape. Algorithm: 1. Erase leftmost 0. 2. Erase rightmost 0. 3. Repeat step 1 and 2 till all 0 s at right hand side get erased.

B 0 0 0 0 # 0 0 B B B 0 0 0 # 0 0 B B B 0 0 0 # 0 B B B B B 0 0 # 0 B B B B B 0 0 # B B B

0 # B q0 (q1 , B , R) (q4 , B , R) -- q1 (q1 , 0 , R) (q1 , # , R) (q2 , B , L) q2 (q3 , B , L) (q5 , 0 , N) __ q3 (q3 , 0 , L) (q3 , # , L) (q0 , B , R) q4 (q4 , B , R) -- (q5 , B , N) q5 * q5 q5 q5

Example 3 Compute multiplication of two unary numbers. Solution: Lets consider two numbers as 3 and 4 . Here we will copy four(second number) zeros for every cycle and we repeat this step for 3(first number) cycles B 0 0 0 # 0 0 0 0 # B B x 0 0 # x 0 0 0 # 0 B B x 0 0 # 0 x 0 0 # 0 0 B B x 0 0 # 0 0 x 0 # 0 0 0 B B x 0 0 # 0 0 0 x # 0 0 0 0 B Cycle 1: 1 *4 = 4 B 0 x 0 # x 0 0 0 # 0 0 0 0 0 B B 0 x 0 # 0 x 0 0 # 0 0 0 0 0 0 B Cycle 2: 2*4 = 8 B 0 x 0 # 0 0 x 0 # 0 0 0 0 0 0 0 B B 0 x 0 # 0 0 0 x # 0 0 0 0 0 0 0 0 B B 0 0 x # x 0 0 0 # 0 0 0 0 0 0 0 0 0 B B 0 0 x # 0 x 0 0 # 0 0 0 0 0 0 0 0 0 0 B Cycle 3: 3*4 = 12 B 0 0 x # 0 0 x 0 # 0 0 0 0 0 0 0 0 0 0 0 B B 0 0 x # 0 0 0 x # 0 0 0 0 0 0 0 0 0 0 0 0 B

B 0 0 0 # 0 0 0 0 # 0 0 0 0 0 0 0 0 0 0 0 0 B B B B

Example 4 Design TM to add two unary numbers. Solution: Addition of two unary numbers can be performed through append operation. Let s consider two numbers 4 and 5: B 0 0 0 0 # 0 0 0 0 0 B B B 0 0 0 # 0 0 0 0 0 B B B 0 0 0 # 0 0 0 0 0 0 B B B B 0 0 # 0 0 0 0 0 0 B B B B 0 0 # 0 0 0 0 0 0 0 B B B B B 0 # 0 0 0 0 0 0 0 B B B B B 0 # 0 0 0 0 0 0 0 0 B B B B B B # 0 0 0 0 0 0 0 0 B B B B B B # 0 0 0 0 0 0 0 0 0 B B B B B B 0 0 0 0 0 0 0 0 0 B

B B B B B B 0 0 0 0 0 0 0 0 0 B 0 # B q0 (q1 , B , R) (q3 , B, R) -- q1 (q1 , 0 , R) (q1 , # , R) (q2 , 0 , L) q2 (q2 , 0 , L) (q2 , # , L) (q0 , B , R) q3* q3 q3 q3