Universal Turing Machine
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@gmail.com
Formerly at department of Computer Science and Engineering
MBM Engineering College, Jodhpur

Thursday 13th November, 2025

kr chowdhary

TOC

1/ 7

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

TM Simulations & Universal TM

A 3-tape TM, 2D-TM, and
NDTM can be simulated by a
standatd TM. Also, A TM can
be also simulated by a TM.
Let Input = [M, w ] to a TM
M ′ . Output of M ′ is what,
when M runs with input w .
M ′ is Universal Turing
machine (UTM).
A UTM can be designed to

kr chowdhary

simulate the computations of
an arbitrary TM M. To do so,
input to UTM must contain
representation of both machine M and input w to be
processed by M.

TOC

2/ 7

TM Simulation on another TM

Let there is TM M that
accepts by halting. The UTM
M ′ for this is:
with Input string = R(M)w ,
where R(M) is representation
of M.
Output-1: Accept (indicates
that M halts with input w ),
output-2: loops, i.e., M does
not halt with input w , i.e.
computation of M does not

kr chowdhary

terminate.
The machine M ′ is called
universal TM, as computation
of any Turing machine can be
simulated by M ′ .

TOC

3/ 7

Design a string representation of a TM M
The states of M are assumed
to be {q0 , q1 , . . . , qn }. TM M
is defined by its transition
function:

Because of the ability to encode
arbitrary symbols as strings over
{0, 1}, we consider Turing machine
with inputs {0, 1} and tape
symbols Γ = {0, 1, B}
Encoding of elements of M:
Symbol Encoding
0
1
1
11
B
111
q0
1
q1
11
...
...
qn
1n+1
L
1
R
11

kr chowdhary

δ (qi , a) = (qj , b, d)
where,
qi , qj ∈ Q; a, b ∈ Γ; d ∈ {L, R}
Let en(z) denote the encoding
of z. Thus, transition
δ (qi , a) = (qj , b, d) is encoded
by string:
en(qi )0en(a)0en(qj )0en(b)0en(d).
The symbol 0 separates the
different components of δ .

TOC

4/ 7

Encoding of elements of M
Representation of machine M is constructed from encoded transitions.
Two consecutive 0s separate transitions. Beginning and end of complete
representation are defined by three 0s.
Consider the Transitions:
Transition
δ (q0 , B) = (q1 , B, R)
δ (q1 , 0) = (q0 , 0, L)
δ (q1 , 1) = (q2 , 1, R)
δ (q2 , 1) = (q0 , 1, L)

Encoding
101110110111011
1101010101
110110111011011
1110110101101

The machine M is represented by string: 000101110110111011
00110101010100110110111011011001110110101101000
Simulation of M on Universal TM M ′
Verification of representation of M: TM can be constructed to
check whether an arbitrary string u ∈ {0, 1}∗ is encoding of
deterministic TM M. Computations examines whether 000 is prefix,
followed by finite sequences of encoded transitions are separated by
00s, then finally 000.
M is deterministic if Q × Γ in every encoded transition is unique.
kr chowdhary

TOC

5/ 7

Simulation of TM M on 3-tape DTM M ′
is determined by symbol
scanned on tape-3 and state
encoded on tape-2. Let these
are a and qi .

Tape-1 holds R(M)w . Tape-3
simulates computations of of
M for input w . Tape-2 acts as
working tape.

1

2

3

If input u is not of the form
R(M)w for deterministic TM
M and string w on tape-1, the
M ′ moves to right forever.

4

Tape-1 is scanned for a and qi
as first two components of a
transition. If not found, M ′
halts by rejecting input.

w is copied from tape-1 to 3,
with tape head at begin of w .
∴ tape-3 is initial
configuration of M with input
w.

5

If tape-1 consists the encoded
information for above, i.e.,
δ (qi , a) = (aj , b, d), then

Encoding of q0 , i.e., 1 is
written tape-2. (for future
steps, we call it qj ).

(a) qi replaced by qj on tape-2.
(b) b is written on tape 3, and
tape head on tape-3 is moved
for direction given in d.
6

Transition of M is simulated
on tape-3. The next transition
kr chowdhary

TOC

Go back to step 2, and carry
on computation by simulating
M.
6/ 7

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

7/ 7