Turing Machine
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@iitj.ac.in
Formerly, Prof. & HOD, Dept. of CSE MBM Engg. College

Sunday 20th July, 2025

kr chowdhary

TOC

1/ 20

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Alan M. Turing
Alan Turing was one of the founding fathers of CS.
His computer model - the Turing Machine (TM) - was
inspiration /premonition of the electronic computer which
came two decades after the TM model
Invented the Turing Test for in AI
Legacy: The Turing Award, eminent award in CS research
Definition
(Church-Turing Thesis:) TM is ultimate model for compuation.
Any thing, which is solvable, i.e., has an algorithm, what ever the
computation model is used to compute that algorithm, it is
ultimately the TM model.

kr chowdhary

TOC

2/ 20

Turing Machine Model for computation

M = (Q, Σ, Γ, δ , s, H),
where, Q is set of states
H is set of Halting states, H ⊆ Q
Σ is set of input symbols
Γ is tape alphabet, Γ = Σ ∪ {B, ▷}
δ is transition function (a partial function),
δ : (Q − H) × Γ → Q × Γ × {L, R}
Definition
Language acceptability by TM:
L = {w |w ∈ Σ∗ , q0 w ⊢∗ αpβ , p ∈ H; α, β ∈ Γ∗ }
kr chowdhary

TOC

3/ 20

Turing Machine
TM has a infinite amount
of read / write memory.
Input is assumed to reside
on the tape.

problem solving process
using pencil and paper. As
we do this, our mental
state changes, for every
smallest step.
Correspondingly, TM has
tape (=paper), R/W head
(=pencil), and state
(=state of our mind).

1936(Alan M. Turing): Any
logical/arithmetic
computation, for which
complete instructions for
carrying out this are
supplied, it is always
possible to design a TM
that can perform this
computation.

{an b n |n ≥ 0} v/s
{an b n c n |n ≥ 0}
Powers of TM: Power is
problem solving capability,
and not about how fast or
slow it can do.

TM v/s Human: TM
model is based on human
kr chowdhary

TOC

4/ 20

Turing Machine
These are Automata, as simple as possible - to define formally,
describe and reason about them, as general as possible (any
computation can be represented by them).
Definition
(Acceptability by Turing machine:) A string w is accepted by TM
M if after being put on the tape with the TM head set to the
left-most position, and letting M run, M eventually enters the
halting state. In this case w is an element of L(M), the language
accepted by M is,
L(M) = {w | w ∈ Σ∗ ∧ q0 w ⊢∗ αy β },
where, y is halting configuration, and α, β ∈ Γ∗

kr chowdhary

TOC

5/ 20

Turing Machine solves a Problem: Erase entire tape

⊢ Bq0 aaaB

Consider a TM
M = (Q, Σ, Γ, δ , s, H), Q =
{q0 , q1 },
Σ = {a}, Γ = {a, B, ▷}, s =
q0 , B is blank character, ▷
is left end marker.
H = {q1 }
δ (q0 , a) = (q0 , B, R)
δ (q0 , B) = (q1 , B, L)
Let w = aaaa
q0 aaaaB

kr chowdhary

⊢ BBq0 aaB
⊢ BBBq0 aB
⊢ BBBBq0 B
⊢ BBBq1 B

TOC

6/ 20

Configuration-1

A configuration of a TM: X1 X2 . . . Xi−1 qXi Xi+1 . . . Xn
- Current state: (q)
- Symbols on tape: X1 ...Xn
- position of RW head: Xi
A formal specification of configuration:
- uqv, where u,v are strings on Σ, and uv is current content on
tape, q is current state, and head is at first symbol of v.
For example, 00101q5 011 where read head points at 0 (third
digit from end) and state is q5 .

kr chowdhary

TOC

7/ 20

Configuration-2
For Two configurations:
uaqi bv and uqj acv , where , a, b, c ∈ Σ and u, v ∈ Σ∗
uaqi bv ⊢ uqj acv if δ (qi , b) = (qj , c, L)
uaqi bv ⊢ uacqj v if δ (qi , b) = (qj , c, R)
Two special cases:
- The left most cell:
qi bv ⊢ qj cv for δ (qi , b) = (qj , c, L)
qi bv ⊢ cqj v for δ (qi , b) = (qj , c, R)
- On the cell with blank symbol:
uaqi is equivalent to uaqi B

kr chowdhary

TOC

8/ 20

Example: of language recognition
Design TM to accept: {an b n | n ≥ 0}
Let M = (Q, Σ, Γ, δ , s, H). The algorithm can be specified as:
1. M replaces left most ’a’ by ’X’, and then head moves to right
until it encounters left most b
2. Replaces this b by Y, and then moves left to find the right
most X. Then moves one step right to left most a
3. Repeat Step 2 and 3 in order, i.e., 2, 3, 2, 3, . . .
4. When searching for b, if finds a blank character B (i.e.,
|an | > |b n |), then M does not accept w .
5. If a is not found but it finds b, then also M does not accept,
(i.e., |an | < |b n |).
6. After changing last b to Y, if M finds no more a then it
checks that no more b remains. If this is true then an b n is
accepted by M i.e., |an | = |b n |
kr chowdhary

TOC

9/ 20

Example: of language recognition
Q = {q0 , q1 , q2 , q3 , q4 }
Σ = {a, b}
Γ = {▷, a, b, X , Y , B}
s = q0
H = {q4 , q0 }
Design TM to accept: {an b n | n ≥ 0}
1. δ (q0 , a) = (q1 , X , R)
δ (q1 , a) = (q1 , a, R); skip through a′ s and
δ (q1 , Y ) = (q1 , Y , R); then Y ′ s
δ (q1 , b) = (q2 , Y , L)
δ (q2 , Y ) = (q2 , Y , L), traverse through Y’s and then
δ (q2 , a) = (q2 , a, L), traverse a’s

kr chowdhary

TOC

10/ 20

Example: of language recognition...
TM to accept: {an b n | n ≥ 0}

Figure 1: Transition diagram for TM accepting Language
L = {an b n | n ≥ 0}.

Move from R to L until X is found and start back:
δ (q2 , X ) = (q0 , X , R), right most X is found. Now repeat from
1 else from 2.
2. δ (q0 , Y ) = (q3 , Y , R), scan through Y’s
δ (q3 , B) = (q4 , B, L), accept w, and halt.
kr chowdhary

TOC

11/ 20

Transition Table for {an b n | n ≥ 0}

Current
State
q0
q1
q2
q3
q4

Tape
Symbol a
(q1 , X , R)
(q1 , a, R)
(q2 , a, L)
-

Tape
Symbol b
(q2 , Y , L)
-

Tape
Symbol B
(q4 , B, L)
(q4 , B, L)
-

kr chowdhary

TOC

Tape
Symbol X
(q0 , X , R)
-

Tape
Symbol Y
(q3 , Y , R)
(q1 , Y , R)
(q2 , Y , L)
(q3 , Y , R)
-

12/ 20

Example: of language recognition Dry Run
TM to accept: {an b n | n ≥ 0}, Let w = aabb
q0 aabbB ⊢ Xq1 abbB ⊢ Xaq1 bbB ⊢ Xq2 aYbB ⊢ Xq2 aBbB
⊢ q2 XaYbB ⊢ Xq0 aYbB ⊢ XXq1 YbB ⊢ XXYq1 bB
⊢ XXq2 YYB ⊢ Xq2 XYYB ⊢ XXq0 YYB ⊢ XXYq3 YB
⊢ XXYYq3 B ⊢ XXYq4 YB (accept the input)
Total number of transitions for |w | = n are: n/2 forward and
n/2 in backward, in each to and fro round, i.e., n. Since, in
each trip, two symbols are marked, therefore, there will be
total n/2 trips, making total transitions: n × n/2 = n2 /2.
Time complexity, O(n2 /2) = O(n2 ), which is polynomial (P)
time complexity.

kr chowdhary

TOC

13/ 20

Two-tape Turing Machine
Example: Construct TM to recognize L = {ww R | w ∈ {a, b}∗ }.
Approach: We can traverse w ; each time if a/b is found in begin,
replace it by B and also, replace a/b at end by B.

Figure 2: TM to recognize ww R strings.

Time complexity: Let |w | = n. Total of trips = n/2. Number of
transitions in successive trips are: n + (n − 2) + (n − 4) + · · · + 4 + 2
= n2 /2 − n/2 in even palindromes, and n2 /2 − n/2 + 2 in odd
palindromes, which is O(n2 ) is polynomial time complexity.
kr chowdhary

TOC

14/ 20

Acceptors v/s Deciders

Let M is TM.
Three possibilities occur on a given input w :
M eventually enters qacc and therefore halts and accepts.
w ∈ L(M)
M eventually enters qrej or crashes somewhere. M rejects w,
i.e., w ∈
/ L(M)
M never halts its computation and is caught up in an infinite
loop. In this case w is neither accepted nor rejected. However,
any string not explicitly accepted is considered to be outside
the accepted language. w ∈
/ L(M)
Decider: M never enters infinite loop(A recursive language).

kr chowdhary

TOC

15/ 20

Fermats last theorem /Church’s Thesis
Consider Fermat’s equation(last theorem): x n + y n = z n ,
where n is a positive integer
Question: Given an n, does this equation have a solution in
integers?
We could create a Turing machine T which would search for
solutions when given an input n by working through a list of
integers.
Then T (n) would halt when n=1 (having found a solution,
such as x=1, y=1 and z=2, and when n=2 (having found a
solution such as x=3, y=4 and z=5
But T would not halt for any other input
Church’s Thesis: Any reasonable attempt to model
mathematically computer algorithms and their performance, is
bound to end up with a model of computation and associated
time cost, that is equivalent to Turing machines within a
polynomial.
kr chowdhary

TOC

16/ 20

Undecidability
Theorem
Algorithms are countably infinite.
Proof.
An algorithm consists of sequence of alphabet strings, and
every alphabet can be encoded into an integer.
Let there be 1000 alphabets,and encoded as, e.g.,
a = 501, b = 502, c = . . . , ! = 700, . . . .
Let an algorithm text be baaa!
∴ it can be encoded as 502501501501700. Similarly every
algorithm can be encoded as integer (of course an integer
number may be very-very large). If two encoding are identical,
then the corresponding algorithms are identical.
All these integers form the set: N.
This concludes that algorithms are countable and infinite.
kr chowdhary

TOC

17/ 20

Undecidability
Theorem: Show that there are
infinitely many problems which
are not solvable.
Primality Proof: • Let a black
box with i/p and i/p, producing
a mapping such that for i/p
sequence 1, 2, 3, 4, 5,6, 7, 8, 9,
10, 11, 12, 13, . . . , output is 0,
1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
. . . . (If i/pt is prime o/p is 1,
else 0). Concatenate outputs
and insert “0” before each,
producing 0.0110101000101 . . . .
Let this problem be p1 . so,
problem p1 maps to
0.0110101000101 . . . , with each
kr chowdhary

prime number as an instance of
the problem.
• Every problem can thus have
a mapping to a binary fraction.
• The Set of all these fractions,
representing the bijection with
problems, is set of are real
numbers: [0, 1], is uncountably
infinite.
• With countably infinite
algorithms (N), and
uncountably infinite problems
(R), we conclude: there exists
infinitely many problems with
no algorithms.
TOC

18/ 20

Language acceptability by TM
• A language accepted by TM is • Church’s Lambda-calculus
paradigm was proved equivalent
recursive (R) if corresponding
to TM.
TM always halts, i.e. on
accepting it as well as rejecting.
• A Turing machine (TM) is
• A language accepted by TM is similar to a finite automaton
with an unlimited and
recursively enumerated(RE) if
unrestricted memory, and
the corresponding TM halts
having writing capability.
only on accepting it. R ⊂ RE .
• A Turing machine can do
everything that a real computer
• It was hard for the ancients to can do.
believe that any algorithm could
be carried out on such a simple • But, a Turing machine cannot
device. For us, it’s much easier solve certain classes of
to believe, especially if you have problems.
programmed in assembly!
A Thinking Machine:

kr chowdhary

TOC

19/ 20

Bibliography

Chowdhary, K.R. (2025). Turing Machine and Computability.
In: Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_9

kr chowdhary

TOC

20/ 20