Computational Complexities of Turing Machine
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@iitj.ac.in
Formerly at department of Computer Science and Engineering
MBM Engineering College, Jodhpur

Tuesday 22nd July, 2025

kr chowdhary

TOC

1/ 14

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

Resources requirements for TM Computations
Complexity is Rate of growth of computation in time and space.
DTM: The time complexity is measured in terms of number of
transitions in a computation, and space complexity is maximum
number of tape squares used.
Multi-tape TM: Complexity differs polynomially from standard TM
Computations of a computer can be simulated on a TM, and it can
be shown that no. of transitions in TM = polynomial expression ×
no. of instructions executed in computer.
∴, resource bounds in TM provide practical information about
complexity of algorithms and computer programs.
Complexity:
Objective: 1) Assessment of Algorithms of problems, 2) Comparison
of difficulty of problems.
Problem Examples:
1. Array sort: Input: A1 . . . An , Output: A1′ . . . An′
2. Squaring a Matrix: Input: B : n × n, output: C = B 2
3. Path problem for directed graph: Input: G = (V , E ), Output:
Yes, if there is a path from vi to vj , else No.
kr chowdhary

TOC

2/ 14

Finding Complexity
4 Acceptance by a TM that halts for all inputs: Input: String w,
output: Yes, if M accepts w, No otherwise
Case 1,2: Computes function, case 3,4: are decision problems.
Resource usage is measured in: case 1 as no. of data movements, in
case 2 as number of scalar multiplications, in 3 as No. of nodes
visited, 4 as No. of transitions in a computation. There is no
definite relation in complexities in above.
Church-Turing thesis says that TM is an effective computing
machine, ∴ time and space complexities of TMs describe number of
transitions and & number of squares on tape for all the problems.
Rate of growth:
Let f (n) = n2 , and function g (n) = n3 .
∴ f ∈ O(g )
g∈
/ O(f ), ∴, n2 ∈ O(n3 ), since n2 ≤P n3 (n2 is polynomially
reducible to n3 )

kr chowdhary

TOC

3/ 14

Time Complexity of Standard TM
TC (Time complexity) is measured in terms of number of
transitions, for TM M for input |w | = n
Example: Analyze the computation for palindrome problem over
Σ = {a, b} for TM

Let tcm (n) is time complexity. Thus, tcm (0) = 1, tcm (1) = 3,
tcm (2) = 6, tcm (3) = 10,
+1
∴ tcm (n) = Σni =1
i = (n + 2)(n + 1)/2 = O(n2 )
kr chowdhary

TOC

4/ 14

Time Complexity of Two tape TM
Exercise: Time complexity for palindrome problem over Σ = {a, b}

Working: Loop1= Copy, Loop2 = Rewind tape2, Loop3 = Compare
tape1 and tape2.
Accepting computation: 3 passes, tcm (n) = 3(n + 1) = 1, is
polynomial.
∴ complexity of standard TM = polynomial × time complexity of
2-tape TM.

kr chowdhary

TOC

5/ 14

Complexity in TM variations

Theorem
Let L be language accepted by K-track DTM M with Time complexity
tcM (n), then L is also accepted by standard TM M ′ with T.C. tcM ′ , then
tcM (n) = tcM ′ (n).
Proof.
In k-track TM δ (qi , x1 , . . . , xk ), where xi is symbol in track i.
The same transition in std-TM (one tape) is δ (qi , [x1 , . . . , xk ]),
where k-tuple is single alphabet in std-TM M ′ . ∴, tcM = tcM ′ .

kr chowdhary

TOC

6/ 14

Simulation of multi-tape TM by Multi-track TM
K tape TM can be simulated by a 2k + 1 track TM

In Two tape:Two heads, Multi-track: one head. The Symbol X in
multi-track indicates virtual head position of two tape TM. To
simulate a transition of two-tape, the 5 track, the TM locates a
symbol at corresponding virtual head (X), reads the symbol under
that, and performs transition as that in two tape TM. Obviously, the
complexity of multi-track is more than that of k-tape TM.

kr chowdhary

TOC

7/ 14

Time Complexity in TM variations
Theorem
Let L be language accepted by K-tape DTM M with Time complexity
tcM (n) = f (n), then L is also accepted by standard TM N with time
complexity tcN (n), where tcN (n) ∈ O(f (n)2 ).
Proof.
We will first simulate K-tape TM on multi-track TM M ′ . The no. of
tracks will be 2k+1, as proved earlier.
∴, we should show only: tcM ′ ∈ (f (n)2 ). (Because complexities of
multi-track and standard TM are equal).
Let us try to simulate the farthest t th transition of M on M ′ .
1. There are k-even tracks for each head position symbol X . There
are 2 × t transitions. Total transitions = 2(t + 1), one extra for head
position, on 2t + 1th track. Contd . . .

kr chowdhary

TOC

8/ 14

Time Complexity in TM variations . . .

2. Similarly, for reading-writing of symbols on all odd tracks,
transitions are 2t.
3. For k tape TM M, total transitions =
k(2t + 2(t + 1)) + 1 = 4kt + 2k + 1. Thus
f (n )
tcM ′ (n) ≤ 1 + Σt =1 (4kt + 2k + 1) ∈ (f (n)2 ).
Since, time complexities of Std TM and multi-track are same, the
above time complexity is of std TM. 2

kr chowdhary

TOC

9/ 14

Time Complexity of Nondeterministic TM

A DTM generates and examins all possibilities
A NDTM employs a Guess-and-check strategy, and needs to
determine if one of the possibilities provide the solution
Example: To find out if k is composite number, we try to divide it
by all the possible factors of it. If one exists, then it is composite.
The set of all the composite numbers is language COMPOSITS.
A NDTM chooses a guess value, and a single division (verification)
determines that it is factor.
A string is accepted by NDTM if at least one of the computation
terminates in accepting state.

kr chowdhary

TOC

10/ 14

Two-tape NDTM to decide a palindrome language
Let Σ = {a, b}. The palindrome may be odd or even.

Operations:
1. Read and copy 1st half from tape1 to tape2,
2. nondeterministically decide the centre, at tape 1,
3. compare 2nd half on tape 1 with first half on tape 2.
No. of transitions for input |w | = n, is n+2 for odd n, N+3 for even
n. tcM (n) = O(n).
kr chowdhary

TOC

11/ 14

Simulation of NDTM by DTM

Theorem
Let L be language accepted by NDTM M with tcM (n) = f (n), for input
|w | = n. Then, L is accepted by DTM M ′ with T.C. tcM ′ = O(f (n)c f (n) ),
where c is maximum number of transitions for any State × Symbol pair
of M.
Proof.
Let M = (Q, Σ, Γ, δ , q0 , H), that halts for all the inputs.
Transformation from M to M ′ is done as follows:
A unique computation of M has sequence (m1 , . . . , mn ), 1 ≤ mi ≤ c;
mi is which of the c possible transformations are executed in ith
step. For |w | = n, maximum transitions of M is f(n). Contd next . . .

kr chowdhary

TOC

12/ 14

Simulation of NDTM by DTM . . .

For one computation of M, the M ′
1. generates sequence m1 , . . . , mn
2. Simulate M for this sequence
3. if solution not found, goto step a.
In worst case no. of transitions in M ′ is c f (n) , as so many sequences
are to be analyzed.
T.C. of M ′ is O(f (n)c f (n) ). 2

Note: This is similar to a bianry tree where the lowest level there are 2h
node, where h is is responsibility of .

kr chowdhary

TOC

13/ 14

Bibliography

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

kr chowdhary

TOC

14/ 14