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

Monday 21st July, 2025

kr chowdhary

TOC

1/ 27

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

Ways to Extend Turing Machines
Many variations have been proposed:
Multiple tape Turing machine
Multiple track Turing machine
Two dimensional Turing machine
Multidimensional Turing machine
Two-way infinite tape
Non-determinic Turing machine
Combinations of the above
Theorem: The operations of a TM allowing some or all the above
extensions can be simulated by a standard TM.The extensions do
not give us machines more powerful than the TM.
The extensions are helpful in designing machines to solve particular
problems.

kr chowdhary

TOC

2/ 27

Multiple Tape TM
Variants of TM:
For example, in two tape Turing machine, each tape has its own
read-write head, but the state is common for all tapes and all heads.
In each step (transitions) TM reads symbols scanned by all heads,
depending on head position and current state, each head writes,
moves R or L, and control-unit enter into new state.
Actions of heads are independent of each other.
Tape position in two tapes: [x, y ], x in first tape, and y in second,
and δ is given by:
δ (qi , [x, y ]) = (qj , [z, w ], d, d), d ∈ {L, R}
δ
a, a
B, a
a, B
q0 q1 , a, b, L, R q2 , b, B, L, L q0 , b, B, L, R,
A standard TM is multi-tape TM with single tape.

B, B
...

Example: These multi-tape TMs are better suited for specific
applications, e.g., copying string from one tape to another tape.
However, their time-complexity remains P only.
kr chowdhary

TOC

3/ 27

Multiple Tape TM

Turing machine, for k ≥ 1
number of tapes:
δ : (Q − H) × Γk →
Q × Γk × {L, R}k
δ (qi , a1 , . . . , ak ) =
qj , (b1 , . . . , bk ), (d1 , . . . , dk )
The steps to carry out a
transition are:
1. change to next state;
2. write one symbols on each
tape;
A transition in a multi-tape

kr chowdhary

3. independently reposition each
tape heads.

TOC

4/ 27

Two-tape TM to recognize language L = {an b n | n ≥ 0}

Working: with The original string w is on tape 1
1

Copies the string a’s on tape 2.

2

Moves head 1 to begin of b’s, and head on last a’s

3

Compare number of b’s tape 1 with number of b’s on tape 2 by
moving heads in opposite directions.

4

Time Complexity: 1 + n + 1 + n + 1 = O(n + 3) = O(n) =
Polynomial (P) (Compare it with standard TM for same problem
with complexity O(n2 )

kr chowdhary

TOC

5/ 27

Two-tape TM to recognize language
L = {ww R | w ∈ {a, b}∗ }

1
2
3

4

5

Working: with The original string w is on tape 1
Copies the string w on tape 2.
Moves head 1 to extreme left (rewind)
Aligns both heads on opposite, i.e, head 1 to extreme left, head 2 to
extreme right
Compare by moving heads in opposite directions. Accept when
compare ok.
Let input is |ww R | = n. Time Complexity: 1 + n + 1 + n + 1 + n + 1
= O(3n + 4) = O(n). This is Polynomial Complexity, hence type of
complexity is P (i.e., type P)
kr chowdhary

TOC

6/ 27

Multi-Tape TM
Example: Construct 2-tape TM to recognize the language
L = {ww |w ∈ {a, b}∗ }.

steps:(Note: x ∈ {a, b}, y ∈ {a, b})
1. Initially the string ww is on tape-1. Copy it to tape-2, at the end
both R/W heads are at right most.
2. Move both heads left: Head-1, 2-steps and head-2, 1-step each time.
3. Move both heads right, each one step. Head-1 moves in first w of
ww and head-2 moves in second w , comparing these w in q4 .
In q3 → q2 transition, the move ’Y |Y , S’ keeps head2 stationary.
kr chowdhary

TOC

7/ 27

Multiple Tape TM
Simulation of a three-tape TM M by standard TM S:
Let the contents of a three tape TM M are:
01010B Tape 1: bold character is R/W head position
aaaB Tape 2: bold character is R/W head position
baB Tape 3: bold character is R/W head position
Tape contents on simulated standard TM S:
01010#aaa#baB , # is separator for contents of 3 tapes.
In practice, S leaves an extra blank before each symbol to record
position of read-write heads
S reads the symbols under the virtual heads (L to R).
Then S makes a second pass to update the tapes according to the
way the transition function of M dictates.
If, at any point S moves one of the virtual heads to the right of #,
it implies that head moved to unread blank portion of that tape. So
S writes a blank symbol in the right most of that tape. Then
continues to simulate.
⇒ control will need a lot more states.
kr chowdhary

TOC

8/ 27

Multiple track TM

The tape is divided into tracks. A tape position in n-track tape
contains n symbols from tape alphabets.
Tape position in two-track is represented by [x, y ], where x is symbol
in track 1 and y is in tack-2. The states, Σ, Γ, q0 , F of a two-track
machine are same as for standard machine.
A transition of a two-track machine reads and writes the entire
position on both the tracks.
δ is: δ (qi , [x, y ]) = [qj , [z, w ], d], where d ∈ {L, R}. The input for
two-track is put at track-1, and all positions on track-2 is initially
blank. The acceptance in multi-track is by final state.
Languages accepted by two-track machines are Recursively
Enumerable languages.
kr chowdhary

TOC

9/ 27

Multi-track Turing Machine = Standard TM
Theorem
A language is accepted by a two-track TM M if and only if it is accepted
by a standard TM M ′ .
Proof.
Part 1:If L is accepted by standard TM M ′ then it is accepted by
two-track TM M also (for this, simply ignore 2nd track). Hence
track content is tuple [a, B].
Part 2:
Let M = (Q, Σ, Γ, δ , q0 , H) be two track machine. Find one
equivalent standard TM M ′
Create ordered pair [x, y ] on single tape machine M ′ .
M ′ = (Q, Σ × {B}, Γ × Γ, δ ′ , q0 , F ) with
δ ′ as δ ′ (qi , [x, y ]) = δ (qi , [x, y ]).

kr chowdhary

TOC

10/ 27

Construct a 3-tape TM to recognize the set
{ak |k is a perfect square}

1

2

Tape 1 holds the input, tape 2
holds progressive k 2 (i.e., k,
kk, kkk, ...) and tape 3 the
progressive k
keep T2 = T3 = ε.
kr chowdhary

3

If Input is compared with T2 ,
by scanning both. If both
reach to B together, accept,
and terminate. Else, put a at
T2 and T3 .

4

If T2 ≡ T1 , accept and
terminate, else if |T2 | > |T1 |,
reject input, else (T2 < T1 ),
then:
append T2 with 2 × T3
and append a to T2 (this
changes content of T2 from
2
2
ak to ak +2k +1 .

5

append a to T3 (increment
t3 ).

6

go back to step 3.

TOC

11/ 27

Two-way infinite tape

There is single tape M which extends from −∞ to + ∞. One R-W
head, M = (Q, Σ, δ , q0 , F )
. . . -3 -2 -1 0 1 2 3 . . . , is square sequence on TM, with R-W head
at 0
This can be simulated by a two-tape TM:
M ′ = (Q ′ ∪ {qs , qt }) × {U, D}, Σ′ , Γ′ , f ′ ), where U = up tape head, D
= down tape head, Σ′ = Σ, Γ′ = Γ ∪ {B}, and
′

′

F = {[qi , U], [qi , D]|qi ∈ F }. Initial state of M is pair [qs , D]. A
transition from this writes B in U tape at left most position.
Transition from [qt , D] returns the tape head to its original position
to begin simulation of M.

kr chowdhary

TOC

12/ 27

Multi-Dimensional Tape:

Single R-W head, but multiple tapes exists. Let the Dimensions be
2D. For each input symbol and state, this writes a symbols at
current head position, moves to a new state, and R-W head moves
to left or right or up or down.
Simulate it on 2-tape TM:
copy each row of 2-D tape on 2nd tape of 2-tape TM. When 2D
TM moves head L or R, move the head on 2nd-tape of two-tape also
L or R. When 2D head moves up, 2nd tape of two-tape scans left
until it finds ∗. As it scans, it writes the symbols on tape-1. Then
scans and puts remaining symbols on tape-1. Now it simulates this
row (on tape-1).

kr chowdhary

TOC

13/ 27

Nondeterministic TM (NDTM)
NDTM has finite number of choices of moves; components are same
as standard TM; may have > 1 move with same input and state
pair, (Q − H × Σ). Nondeterminism is like FA and PDA.
A NDTM machine accepts by halting if there is at least one
computation sequence that halts normally when run with input w .
Example: Find, if a graph of n nodes has a connected subgraph of k
nodes. For this, no efficient algorithm exists. A Non-exhaustive
based solution is Guess and check.
1

2

NDTM: Arbitrarily choose a move when more than one possibility
exists for δ (qi , a).
Accept the input if there is at least one computation sequence that
leads to accepting state (however, the converse is irrelevant).

To find a NDTM for ww input, w ∈ Σ∗ , you need to guess the mid
point and compare two w ’s.
A NDTM may specify any number of transitions for a given
configuration, i.e. δ : (Q − H) × Γ → subset of Q × Γ × {L, R}

kr chowdhary

TOC

14/ 27

A NDTM to accept ab preceded or followed with c
Example: w = ucv , where c is preceded by or followed by ab, and
u, v ∈ {a, b, c}∗

Approach: Read input a, b, c and write a, b, c respectively, and move to R
in each, at start state. Then with input c, Nondeterministically decide
c, a, b by moving R in three states transitions or decide c, b, a by moving
L in three other states transitions (i.e., abc)

kr chowdhary

TOC

15/ 27

Simulation of a NDTM on Standard TM
To accomplish the transformation of a NDTM into a deterministic
TM, we show that multiple computations of a single input string can
be sequentially generated and examined.
A NDTM produces multiple computations for a single string. We
show that multiple computations m1 , . . . , mi , . . . , mk for a single
input string can be sequentially generated and applied.(A
computation mi is δ (qi , a) = [qj , b, d], where d ∈ {L, R}.
These computations can be systematically produced by adding the
alternative transitions for each Q × Σ pair. Each mi has 1 : n
number of transitions. If δ (qi , x) = φ , the TM halts.
Using the ability to sequentially produce the computations, a NDTM
M can be simulated by a 3-tape deterministic TM M ′ .
Every nondeterministic TM has an equivalent 3-tape Turing
machine, which, in turn, has an equivalent standard TM (1-tape
Turing machine).

kr chowdhary

TOC

16/ 27

Simulation of a NDTM M by 3-tape TM M ′
mi ∈ {c1 , . . . , cn }. For
exhaustive solution,
complexity is decided by tree
height k, hence complexity is
k n.

Simulation of NDTM by
3-tape DTM:
Approach: A NDTM may
have more than one transition
for same input (state × input
symbol) pair. We may call
these configurations as c1 ...cn .

To perform the simulation of
M on M ′ , all the computation
sequence, for each (state,
input) pair are systematically
generated.
The tree created can be
searched in DFS or BFS, until
accepting/halting state is
reached.

If a computation sequence
m1 , . . . , mi , . . . , mk , leads to
solution, then for a NDTM
these are the steps for
solution, where
kr chowdhary

However, DFS is not preferred
because, it may go infinity.
Therefore, the generated
states are searched in BFS.
TOC

17/ 27

Simulation of a NDTM M by 3-tape TM m′

Tape-1 of M ′ stores the input string, tape-2 simulates the tape of
M, and tape-3 holds sequence m1 , . . . , mi , . . . , mk to guide the
simulation.
′

Computation of M consists following:
1

2
3

4

5

A sequence of inputs m1 , . . . , mi , . . . , mk , where each i, (i = 1 : n) is
written on tape-3. (mi ∈ {c1 , . . . , cn })
Input string is copied on tape-2.
Computation of M defined by sequence on tape-3 is simulated on
tape-2.
If simulation halts prier to executing k transitions, computations of
M ′ halts and accepts input, else
the Next sequence is generated on tape-3 and computation continues
on tape-2.

kr chowdhary

TOC

18/ 27

Example: Simulation of a NDTM M by 3-tape TM m′

Let us consider the NDTM M given
below to be simulated on 3-tape
DTM M ′ . Let us assume that
input string to NDTM is w = acab.

Since, there are maximum three
transitions at any (state, input)
pair, we take set {c1 , c2 , c3 } as
{1, 2, 3}. In case there is single
transition only, we repeat that to
make that count equal to 3. The
following table shows all pairs of
(q × σ ), where σ ∈ Sigma.
δ (q0 , B)

δ (q1 , a)

δ (q3 , b)

...

kr chowdhary

TOC

(1 q1 , B, R)
(2 q1 , B, R)
(3 q1 , B, R)
(1 q1 , a, R)
(2 q1 , a, R)
(3 q1 , a, R)
(1 q4 , b, R)
(2 q4 , b, R)
(3 q4 , b, R)
...

δ (q2 , a)

δ (q1 , c)

δ (q5 , b)

...

(1 q3 , a, R)
(2 q3 , a, R)
(3 q3 , a, R)
(1 q1 , c, R)
(2 q2 , c, R)
(3 q5 , c, R)
(1 q6 , b, R)
(2 q6 , b, R)
(3 q6 , b, R)
...

19/ 27

Simulation of a NDTM M by 3-tape TM m′
To simulate the NDTM on a 3-tape TM, following m1 , . . . , mi , . . . , mk
sequences are possible. All possible sequences are enumerated. The
sequence numbers are given as per the table, given in the previous slide.
Each sequence indicates a transition from one ID to next ID of the 3-tape
DTM.
q0 BacabB 1
⊢ Bq1 acabB 1
⊢ Baq1 cabB 1
⊢ Bacq1 abB 1
⊢ Bacaq1 bB 1
⊢ Bacabq1 B
sequence=
(1,1,1,1,1)

q0 BacabB 1
⊢ Bq1 acabB 1
⊢ Baq1 cabB 2
⊢ Bacq2 abB 1
⊢ Bacaq3 bB 1
⊢ Bacabq4 B
sequence=
(1,1,2,1,1)

q0 BacabB 2
⊢ Bq1 acabB 2
⊢ Baq1 cabB 3
⊢ Bq5 acabB

sequence
(2,2,3)

Therefore, what is required to generate the sequences as above:
(1,1,1,1,1), then (1,1,2,1,1), then (2,2,3), in lexicographic order. We
note, that the sequence (1,1,2,1,1) is accepting sequence; the moment
such generated sequence of configurations is simulated on tape-2, the
machine is halted.
kr chowdhary

TOC

20/ 27

Simulation of a NDTM: Generation of lexicographic
sequences
Sequence generator is a TM, with
no input, but output - sequence,
whose generation is interleaved
with the computation of the
simulation of NDTM on tape-2 of
M ′ . The figure below shows the
sequence generation.

kr chowdhary

The simulation of NDTM M on a
3-tape DTM M ′ is as follows: (1)
Input string w is put on tape 1, (2)
w is copied on tape 2, (3) next
sequence (m1 ..mk ) is generated on
tape 3, (4) tape 2 is simulated for
the moves (sequence) available on
tape 3. (5) If any move leads to
halting state, the machine is halted
and w is accepted. (6) process is
repeated from step 2. Note that
sequence generation is
non-terminating. Hence, if w ∈
/ L,
the process will continue
indefinitely.

TOC

21/ 27

Turing Machine as language enumerator
TM can also be designed to enumerate a language. Such machines
produce the exhaustive list of of string of the language, progressively
longer and longer.
Enumeration has no input, and its computation continues
indefinitely if the language is infinite, as well as when it is finite.
For enumeration, a TM of tape k ≥ 2 is used, tape 1 is output tape,
which would hold all the generated strings, separated by #, and
other tapes are working tapes.
Output tape 1 has: B#u1 #u2 # . . . #ui # . . . , where ui ∈ L.
Tape head 1 always moves R, S, while others may move R, L, S.
Example
Enumerate all the strings for L = {an b n c n | n ≥ 0}
Solution. The L can be generated by two-tape TM E with following
steps: (1) Write ## on tape 1 and 2 for ε. (2) add a on tape 2, (3)
copy a equal to size of tape 2 on tape 1, then by same size the b is
written on tape 1, then by same size c is written tape 1, followed with #
(4) goto step 2.
kr chowdhary

TOC

22/ 27

Turing Machine as language enumerator
The language L = {an b n c n | n ≥ 0} is suppose recognized by TM M. Let
the enumerator E generates all the strings of L.

kr chowdhary

TOC

23/ 27

Turing Machine as language enumerator
Theorem
If L is enumerated by a TM then L is recursively enumerable.
Proof.
Let L is enumerated by a TM E of k tapes. We add a tape new tape
k + 1 to it. Let this new machine is M. Consider a string w ∈ L, and we
write it on k + 1th tape. Every time # is written on tape 1 by E , and its
starts generating new string ui , simultaneously it is compared with w on
tape k + 1, if found equal, M halts, otherwise the process of generating
and compare is repeated for next string.
Since, when w ∈ L machine M halts else continues indefinitely, L is
recursively enumerable.
For enumeration it is necessary that lexicographic order (lo) of strings is
generated. We can generate all the strings on alphabet Σ = {a1 , . . . , an }
in lexicographic order using recursion as follows:
lo(ε) = 0, lo(ai ) = i, i = 1, n
lo(ai u) = i.nlenth(n) + lo(u)
kr chowdhary

TOC

24/ 27

Turing Machine as language enumerator
Theorem
For any alphabet Σ, there is TM EΣ∗ that enumerates Σ∗ in lexicographic
order.
Proof.
Let M be the TM that accepts L. The lexicographic ordering produces
listing: ε, u1 , u2 , . . . , ∈ Σ∗ . We Construct a table with columns as
strings in Σ∗ and rows as natural numbers, in the order as shown.

kr chowdhary

TOC

25/ 27

Turing Machine as language enumerator . . .
The [i, j] entry in the table means “run the M for input ui for j steps.
The machine E is built to enumerate L such that enumeration of the
ordered pairs are interleaved with the computation of M. The
computation of E is a loop:
1

generate an ordered pair [i, j]

2

run a simulation of M with input ui for j transitions or until the
simulation halts.

3

If M accepts, write ui on the output tape

4

continue with step 1.

If ui ∈ L, the computation of M with input ui halts and accepts after k
transitions, for some number k.
Thus, ui will be written on output tape of E when ordered pair [i, j] is
processed. The 2nd element of k ensures that simulation is terminated
after k steps. Consequently, no non-nonterminating computation are
allowed, and each string of Σ∗ is examined.
This is one more proof of the theorem : ”If a language is enumerated by
TM then it is RE“.
kr chowdhary

TOC

26/ 27

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

27/ 27

