COMP3630 / COMP6363
week 5: Introduction to Turing Machines
This Lecture Covers Chapter 8 of HMU: Introduction to Turing Machines
slides created by: Dirk Pattinson, based on material by
Peter Hoefner and Rob van Glabbeck; with improvements by Pascal Bercher
convenor & lecturer: Pascal Bercher
The Australian National University
Semester 1, 2025
Content of this Chapter
Turing Machine
Extensions of Turing Machines
Restrictions of Turing Machines
Extensions of PDAs – and Relationship to TMs
Additional Reading: Chapter 8 of HMU.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 2 / 34
Introduction to TMs
Introduction to TMs
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 3 / 34
Introduction to TMs
Turing Machine: Informal Definition
Finite Control
B B B B BBa bc a b b · · ·· · ·
∠ A tape extending infinitely in both sides
∠ A reading head that can edit tape, move right or left
∠ A finite control
∠ A string is accepted if finite control ever reaches a final/accepting state
Heads-up: There are many variations of TMs (e.g., in COMP1600, the head could also
stay stationary), and we will go through a few of them.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 4 / 34
Introduction to TMs
Turing Machine: Formal Definition
A Turing machine M = (Q,Σ,Γ, δ, q0,B,F ) is comprised of:
∠ Q: finite set of states
∠ Σ: finite set of input symbols
∠ Γ: finite set of tape symbols such that Σ ⊆ Γ
∠ δ: (deterministic) transition function. δ is a partial function over Q × Γ, where
the first component is viewed as the present state, and the second is viewed as
the tape symbol read. If δ(q,X ) is defined, then
Present state
Next StateTape symbol Reading head direction to move next
‹(q;X) = (q0; Y; D) The symbol replacing X
∠ B ∈ Γ \ Σ is the blank symbol. All but a finite number of tape symbols are Bs.
∠ q0: the initial state of the TM.
∠ F : the set of final/accepting states of the TM.
∠ Head always moves to the left or right. Being stationary is not an option. It can also
be defined with such an option, see tutorial.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 5 / 34
Introduction to TMs
Describing TMs
∠ Turing machines can be defined by describing δ using a transition table.
∠ They can also be defined using transition diagrams (with labels appropriately altered)
q q0If ‹(q;X) = (q0; Y; D)
X=Y D
A TM that accepts any binary string that does not contain 111
q0
1=
1
!
1=1!
1=1!
0=0!
0=
0
!
q1
q2q3
qf
B=B
!
B=B !
B
=B
!
0=0!
This encodes a DFA (almost).
Can you see why?
Because we never manipulate
the tape and terminate once
the String is read. The only
difference is that not all edges
are defined, but this can be
fixed with a trap state.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 6 / 34
Introduction to TMs
Instantaneous Descriptions of TMs
∠ An instantaneous description (or configuration) of a TM is a complete description of
the system that enables one to determine the trajectory of the TM as it operates.
∠ The instantaneous description or configuration or ID of a TM contains 3 parts:
(a) The (finite, non-trivial) portion of tape to the left of the reading head;
(b) the state that the TM is presently in; and
(c) the (finite, non-trivial) portion of the tape to the right of the reading head.
q B B X1 X2 X3 X‘· · · · · · · · ·· · · Xi
1  i  ‘
head
q B B X1 X2 X3 · · · · · ·· · · X‘
B B
B B
z }| {i Blanks
segment to the strict leftz }| {
X1 · · ·Xi1
statez}|{
q
segment from the head onwardsz }| {
Xi · · ·X‘
segment to the strict leftz }| {
X1 · · ·X‘Bi1
statez}|{
q
head
· · ·
q B BX1 X2 X3 · · ·· · · X‘B B
z }| {
head
· · ·
i Blanks
· · · statez}|{
q
segment from the head onwardsz }| {
BiX1 · · ·X‘
IDState, Tape contents, Reading head location
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 7 / 34
Introduction to TMs
‘Moves’ of a TM
∠ Just as in the case of a PDA, we use ⊢
M
to indicate a single move of a TM M,
and
∗
⊢
M
to indicate zero or a finite number of moves of a TM.
Next IDPresent ID
X1 · · ·Xi1qXi · · ·X‘
X1 · · ·X‘Bi1q
qBiX1 : : : X‘
Transition
‹(q;Xi ) = (q
0; Y; R)
‹(q;Xi ) = (q
0; Y; L)
X1 · · ·Xi1Y q0Xi+1 · · ·X‘
X1 · · ·Xi2q0Xi1Y Xi+1 · · ·X‘
‹(q;B) = (q0; Y; R)
‹(q;B) = (q0; Y; R)
‹(q;B) = (q0; Y; L)
‹(q;B) = (q0; Y; L)
X1 · · ·X‘Bi1Y q0
(1 < i < ‘)
X1 · · ·X‘1q0X‘Y i = 1
X1 · · ·X‘Bi2q0BY i > 1{
Y q0X2 · · ·X‘ i = 0
Y q0Bi1X1 · · ·X‘ i > 0{
q0BY Bi1X1 · · ·X‘ i > 0
q0BY X2 · · ·X‘ i = 0{
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 8 / 34
Introduction to TMs
Language accepted by a TM
∠ A string w is in the language accepted by a TM M iff q0w
∗
⊢
M
αpβ for some p ∈ F .
For accepted words, note that the TM may not necessarily halt (i.e., allow for no
further transitions) in such a final state; it may even move to a non-final state
afterwards. If a final state is ever visited, w is accepted in the language of M.
It is always possible to redesign a TM to halt for all accepted words without
changing its language; just remove all transitions out of final states.
∠ Otherwise, w is rejected by M.
Careful: Rejection might be defined differently in different textbooks/courses.
(In fact, our textbook doesn’t even define it! It just “uses” it.)
We will learn that we can’t always notice whether a word is rejected, because the
TM might be stuck in a loop (and we don’t know that). In general, we cannot
redesign TMs to halt on all rejected words.
∠ A language L is recursively enumerable if it is accepted by some TM.
∠ A language L is recursive if it is accepted by a TM that always halts on all inputs.
Re
cu
rsi
veRegular
Co
nte
xt-
fre
e
Re
cu
rsi
ve
ly
En
um
er
ab
le
(R
E) (Context-sensitive languages sit between
the CFLs and recursive languages.)
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 9 / 34
Introduction to TMs
On Acceptance, Rejection, Halting, and Decidability
Usually, there is no need to define outgoing transitions for final states, since as soon as
we enter a final state, the input word is accepted (so why proceed?)
∠ Thus, when you pick/design a TM to accept a given language L, you can consider
“reasonable” TMs that always halt on accepted words.
∠ However, if you have to judge properties of a given TM (e.g., whether it always halts,
or accepts a particular word etc.), then you have to deal with any TM – reasonable or
not... (Motivation: You might want to judge properties of somebody’s “program”)
Let L be given and M a TM, such that L(M) = L.
∠ If M halts on all inputs in Σ∗, we call it a total TM, say that it decides L, and call L
a decidable (or recursive) language.
∠ If M halts on all inputs taken from L (but does not necessarily halt for all inputs in
Σ∗ \ L), then L is semi-decidable (or recursively enumerable).
∠ In both cases, M ‘accepts’ L. (That’s literally what L(M) = L means!)
∠ Note: Just because L ∈ RE does not mean L /∈ R since R ⊆ RE . Also, R ⊊ RE .
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 10 / 34
Introduction to TMs
On Acceptance, Rejection, Halting, and Decidability
∠ “Accepting w”, i.e. w ∈ L(M), does not imply halting, since the machine may keep
going after reaching a final state. If we design a TM, there’s no point in defining
transitions out of any final state (so, it would halt).
∠ “Rejecting w”, i.e. w /∈ L(M), also does not imply halting. Either w was rejected
because the TM halted after a finite number of steps having never reached a final
state, or the TM loops through non-final states forever (and never reached a final
state before).
∠ “Not accepting w” is the same as “rejecting w .”
∠ “Not rejecting w” is the same as “accepting w .”
∠ “Halting on w” neither implies w ∈ L(M) nor w /∈ L(M), i.e., it is not enough
information to determine whether w was accepted or rejected. This is because we do
not know whether we have previously traversed a final state.
∠ “Not halting on w” also neither implies w ∈ L(M) nor w /∈ L(M). Those are
determined by whether the TM ever traverses a final state. However, if the TM is
“reasonable”, then w /∈ L(M) (i.e., the word is rejected).
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 11 / 34
Introduction to TMs
On Acceptance, Rejection, Halting, and Decidability
Accepted
w ∈ L(M)
Rejected
w /∈ L(M)
Halted on w
reached a final state,
possibly kept going, then
eventually reached a
point where no further
transition was possible
eventually reached
a point where no
further transition was
possible and never
traversed a final state
Looped forever on w
reached a final state
and keeps making
transitions forever
keeps making transitions
forever, traversing
non-final states only
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 12 / 34
Extensions of TMs
Extensions of TMs
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 13 / 34
Extensions of TMs
Multiple-Track TMs
Multiple-track TM
∠ We do not provide a formal definition (but assume you could provide one).
∠ There are k tracks, each having symbols written on them. They are essentially tapes,
but we call them that way since they are not independent.
∠ The machine can only read symbols from each tape corresponding to one location,
i.e., all symbols in a column at any one time.
∠ Likewise, all tapes move simultaneously in the same direction.
Finite Control
· · ·· · ·
· · ·· · ·
· · ·· · ·
...
X1
X2
Xk
∠ A k-track TM with tape alphabet Γ has the same language-acceptance power as a
TM with tape alphabet Γk . (E.g., each cell contains the “symbol” (X1, . . . ,Xk))
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 14 / 34
Extensions of TMs
Multi-tape TMs
Multiple-tape TM
∠ We (again) don’t provide a formal definition (but assume you could provide one).
∠ There are k (independent) tapes, each having symbols written on them.
∠ The machine can read each tape independently, i.e., the symbols read from each tape
need not correspond to the same location.
∠ After all tapes are read, all tape transitions must happen (now we can also stay with
a head – the entire TM is for convenience anyway!).
Finite Control
· · ·· · ·
· · ·· · ·
· · ·· · ·
...
X1
X2
Xk
∠ The rest stays the same (e.g., one set of states, acceptance, etc.).
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 15 / 34
Extensions of TMs
Multi-tape TMs
Theorem 8.2.1
Every language that is accepted by a multi-tape TM is also recursively enumerable
(i.e., accepted by some ‘standard’ TM).
Proof of Theorem 8.2.1
∠ Let L be accepted by a k-tape TM M. We’ll devise a 2k-track TM M ′ that accepts L.
∠ Every even tape of M ′ has the same alphabet as that of the k-tape TM.
The 2i th track of M ′ contains exactly the same contents as the i th tape of M.
∠ Every odd track has an alphabet {B, †}, and contains a single †.
The 2i − 1th track of M ′ contains † at the location where the i th head of M is located.
Finite Control Finite Control
· · ·· · ·
· · ·· · ·
· · ·· · ·· · ·
10 11
54
1312
6 14
†
12
†
†
0 1 1 0 0 1 1 0 0
1 1 1 1 0 0 0
0 0 0 0
0 1 1 0 0 1 1 0 0
0
1 1 1 1
1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1
M 0 M
· · ·· · ·
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 16 / 34
Extensions of TMs
Multi-tape TMs
Proof of Theorem 8.2.1 (1 of 3)
What is the main problem we need to solve?
∠ In the Multi-tape TM M, heads move independently, whereas in the Multi-track TM
M ′ they do not. So the heads can diverge:
Finite Control Finite Control
· · ·· · ·
· · ·· · ·
· · ·· · ·· · ·
10 11
54
1312
6 14
†
12
†
†
0 1 1 0 0 1 1 0 0
1 1 1 1 0 0 0
0 0 0 0
0 1 1 0 0 1 1 0 0
0
1 1 1 1
1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1
M 0 M
· · ·· · · (But M ′ has just a single head position!)
So, how to solve it?
∠ Make sure that in each transition of M, we visit all heads of M ′.
∠ “Store” all head positions in a state with k (number of tapes) entries.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 17 / 34
Extensions of TMs
Multi-tape TMs
Proof of Theorem 8.2.1 (2 of 3)
∠ The state of M ′ has 3 components: (a) the state of M; (b) the number of †s to its
head’s strict left; and (c) a k-length tuple from (Γ ∪ {?})k .
∠ At the beginning of the sweep, the head of M ′ is at the location of the leftmost † and
the state of M ′ is (q, 0, [?, · · · , ?]). The head moves to the right uncovering †s and
the corresponding track symbols (are stored in the third component of the state).
∠ Each move of M takes multiple moves of M ′, and is a sweep of the tape from the
location of the leftmost † to that of the rightmost † and back performing the changes
to tracks that M would do to its corresponding tapes.
∠ The right sweep ends when the second component is k.
Finite Control Finite Control
· · ·· · ·
· · ·· · ·
· · ·· · ·· · ·
10 11
54
1312
6 14
†
12
†
†
0 1 1 0 0 1 1 0 0
1 1 1 1 0 0 0
0 0 0 0
0 1 1 0 0 1 1 0 0
0
1 1 1 1
1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1
M 0 M
· · ·· · ·
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 18 / 34
Extensions of TMs
Multi-tape TMs
Proof of Theorem 8.2.1 (3 of 3)
∠ At this stage (once the i in (q, i , [γ1, · · · , γk ]) is k and all γj are set), M ′ knows the
head symbols M will have read, and knows what actions to take.
∠ It then sweeps left making appropriate changes to the tracks (just like M does to its
tape) each time a † is encountered. M ′ also moves the †s accordingly.
∠ The left sweep ends when the second component is zero. At this time, M ′ would
have completed moving the †s and the track contents; they’ll now match those of M.
∠ M ′ then moves the state to (q′, 0, [?, · · · , ?]) and starts the next sweep if q′ is not a
final state.
∠ Note that M ′ mimics M and hence the languages accepted are identical.
Finite Control Finite Control
· · ·· · ·
· · ·· · ·
· · ·· · ·· · ·
10 11
54
1312
6 14
†
12
†
†
0 1 1 0 0 1 1 0 0
1 1 1 1 0 0 0
0 0 0 0
0 1 1 0 0 1 1 0 0
0
1 1 1 1
1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1
M 0 M
· · ·· · ·
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 19 / 34
Extensions of TMs
Multi-tape TMs
∠ The running time of a TM M with input w is the number of moves M makes before
it halts. (If it does not, the running time is ∞).
∠ The time complexity TM : {0, 1, . . .} → {0, 1, . . .} ∪ {∞} of a TM M is defined as:
∠ TM(n) := maximum running time of M for an input w of length n symbols.
Theorem 8.2.2
The time taken for M ′ in Theorem 8.2.1 to process n moves of k-tape M is O(n2).
Outline of Proof of Theorem 8.2.2
∠ In the ith move of M, any two heads of M
can be at most 2i locations apart.
∠ Each sweep then requires 4i moves of M ′.
∠ Each track update requires Θ(k) time.
∠ So, n moves in M need O(n2) moves in M ′.
! !
!
!


· · ·
· · ·
Moves ofM0 n
Lo
ca
tio
n
of
ta
pe
he
ad
s
n
0
n
2n
ap
ar
t
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 20 / 34
Extensions of TMs
Non-deterministic TMs
Non-deterministic TM: δ(q,X ) is a set of triples representing possible moves.
Theorem 8.2.3
For every non-deterministic TM M, there is a TM N such that L(M) = L(N).
Outline of Proof of Theorem 8.2.3
ID1
ID2;1 ID2;2 ID2;k
ID3;1 ID3;2 ID3;3 ID3;4 ID3;‘
· · ·
· · ·
ID1
ID3;1 ID3;2
ID3;3 ID3;4
‡ †
ID1 ID2;1 ID2;2‡ † † · · ·† † ID2;k †
ID1 ID2;1 ID2;2‡ † · · ·† † ID2;k † † †
ID3;1 ID3;2ID1 ID2;1 ID2;2‡ · · ·† † ID2;k † † † † †
‡
‡ ‡
Tape 1
(IfM does not halt at ID1)
(IfM does not halt at ID1 and ID2;1)
(IfM does not halt at ID1, ID2;1 and ID2;2)
(N does Breadth-First exploration of IDs ofM)
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 21 / 34
Extensions of TMs
Outline of Proof of Theorem 8.2.3
∠ We can devise a 2-tape TM N that simulates M.
∠ N first replaces the content of the first tape by ‡ followed by the ID that M is initially
in, which is then followed by a special symbol †, which serves as ID separator.
(N uses the second tape as scratch tape to enable this operation).
∠ If the ID corresponds to a final state, N accepts (as would M).
∠ If not, N then identifies all possible choices for the next IDs for M and enters each
one of them followed by † at the right end of its first tape. (Again, N uses the second
tape as scratch tape to enable this operation.)
∠ N then searches for † to the right of ‡, changes the † to a ‡ (to signify that it is
processing the succeeding ID), and processes that ID in the similar way.
∠ N halts at an ID iff M would at that ID. (To have halting equivalence.)
ID1
ID2;1 ID2;2 ID2;k
ID3;1 ID3;2 ID3;3 ID3;4 ID3;‘
· · ·
· · ·
ID1
ID2;1 ID2;2 ID2;k
ID3;1 ID3;2 ID3;3 ID3;4 ID3;‘
· · ·
· · ·
ID1
ID3;1 ID3;2
ID3;3 ID3;4
‡ †
ID1 ID2;1 ID2;2‡ † † · · ·† † ID2;k †
ID1 ID2;1 ID2;2‡ † · · ·† † ID2;k † † †
ID3;1 ID3;2ID1 ID2;1 ID2;2‡ · · ·† † ID2;k † † † † †
‡
‡ ‡
Tape 1
(IfM does not halt at ID1)
(IfM does not halt at ID1 and ID2;1)
(IfM does not halt at ID1, ID2;1 and ID2;2)
(N does Breadth-First exploration of IDs ofM)
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 22 / 34
Restrictions of TMs
Restrictions of TMs
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 23 / 34
Restrictions of TMs
TM Semi-infinite Tape
A TM with a semi-infinite tape is a TM that only has blanks on one of its sides, but not
on the other.
Phrased (slightly) more formally:
A TM with a semi-infinite tape is a TM that can never move to left of the left-most
input symbol.
We don’t provide a formal definition, but a way of simulating this is by providing a
special symbol, placed on the left of the input, and defining the transitions to always go
to the right when this is read.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 24 / 34
Restrictions of TMs
TM Semi-infinite Tape
Theorem 8.3.1
Every recursively enumerable language is also accepted by a TM with semi-infinite tape.
Outline of Proof of Theorem 8.3.1
∠ Given a TM M that accepts a language L, construct a two-track TM M ′ as follows.
∠ The first/second tracks of M ′ are the right/left parts of the tape of M.
∠ First, write a special symbol, say † at the leftmost part of the second track; this
indicates to M ′ that a left move is not to be attempted at this location.
∠ At any time, M ′ keeps track of whether M is to the right or left of its start location.
If M is to the strict right of its start location, M ′ mimics M on the first track.
If M is to the strict left of its start location, M ′ mimics M on second track, but
with the head directions reversed. M ′ detects the start by the † symbol.
∠ It can be formally shown that M ′ accepts a string iff M accepts it.
0 11 22
BB ab b ab b
† BB
12
0 1 2
· · ·· · ·
· · ·· · ·
· · ·
· · ·
· · ·
M 0M L$ RL$ RL$ R
R$ L
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 25 / 34
Extensions of PDAs
Extensions of PDAs
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 26 / 34
Extensions of PDAs
Multi-stack Machines
A multistack machine is a PDA with several independent stacks (i.e., one can be popping
a symbol, while another is pushing a symbol).
Theorem 8.4.1
Every recursively enumerable language is accepted by a two-stack PDA
Outline of Proof of Theorem 8.4.1
∠ Let each stack again contain a bottom-most start symbol.
∠ Let ID = x−3x−2x−1qx0x1x2, i.e., w = x−3x−2x−1x0x1x2, and head read reads x0
Let stack-1 contain x0x1x2 (with x0 at the top), representing the head position
and the symbols to its right.
Let stack-2 contain x−1x−2x−3 (with x−1 at the top), representing the symbols
to the left of the head in reversed order.
∠ What if we move the head to the right? Then, ID’ = x−3x−2x−1x0q′x1x2.
We can easily do this with our stacks:
How should the stack now look like?
stack-1: x1x2 and stack-2: x0x−1x−2x−3.
But that’s just a simple pop and push!
∠ Moving to the left, and changing the symbol that’s written can be simulated as well.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 27 / 34
Extensions of PDAs
Multi-stack Machines
Outline of Proof of Theorem 8.4.1, cont’d
∠ Remaining problem: How to fill the stacks initially?
∠ Recall: stack-1 contains what’s right of the head and stack-2 what’s left (but
reversed).
∠ Initial configuration is q0w , so stack-1 should be w and stack-2 “empty”.
∠ We achieve this by the following procedure:
∠ I.e., run to the right filling stack-2, then run back putting it on stack-1.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 28 / 34
Extensions of PDAs
Counter Machines
∠ A counter machine is a multi-stack machine whose stack alphabet contains two
symbols: Z0 (stack end marker) and X
∠ Z0 is initially in the stack.
∠ Z0 may be replaced by X
iZ0 for some i ≥ 0
∠ X may be replaced by X i for some i ≥ 0.
∠ A counter machine effectively stores a non-negative number.
Finite Control
X
Z0
X
X
X
Z0
X
X
X
X
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 29 / 34
Extensions of PDAs
Simulating a 2-Stack PDA with a 3-Counter Machine
Theorem 8.4.2
Every recursively enumerable language is accepted by a three-counter machine.
Key Challenge
∠ Challenges:
A 2-stack PDA uses arbitrary symbols on its stacks.
A counter machine can only store and manipulate numbers.
We must encode a stack’s contents into a single number so that counter
operations can simulate stack operations.
We must implement mathematical operations in a stack to encode push and pop
operations on the “single numbers”.
∠ How stacks work?
counter 1 and 2 encode stacks 1 and 3
counter 3 is used for additional computations
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 30 / 34
Extensions of PDAs
Encoding a Stack into a Counter
Encoding Method
∠ Assign each symbol in the stack alphabet a unique number:
A = 0,B = 1,C = 2, . . . ,D = 3, etc.
∠ Represent a stack as a single number using positional encoding:
X = Y1 + rY2 + r
2Y3 + · · ·+ r k−1Yk
where:
Y1 is the top symbol,
Y2,Y3, . . . are symbols below it,
r = |Γ|, the size of the stack alphabet.
Example
∠ Suppose the stack contains (top to bottom): B,C ,A,A,D.
∠ Let r = 4 (since the alphabet has 4 symbols).
∠ Encode as: X = 1+ 4(2) + 42(0) + 43(0) + 44(3) = 777.
∠ The counter now stores X = 777.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 31 / 34
Extensions of PDAs
Simulating Stack Operations
Popping the Top Symbol
∠ Extract the top symbol using X mod r :
777 mod 4 = 1 ⇒ Top symbol was B
∠ Remove it by dividing by r : X ′ = ⌊X/4⌋ = 194.
∠ The counter now stores X ′ = 194, encoding stack
C ,A,A,D = 2+ 4(0) + 42(0) + 43(3) = 194.
Pushing a Symbol
∠ Suppose we push symbol A onto the stack C ,A,A,D.
∠ The current stack encoding is: X = 194.
∠ Compute the new encoding:
X ′ = 4 · X + 0 = 4 · 194+ 0 = 776.
∠ The counter now stores X ′ = 776, encoding stack A,C ,A,A,D:
776 = 0+ 4(2) + 42(0) + 43(0) + 44(3).
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 32 / 34
Extensions of PDAs
Counter Machine Implementation
∠ Computing X mod r (extracting top symbol from stack 1 or 2):
Subtract r repeatedly from the respective stack counter (1 or 2) until value is
less than r .
This remaining value is the top symbol.
∠ Computing X ′ = ⌊X/r⌋ (removing top symbol from stack 1 or 2):
Move remainder to counter 3.
Subtract remainder from stack counter.
Divide stack counter by r by decrementing it while incrementing counter 3 in
steps of r .
∠ Computing X ′ = rX + Z (pushing a symbol onto a stack):
Copy X to counter 3.
Multiply counter 3 by r by adding it to itself r times.
Add Z to counter 3.
Copy the result back to the respective stack counter (1 or 2).
∠ Ensuring correct stack operations:
Stack 1 and stack 2 each use a separate counter.
When operating on stack 1, stack 2 stays unchanged, and vice versa.
Counter 3 is used only as temporary storage.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 33 / 34
Extensions of PDAs
Simulating a 3-Counter Machine with 2 Counters
Theorem 8.4.3
Every recursively enumerable language is accepted by a two-counter machine.
Key Idea
∠ Encode three counters using prime factorization:
X = 2i3j5k , (1)
where i , j , k are the values of the three counters.
∠ Updates involve:
Multiplying by 2, 3, or 5 to increment.
Dividing by 2, 3, or 5 to decrement.
Checking divisibility to test for zero.
∠ Since a second counter can store temporary results, a 2-counter machine can simulate
a 3-counter machine.
Pascal Bercher week 5: Introduction to Turing Machines Semester 1, 2025 34 / 34

学霸联盟