Short Notes: Turing Machine | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


Turing Machine
The languages accepted by Turing machine are said to be recursively enumerable. 
A Turing Machine (TM) is a device with a finite amount of read only hard memory 
(states) and an unbounded amount of read/write tape memory.
• Recursive languages are closed under complementation, union, intersection, 
concatenation and Kleene closure.
• A Turing machine is said to be partially decide a problem, if the following two 
conditions are satisfied.
1. The problem is a decision problem.
2. The Turing machine accepts as given input if and only if the problem has 
an answer 'yes' for the input that is the Turing machine accepts the 
language L.
• A Turing machine is said to be decide a problem, if it partially decides the 
problem and all its computations are halting computations.
A language L is Turing-recognisable if there is a Turing machine M such that 
L=L(M).
A language L is Turing-decidable if there is a Turing machine M such that M 
decides L.
Turing-decidable language is also Turing-recognisable, but Turing-recognisable may 
not be Turing-decidable.
A language is recursively enumerable iff it is Turing-enumerable.
Universal Turing Machine (UTM)
Page 2


Turing Machine
The languages accepted by Turing machine are said to be recursively enumerable. 
A Turing Machine (TM) is a device with a finite amount of read only hard memory 
(states) and an unbounded amount of read/write tape memory.
• Recursive languages are closed under complementation, union, intersection, 
concatenation and Kleene closure.
• A Turing machine is said to be partially decide a problem, if the following two 
conditions are satisfied.
1. The problem is a decision problem.
2. The Turing machine accepts as given input if and only if the problem has 
an answer 'yes' for the input that is the Turing machine accepts the 
language L.
• A Turing machine is said to be decide a problem, if it partially decides the 
problem and all its computations are halting computations.
A language L is Turing-recognisable if there is a Turing machine M such that 
L=L(M).
A language L is Turing-decidable if there is a Turing machine M such that M 
decides L.
Turing-decidable language is also Turing-recognisable, but Turing-recognisable may 
not be Turing-decidable.
A language is recursively enumerable iff it is Turing-enumerable.
Universal Turing Machine (UTM)
• A UTM is a specified Turing machine that can simulate the behaviour of any 
TM.
• A UTM is capable of running any algorithm.
For simulating even a simple behaviour, a Universal Turing Machine must have a 
large number of states. If we modify our basic model by increasing the number of 
read/write heads, the number of dimensions of input tape and adding a special 
purpose memory, then we can design a Universal Turing Machine.
Definition of Turing Machine
A Turing Machine (TM) is defined as 7-tuples.
TM = (Q, Z, T, 5, q0, b, F),
where, Q is a finite non-empty set of states, Z is a non-empty set of input symbols 
(alphabets) which is a subset of r and b e Z, r is a finite non-empty set of tape 
symbols, 5 is the transition function which maps (Q x r) to (Q x r x {L, R}), q0 is the 
initial state and qo e Q, b is the blank and b e r, F is the set of final states and F c 
Q.
Transition Function of a Turing Machine
The transition function Q x r — ? Q x r x {L, R} states that if a Turing machine is in 
some state (from set Q), by taking a tape symbol (from set I"), it goes to some next 
state (from set 'i) by overwriting (replacing) the current symbol by another or same 
symbol and the read/write head moves one cell either left (L) or right (R) along the 
tape.
1. {fl"6nc" | n > 1}
Solution:
M = {{qa.qa-<lb,Qc,Qy,qz,(lf}- {«, b , c}, (a, 6, c, X , Y, Z }, 6, q 0. D. {qf })
Page 3


Turing Machine
The languages accepted by Turing machine are said to be recursively enumerable. 
A Turing Machine (TM) is a device with a finite amount of read only hard memory 
(states) and an unbounded amount of read/write tape memory.
• Recursive languages are closed under complementation, union, intersection, 
concatenation and Kleene closure.
• A Turing machine is said to be partially decide a problem, if the following two 
conditions are satisfied.
1. The problem is a decision problem.
2. The Turing machine accepts as given input if and only if the problem has 
an answer 'yes' for the input that is the Turing machine accepts the 
language L.
• A Turing machine is said to be decide a problem, if it partially decides the 
problem and all its computations are halting computations.
A language L is Turing-recognisable if there is a Turing machine M such that 
L=L(M).
A language L is Turing-decidable if there is a Turing machine M such that M 
decides L.
Turing-decidable language is also Turing-recognisable, but Turing-recognisable may 
not be Turing-decidable.
A language is recursively enumerable iff it is Turing-enumerable.
Universal Turing Machine (UTM)
• A UTM is a specified Turing machine that can simulate the behaviour of any 
TM.
• A UTM is capable of running any algorithm.
For simulating even a simple behaviour, a Universal Turing Machine must have a 
large number of states. If we modify our basic model by increasing the number of 
read/write heads, the number of dimensions of input tape and adding a special 
purpose memory, then we can design a Universal Turing Machine.
Definition of Turing Machine
A Turing Machine (TM) is defined as 7-tuples.
TM = (Q, Z, T, 5, q0, b, F),
where, Q is a finite non-empty set of states, Z is a non-empty set of input symbols 
(alphabets) which is a subset of r and b e Z, r is a finite non-empty set of tape 
symbols, 5 is the transition function which maps (Q x r) to (Q x r x {L, R}), q0 is the 
initial state and qo e Q, b is the blank and b e r, F is the set of final states and F c 
Q.
Transition Function of a Turing Machine
The transition function Q x r — ? Q x r x {L, R} states that if a Turing machine is in 
some state (from set Q), by taking a tape symbol (from set I"), it goes to some next 
state (from set 'i) by overwriting (replacing) the current symbol by another or same 
symbol and the read/write head moves one cell either left (L) or right (R) along the 
tape.
1. {fl"6nc" | n > 1}
Solution:
M = {{qa.qa-<lb,Qc,Qy,qz,(lf}- {«, b , c}, (a, 6, c, X , Y, Z }, 6, q 0. D. {qf })
2. {wwR | w is any string of 0’s and l ‘s}
Solution:
A! = ({qintU < ? o , <7i, <7o«, <7i«, ^bocfc, <7/}, { 0 , 1 } , {0, 1 } , 6, qinit, B, {qf})
S t a t e 0 1 D
Qinit ( < Q o, B- B) (<7i, £ .7 ? ) (qf, B , R)
Q a {qoA)-R) (<7o, 1, /?)
( q o R . B . L )
4 t
(< 71,0,/?)
(<7i, 1, B)
(qX R ,B ,L )
(qbacki B, L) - -
q VR - (qbacki B, L) -
q b a c .k Q b a c k i 0 , L ) (qbacki 1, B) ( q i n i t, B, /? )
3. Construct a TM that accepts the language A = {()(2 A n ) | n>=0}
A = { 02" | h >01
Behaviour of Turing Machine
Depending upon the number of moves in transition, a TM may be deterministic or 
non-deterministic. If TM has at most one move in a transition, then it is called 
Deterministic TM (DTM), if one or more than one move, then Non-deterministic TM 
(NTM or NDTM). •
• A non-deterministic TM is equivalent to a deterministic TM.
• Some single tape TM simulates every 2 PDA (a PDA with two stacks).
• The read only TM may be considered as a Finite Automata (FA) with additional 
property of being able to move its head in both directions (left and right).
Page 4


Turing Machine
The languages accepted by Turing machine are said to be recursively enumerable. 
A Turing Machine (TM) is a device with a finite amount of read only hard memory 
(states) and an unbounded amount of read/write tape memory.
• Recursive languages are closed under complementation, union, intersection, 
concatenation and Kleene closure.
• A Turing machine is said to be partially decide a problem, if the following two 
conditions are satisfied.
1. The problem is a decision problem.
2. The Turing machine accepts as given input if and only if the problem has 
an answer 'yes' for the input that is the Turing machine accepts the 
language L.
• A Turing machine is said to be decide a problem, if it partially decides the 
problem and all its computations are halting computations.
A language L is Turing-recognisable if there is a Turing machine M such that 
L=L(M).
A language L is Turing-decidable if there is a Turing machine M such that M 
decides L.
Turing-decidable language is also Turing-recognisable, but Turing-recognisable may 
not be Turing-decidable.
A language is recursively enumerable iff it is Turing-enumerable.
Universal Turing Machine (UTM)
• A UTM is a specified Turing machine that can simulate the behaviour of any 
TM.
• A UTM is capable of running any algorithm.
For simulating even a simple behaviour, a Universal Turing Machine must have a 
large number of states. If we modify our basic model by increasing the number of 
read/write heads, the number of dimensions of input tape and adding a special 
purpose memory, then we can design a Universal Turing Machine.
Definition of Turing Machine
A Turing Machine (TM) is defined as 7-tuples.
TM = (Q, Z, T, 5, q0, b, F),
where, Q is a finite non-empty set of states, Z is a non-empty set of input symbols 
(alphabets) which is a subset of r and b e Z, r is a finite non-empty set of tape 
symbols, 5 is the transition function which maps (Q x r) to (Q x r x {L, R}), q0 is the 
initial state and qo e Q, b is the blank and b e r, F is the set of final states and F c 
Q.
Transition Function of a Turing Machine
The transition function Q x r — ? Q x r x {L, R} states that if a Turing machine is in 
some state (from set Q), by taking a tape symbol (from set I"), it goes to some next 
state (from set 'i) by overwriting (replacing) the current symbol by another or same 
symbol and the read/write head moves one cell either left (L) or right (R) along the 
tape.
1. {fl"6nc" | n > 1}
Solution:
M = {{qa.qa-<lb,Qc,Qy,qz,(lf}- {«, b , c}, (a, 6, c, X , Y, Z }, 6, q 0. D. {qf })
2. {wwR | w is any string of 0’s and l ‘s}
Solution:
A! = ({qintU < ? o , <7i, <7o«, <7i«, ^bocfc, <7/}, { 0 , 1 } , {0, 1 } , 6, qinit, B, {qf})
S t a t e 0 1 D
Qinit ( < Q o, B- B) (<7i, £ .7 ? ) (qf, B , R)
Q a {qoA)-R) (<7o, 1, /?)
( q o R . B . L )
4 t
(< 71,0,/?)
(<7i, 1, B)
(qX R ,B ,L )
(qbacki B, L) - -
q VR - (qbacki B, L) -
q b a c .k Q b a c k i 0 , L ) (qbacki 1, B) ( q i n i t, B, /? )
3. Construct a TM that accepts the language A = {()(2 A n ) | n>=0}
A = { 02" | h >01
Behaviour of Turing Machine
Depending upon the number of moves in transition, a TM may be deterministic or 
non-deterministic. If TM has at most one move in a transition, then it is called 
Deterministic TM (DTM), if one or more than one move, then Non-deterministic TM 
(NTM or NDTM). •
• A non-deterministic TM is equivalent to a deterministic TM.
• Some single tape TM simulates every 2 PDA (a PDA with two stacks).
• The read only TM may be considered as a Finite Automata (FA) with additional 
property of being able to move its head in both directions (left and right).
Language Recognition by Turing Machine
TM can be used as a language recogniser. TM recognises all languages, regular 
language, CFL, CSL, Type-0.
There are several ways an input string might fail to be accepted by a Turing 
machine
• It can lead to some non-halting configuration from which the Turing machine 
cannot move.
• At some point in the processing of the string, the tape head in scanning the 
first cell and the next move specifies moving the head left off the end of the 
tape.
• In either of these cases, we say that the Turing machine crashes
Variation of TM with other Automata
• Multitape Turing Machine A Turing machine with several tapes is said to be a 
multitape Turning machine. In a multitape Turing machine, each tape is 
controlled by its own independent read/write head.
• Turing machine with multiple tape is no more powerful that one tape Turing 
machine.
• Multi-dimensional Turing Machine A Turing machine is said to be multi­
dimensional Turing machine, if its tape can be viewed as extending infinitely 
in more than one dimension.
• Multihead Turing Machine A multihead Turing machine can be viewed as a 
Turing machine with a single tape and a single finite state control but with 
multiple independent read/write heads.
• In one move, the read/write heads may take move independently left, right or 
remain stationary
• Offline Turing Machine An offline Turing machine is a multitape Turing 
machine whose input tape is read only (writing is not allowed). An offline 
Turing machine can simulate any Turing machine A by using one more tape 
than Turing machine A. The reason of using an extra tape is that the offline 
Turing machine makes a copy of its own input into the extra tape and it then 
simulate Turing machine A as if the extra tape were A's input.
Halting Problem of Turing Machine: A class of problems with two output 
(true/false) is called solvable (or decidable) problem, if there exists some definite 
algorithm which always halts (also called terminates), else the class of problem is 
called unsolvable (or undecidable.
Recursive and Recursively Enumerable Languages
A language L is said to be recursively enumerable, if there exists a Turing machine 
that accepts it.
A language is recursive if and only if there exists a membership algorithm for it. 
Therefore, a language L on Z is said to be recursive, if there exists a Turing 
machine that accepts the language L and 'it halts on every u )e l+.
Page 5


Turing Machine
The languages accepted by Turing machine are said to be recursively enumerable. 
A Turing Machine (TM) is a device with a finite amount of read only hard memory 
(states) and an unbounded amount of read/write tape memory.
• Recursive languages are closed under complementation, union, intersection, 
concatenation and Kleene closure.
• A Turing machine is said to be partially decide a problem, if the following two 
conditions are satisfied.
1. The problem is a decision problem.
2. The Turing machine accepts as given input if and only if the problem has 
an answer 'yes' for the input that is the Turing machine accepts the 
language L.
• A Turing machine is said to be decide a problem, if it partially decides the 
problem and all its computations are halting computations.
A language L is Turing-recognisable if there is a Turing machine M such that 
L=L(M).
A language L is Turing-decidable if there is a Turing machine M such that M 
decides L.
Turing-decidable language is also Turing-recognisable, but Turing-recognisable may 
not be Turing-decidable.
A language is recursively enumerable iff it is Turing-enumerable.
Universal Turing Machine (UTM)
• A UTM is a specified Turing machine that can simulate the behaviour of any 
TM.
• A UTM is capable of running any algorithm.
For simulating even a simple behaviour, a Universal Turing Machine must have a 
large number of states. If we modify our basic model by increasing the number of 
read/write heads, the number of dimensions of input tape and adding a special 
purpose memory, then we can design a Universal Turing Machine.
Definition of Turing Machine
A Turing Machine (TM) is defined as 7-tuples.
TM = (Q, Z, T, 5, q0, b, F),
where, Q is a finite non-empty set of states, Z is a non-empty set of input symbols 
(alphabets) which is a subset of r and b e Z, r is a finite non-empty set of tape 
symbols, 5 is the transition function which maps (Q x r) to (Q x r x {L, R}), q0 is the 
initial state and qo e Q, b is the blank and b e r, F is the set of final states and F c 
Q.
Transition Function of a Turing Machine
The transition function Q x r — ? Q x r x {L, R} states that if a Turing machine is in 
some state (from set Q), by taking a tape symbol (from set I"), it goes to some next 
state (from set 'i) by overwriting (replacing) the current symbol by another or same 
symbol and the read/write head moves one cell either left (L) or right (R) along the 
tape.
1. {fl"6nc" | n > 1}
Solution:
M = {{qa.qa-<lb,Qc,Qy,qz,(lf}- {«, b , c}, (a, 6, c, X , Y, Z }, 6, q 0. D. {qf })
2. {wwR | w is any string of 0’s and l ‘s}
Solution:
A! = ({qintU < ? o , <7i, <7o«, <7i«, ^bocfc, <7/}, { 0 , 1 } , {0, 1 } , 6, qinit, B, {qf})
S t a t e 0 1 D
Qinit ( < Q o, B- B) (<7i, £ .7 ? ) (qf, B , R)
Q a {qoA)-R) (<7o, 1, /?)
( q o R . B . L )
4 t
(< 71,0,/?)
(<7i, 1, B)
(qX R ,B ,L )
(qbacki B, L) - -
q VR - (qbacki B, L) -
q b a c .k Q b a c k i 0 , L ) (qbacki 1, B) ( q i n i t, B, /? )
3. Construct a TM that accepts the language A = {()(2 A n ) | n>=0}
A = { 02" | h >01
Behaviour of Turing Machine
Depending upon the number of moves in transition, a TM may be deterministic or 
non-deterministic. If TM has at most one move in a transition, then it is called 
Deterministic TM (DTM), if one or more than one move, then Non-deterministic TM 
(NTM or NDTM). •
• A non-deterministic TM is equivalent to a deterministic TM.
• Some single tape TM simulates every 2 PDA (a PDA with two stacks).
• The read only TM may be considered as a Finite Automata (FA) with additional 
property of being able to move its head in both directions (left and right).
Language Recognition by Turing Machine
TM can be used as a language recogniser. TM recognises all languages, regular 
language, CFL, CSL, Type-0.
There are several ways an input string might fail to be accepted by a Turing 
machine
• It can lead to some non-halting configuration from which the Turing machine 
cannot move.
• At some point in the processing of the string, the tape head in scanning the 
first cell and the next move specifies moving the head left off the end of the 
tape.
• In either of these cases, we say that the Turing machine crashes
Variation of TM with other Automata
• Multitape Turing Machine A Turing machine with several tapes is said to be a 
multitape Turning machine. In a multitape Turing machine, each tape is 
controlled by its own independent read/write head.
• Turing machine with multiple tape is no more powerful that one tape Turing 
machine.
• Multi-dimensional Turing Machine A Turing machine is said to be multi­
dimensional Turing machine, if its tape can be viewed as extending infinitely 
in more than one dimension.
• Multihead Turing Machine A multihead Turing machine can be viewed as a 
Turing machine with a single tape and a single finite state control but with 
multiple independent read/write heads.
• In one move, the read/write heads may take move independently left, right or 
remain stationary
• Offline Turing Machine An offline Turing machine is a multitape Turing 
machine whose input tape is read only (writing is not allowed). An offline 
Turing machine can simulate any Turing machine A by using one more tape 
than Turing machine A. The reason of using an extra tape is that the offline 
Turing machine makes a copy of its own input into the extra tape and it then 
simulate Turing machine A as if the extra tape were A's input.
Halting Problem of Turing Machine: A class of problems with two output 
(true/false) is called solvable (or decidable) problem, if there exists some definite 
algorithm which always halts (also called terminates), else the class of problem is 
called unsolvable (or undecidable.
Recursive and Recursively Enumerable Languages
A language L is said to be recursively enumerable, if there exists a Turing machine 
that accepts it.
A language is recursive if and only if there exists a membership algorithm for it. 
Therefore, a language L on Z is said to be recursive, if there exists a Turing 
machine that accepts the language L and 'it halts on every u )e l+.
Recursively enumerable languages are closed under union, intersection, 
concatenation and Kleene closure and these languages are not closed under 
complementation.
• The complement of a recursive language is recursive.
• The union of two recursive languages is recursive.
• The union of two recursiv enumerable languages is recursive enumerable.
• Intersection of two recursive languages isrecursive.
• There are some recursively enumerable languages which are not recursive.
• If L is recursive then, L is also recursive and consequently both languages are 
recursively enumerable.
• A language is recursive iff both it and its complement are recursively 
enumerable.
• A language L is lexicographically Turing-enumerable iff there is a Turing 
machine that lexicographically enumerates it.
• A language is recursive iff it is lexicographically Turing-enumerable.
• Every context sensitive language is recursive.
• The family of recursively enumerable languages is closed under union.
• If a language is not recursively enumerable, then its complements cannot be 
recursive.
• If a languages L is recursive, then it is recursively enumerable language but 
vice-versa is not true.
An infinite set is countable if and only if there is a one-to-one correspondence 
between its elements and the natural numbers. Otherwise it is said to be 
uncountable.
• If Z is a finite set then Z * is countable.
• For every alphabet Z there is a language Lcz* that is not recursively 
enumerable.
• There exists a language L that is recursively enumerable but not decidable.
• The halting problem is the problem of deciding whether a given Turing 
machine halts when presented with a given input. The halting problem is not 
decidable.