Theory of Computation Alliance School of Advanced Computing

MODULE 5

TURING MACHINE

Prepared By Prof. EBIN PM 1

TURING MACHINE (TM)

Turing machine was invented in 1936 by Alan Turing.
It is an accepting device which accepts Recursive Enumerable
Language generated by type 0 (unrestricted)grammar.
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.

Prepared By Prof. EBIN PM 2

Prepared By Prof. EBIN PM 1

Theory of Computation Alliance School of Advanced Computing

Turing Machine

Tape alphabets : Σ = {0,1,a,b,x,z₀}

Blank symbol ( ˽ ) is a special symbol which is not in Σ

Prepared By Prof. EBIN PM 3

Operations on the Tape

• Read / Scan the symbol which is pointed by the tape head
• Update / Write a symbol which is pointed by the tape head
• Move the tape head one step left
• Move the tape head one step right

Prepared By Prof. EBIN PM 4

Prepared By Prof. EBIN PM 2

Theory of Computation Alliance School of Advanced Computing

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

Prepared By Prof. EBIN PM 5

Operation Rule – 1
At each step of computation
Read the current symbol
Write (update) the same cell
Move exactly one cell either LEFT or RIGHT
Symbol to Direction to
read move

a→b,R Transition Diagram

q₀ q₁

Symbol to
write

Prepared By Prof. EBIN PM 6

Prepared By Prof. EBIN PM 3

Theory of Computation Alliance School of Advanced Computing

Operation Rule – 2
Turing Machine has a control portion , which controls the Turing
Machine and is similar to FSM or PDA. It is deterministic also
TM has an initial state
TM has two final states
Accept state
Reject state
When the computation Halt (stop) ?
 HALT & Accept
HALT & Reject
Loop (Keep on computation and fail to stop)
Prepared By Prof. EBIN PM 7

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
T : the tape symbol
q₀ : the initial state
F : a set of final states (Accept & Reject state)
B : a blank symbol used as a end marker for input
δ : a transition or mapping function.

Prepared By Prof. EBIN PM 8

Prepared By Prof. EBIN PM 4

Theory of Computation Alliance School of Advanced Computing

Transition Function (δ )
Q × Σ → T × (R/L) × Q

Production rule of TM
δ (q₀, a) → (q₁ , y, R)

Any computations that can be done on existing digital computer,

can also be done by Turing Machine
If we are having an algorithm of a problem, then that can also be
solved by Turing Machine.

Prepared By Prof. EBIN PM 9

 Turing Thesis
It states that, any computation that can be carried out by mechanical
means can be performed by some Turing Machine.

The language that acceptable by the Turing Machine is called

Recursively Enumerable Language.

Prepared By Prof. EBIN PM 10

10

Prepared By Prof. EBIN PM 5

Theory of Computation Alliance School of Advanced Computing

Q: Design a Turing Machine which recognize the language L=01*0

Consider 0110

Tape x y y x ˽

Prepared By Prof. EBIN PM 11

11

Q: Design a Turing Machine which recognize the language L=0ⁿ1ⁿ

Algorithm
Change 0 to x
Move right to first “1” (If none: Reject)
Change 1 to y
Move left to leftmost “0”
Repeat the above steps until no more 0’s
Make sure no more 1’s remain

0 0 1 1 1 1 ˽ ˽
Tape 0 0
x x x x y y y y
Prepared By Prof. EBIN PM 12

12

Prepared By Prof. EBIN PM 6

Theory of Computation Alliance School of Advanced Computing

Transition Diagram

Tape

˽ ˽
0 0 0 0 1 1 1 1

Prepared By Prof. EBIN PM 13

13

Q: Design a Turing Machine which accepts even palindromes over

the alphabet Σ = {a, b}
Eg: abaaba
Tape
a b a a b a ˽ ˽ ˽ ˽

˽ ˽ ˽ ˽ ˽ ˽

Prepared By Prof. EBIN PM 14

14

Prepared By Prof. EBIN PM 7

Theory of Computation Alliance School of Advanced Computing

Transition Diagram

a b a a b a ˽ ˽ ˽ ˽

Prepared By Prof. EBIN PM 15

15

LINEAR BOUNDED AUTOMATA (LBA)

It behaves as a Turing machine but the storage space of tape is
restricted only to the length of the input string.
 It is less powerful than a Turing machine but more powerful than
push down automata.
The computation is restricted to the constant bounded area.
 The input alphabet contains two special symbols which serve as
left end markers and right end markers which mean the transitions
neither move to the left of the left end marker nor to the right of
the right end marker of the tape.

Prepared By Prof. EBIN PM 16

16

Prepared By Prof. EBIN PM 8

Theory of Computation Alliance School of Advanced Computing

A deterministic linear bounded automaton is always context-

sensitive and the linear bounded automaton with empty language
is undecidable.
Length of the input tape is bounded ie, finite. That’s why it is
called as Linear Bounded Automata.

Prepared By Prof. EBIN PM 17

17

A linear bounded automaton can be defined as an 8-tuple

(Q, T, ∑, q₀, ML, MR, δ, F) where
Q is a finite set of states
T is the tape alphabet
∑ is the input alphabet
q₀ is the initial state
ML is the left end marker
MR is the right end marker where MR ≠ ML
δ is a transition function which maps each pair (state, tape symbol)
to (state, tape symbol, Constant ‘c’) where c can be 0 or +1 or -1
F is the set of final states
Prepared By Prof. EBIN PM 18

18

Prepared By Prof. EBIN PM 9

Theory of Computation Alliance School of Advanced Computing

Linear Bounded Automata (LBA) – Applications

For implementation of genetic programming.
For constructing syntactic parse trees for semantic analysis of the
compiler.
Expressive Power of various Automata
The Expressive Power of any machine can be determined from the
class or set of Languages accepted by that particular type of
Machine. Here is the increasing sequence of expressive power of
machines :
FA < DPDA < PDA < LBA < TM

Prepared By Prof. EBIN PM 19

19

we can observe that FA is less powerful than any other machine.
It is important to note that DFA and NFA are of same power
because every NFA can be converted into DFA and every DFA can
be converted into NFA .
The Turing Machine (TM) is more powerful than any other
machine.
Linear Bounded Automata is accepted Context Sensitive Language
(Type 1).

Prepared By Prof. EBIN PM 20

20

Prepared By Prof. EBIN PM 10

Theory of Computation Alliance School of Advanced Computing

MULTI – TAPE TURING MACHINE

• Multi-tape Turing Machines have multiple tapes where each tape is
accessed with a separate head.
• Each head can move independently of the other heads. Initially the
input is on tape 1 and others are blank.
• At first, the first tape is occupied by the input and the other tapes
are kept blank.
• Next, the machine reads consecutive symbols under its heads and
the TM prints a symbol on each tape and moves its heads.

Prepared By [Link] PM, AP, IESCE 21

21

A Multi-tape Turing machine can be formally described as a 6-tuple

(Q, T, B, δ, q₀, F) where
Q is a finite set of states
T is the tape alphabet
B is the blank symbol
q₀ is the initial state
F is the set of final states
δ is a relation on states and symbols where
δ: Q × Tⁿ → Q × Tⁿ × {L , R}ⁿ where n is the number of tapes
Every Multi-tape Turing machine has an equivalent single-tape
Turing machine.
Prepared By [Link] PM, AP, IESCE 22

22

Prepared By Prof. EBIN PM 11

Theory of Computation Alliance School of Advanced Computing

Example
n=2
δ (q₀ , a , e) = (q₁ , x , y , L , R)

q₀ q₁

abc de f xbc dy f
Tape 1 Tape 2 Tape 1 Tape 2

Prepared By [Link] PM, AP, IESCE 23

23

NON-DETERMINISTIC TURING MACHINE

• Only the difference is in transition function
 δ of Deterministic TM
Q × Σ → T × (R/L) × Q
δ of Non-Deterministic TM
Q × Σ → P { T × (R/L) × Q} where P = power set

 In a particular state, up on reading a particular input symbol, the

Non Deterministic TM will go to more than one state.

Prepared By [Link] PM, AP, IESCE 24

24

Prepared By Prof. EBIN PM 12

Theory of Computation Alliance School of Advanced Computing

Deterministic & Non – Deterministic TM

Deterministic TM Non-Deterministic TM

Prepared By [Link] PM, AP, IESCE 25

25

Configuration of Deterministic and No-Deterministic TM

Configuration :
It is a way to represent the entire state of a TM at a moment
during computation
It is a string which shows
• The current state
• The current position of the head
• The entire tape contents

a b a b b a a ˽ ˽ ˽ abaQbbaa
Prepared By [Link] PM, AP, IESCE 26

26

Prepared By Prof. EBIN PM 13

Theory of Computation Alliance School of Advanced Computing

Deterministic TM and its computation history

using Configuration
Deterministic TM Configuration

ccQabbc

ccxSbbc

ccxyPbc
Prepared By [Link] PM, AP, IESCE 27

27

Non-Deterministic TM and its computation

history using Configuration
Non- Deterministic TM Configuration
ccQabbc

cScybbc ccxPbbc

Tczybbc ccxyRbc

cwUybbc

Prepared By [Link] PM, AP, IESCE 28

28

Prepared By Prof. EBIN PM 14

Theory of Computation Alliance School of Advanced Computing

With Non determinism, at each moment in the computation, there

can be more than one successor configuration.
Outcome of Non-Deterministic TM
Accept – If any branch of the computation accepts, then the Non-
Deterministic TM will accept
Reject – If all branches of the computation halt and reject (ie., no
branches accept, but all computations halt) then the Non-
Deterministic TM rejects.
Loop – Computation continues but accept is never encountered.
Some branches in the computation history are infinite.

Prepared By [Link] PM, AP, IESCE 29

29

RECURSIVE & RECURSIVE ENUMERABLE

LANGUAGES
The Turing Machine may
Halt & Accept the input
Halt and Reject the input
Never Halt (Loop)
Recursive Language (REC)
• REC languages are also called as Turing decidable languages
• A language “L” is said to be recursive, if there exist a Turing Machine
which will accept all the strings in “L” and reject all the strings not in “L”.
• The Turing Machine will halt every time and give the answer(accepted
or rejected) for each and every string input.

Prepared By [Link] PM, AP, IESCE 30

30

Prepared By Prof. EBIN PM 15

Theory of Computation Alliance School of Advanced Computing

Recursive Enumerable Language (RE)

• RE languages are also called as Turing recognizable languages.
• A language “L” is said to be Recursively Enumerable Language, if
there exist a Turing Machine which will accept(and therefore halt)
for all the input strings which are in “L”.
• But may or may not halt for all input strings which are not in “L”.
• Recursive language is a subset of Recursive Enumerable Language.

Prepared By [Link] PM, AP, IESCE 31

31

Properties of Recursive Language (REC)

• Union: If L₁ and If L₂ are two recursive languages, their union L₁∪L₂
will also be recursive because if TM halts for L₁ and halts for L₂, it
will also halt for L₁∪L₂.
• Concatenation: If L₁ and If L₂ are two recursive languages, their
concatenation L₁.L₂ will also be recursive.
• Kleene Closure: If L₁ is recursive, its kleene closure L₁* will also be
recursive.
• Intersection: If L₁ and If L₂ are two recursive languages, their
intersection L₁ ∩ L₂ will also be recursive.
• Complement: complement of recursive language L₁ which is ∑*-L₁,
will also be recursive
Prepared By [Link] PM, AP, IESCE 32

32

Prepared By Prof. EBIN PM 16

Theory of Computation Alliance School of Advanced Computing

Properties of Recursive Enumerable Language (RE)

• Union: If L₁ and If L₂ are two recursive enumerable languages, their
union L₁∪L₂ will also be recursive enumerable
• Concatenation: If L₁ and If L₂ are two recursive enumerable
languages, their concatenation L₁.L₂ will also be recursive
enumerable
• Kleene Closure: If L₁ is recursive enumerable, its kleene closure L₁*
will also be recursive enumerable
• Intersection: If L₁ and If L₂ are two recursive enumerable languages,
their intersection L₁ ∩ L₂ will also be recursive enumerable.
• Complement: RE languages are not closed under complement,
which means complement of RE language need not be RE.
Prepared By [Link] PM, AP, IESCE 33

33

DECIDABILITY & UNDECIDABILITY

Decidable Language
• A language L is decidable if it is a recursive language.
• All decidable languages are recursive languages and vice-versa

Partially Decidable Language

• A language L is partially decidable, if L is a recursively enumerable
Language

Prepared By [Link] PM, AP, IESCE 34

34

Prepared By Prof. EBIN PM 17

Theory of Computation Alliance School of Advanced Computing

Undecidable Language
• A language is undecidable if it is not decidable
• An undecidable language may sometimes be partially decidable
but not decidable.
• If a language is not even partially decidable, then there exists no
Turing Machine for that language

Prepared By [Link] PM, AP, IESCE 35

35

Recursive Language Turing Machine will always Halt

Recursively Enumerable Turing Machine will halt some times & may
Language not halt some times
Decidable Language Recursive Language

Partially Decidable Recursively Enumerable Language

Language
Undecidable No Turing Machine for that language

Prepared By [Link] PM, AP, IESCE 36

36

Prepared By Prof. EBIN PM 18