COMP30026 Models of Computation – Recognisable and Decibale Languages
COMP30026 Models of Computation
Recognisable and Decibale Languages
Bach Le / Anna Kalenkova
Lecture Week 11. Part 1
Semester 2, 2021
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 1 / 33
Turing Machines: Simulation
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 2 / 33
Multitape Machines
A multitape Turing machine has k
tapes. It takes its input on tape 1,
other tapes are blank.
The transition function now has
type
δ : Q × Γk → Q × Γk × {L,R}k
It specifies how the k tape heads
behave when the machine is in
state qi , reading a1, . . . ak :
δ(qi , a1, . . . , ak) = (qj , (b1, . . . , bk), (d1, . . . , dk))
state
control
x y a y x x
b b b
b a a x x
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 3 / 33
Simulating a Multitape Machine
Theorem: A language is Turing recognisable iff some multitape
Turing machine recognises it.
Proof sketch: We show how to simulate a multitape machine M by
a standard Turing machine S .
Suppose the multitape machine’s tape alphabet is Γ.
The standard machine has tape alphabet {#} ∪ Γ ∪ Γ′ where # is a
separator, not in Γ ∪ Γ′, and there is some one-to-one correspondence
between elements in Γ and elements in Γ′.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 4 / 33
Simulating a Multitape Machine
M
c a a x x
b b b
x c a c x x
S
# c′ a a x x # b b b xy′ # x c a c x′
S reorganises input x1x2 · · · xn into #x
′
1×2 · · · xn#xy
′# · · ·#xy′#
︸ ︷︷ ︸
k−1 times
Note how elements of Γ′ represent “marked” elements from Γ.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 5 / 33
Simulating a Multitape Machine
Simulating an M move, S scans its tape to determine the marked
symbols. On a second scan it updates the tape according to M ’s
transition function.
If a “virtual head” of M moves to a #, S shifts that symbol, and
every symbol after it, one cell to the right. In the vacant cell it
writes xy.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 6 / 33
Nondeterministic Turing Machines
A nondeterministic Turing machine has a transition function of type
δ : Q × Γ → P(Q × Γ× {L,R})
If some computation branch leads to ‘accept’ then the machine
accepts its input.
This is the same type of nondeterminism that an NFA possesses.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 7 / 33
Simulating a Nondeterministic Turing Machine
First, a deterministic
machine to generate
{1, . . . , k}∗, in order
of increasing length.
Try running it for k = 3.
xy→ R xy→ L
xy→ Rxy→ 1, L
i → L
i → R
k → 1, L
1 → R
1 → 2, L
2 → 3, L
…
(k − 1) → k, L
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 8 / 33
Simulating a Nondeterministic Turing Machine
Theorem: A language is Turing recognisable iff some
nondeterministic Turing machine recognises it.
Proof sketch: We need to show that every nondeterministic Turing
machine N can be simulated by a deterministic Turing machine D.
We show how it can be simulated by a 3-tape machine.
Let k be the largest number of choices, according to N’s transition
function, for any state/symbol combination.
Tape 1 contains the input.
Tape 3 holds longer and longer sequences from {1, . . . , k}∗.
Tape 2 is used to simulate N’s behaviour for each fixed sequence of
choices given by tape 3.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 9 / 33
Simulating a Nondeterministic Turing Machine
D
Tape 3
Tape 2
Tape 1
xy 3 1 1 3 1
x b a x xy
a b b xy
1 Initially tape 1 contains input w . The other two tapes are empty.
2 Overwrite tape 2 by w .
3 Use tape 2 to simulate N. Tape 3 dictates how N should make
its choices. If N says accept, accept. If the “choice list” on tape
3 gets exhausted, go to step 4.
4 Generate the next choice list on tape 3. Go to step 2.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 10 / 33
Enumerators
The Turing machine we built to generate all strings in {1, . . . , k}∗ is
an example of an enumerator.
We could imagine it being attached to a printer, and it would print
all the strings in {1, . . . , k}∗, one after the other, never terminating.
For an enumerator to enumerate a language L, for each w ∈ L, it
must eventually print w .
The reason why we also call Turing recognisable languages recursively
enumerable is the following theorem.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 11 / 33
Enumerators
Thm: L is Turing recognisable iff some enumerator enumerates L.
Proof: Let E enumerate L. Then we can build a Turing machine
recognising L as follows:
1 Let w be the input.
2 Simulate E . For each string s output by E , if s = w , accept.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 12 / 33
Enumerators
Thm: L is Turing recognisable iff some enumerator enumerates L.
Proof: Let E enumerate L. Then we can build a Turing machine
recognising L as follows:
1 Let w be the input.
2 Simulate E . For each string s output by E , if s = w , accept.
Conversely, let M recognise L. Then we can build an enumerator E
by elaborating the enumerator from a few slides back: We can
enumerate Σ∗, producing s1, s2, . . .
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 12 / 33
Enumerators
Thm: L is Turing recognisable iff some enumerator enumerates L.
Proof: Let E enumerate L. Then we can build a Turing machine
recognising L as follows:
1 Let w be the input.
2 Simulate E . For each string s output by E , if s = w , accept.
Conversely, let M recognise L. Then we can build an enumerator E
by elaborating the enumerator from a few slides back: We can
enumerate Σ∗, producing s1, s2, . . . Here is what E does:
1 Let i = 1.
2 Simulate M for i steps on each of s1, . . . si .
3 For each accepting computation, print that s.
4 Increment i and go to step 2.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 12 / 33
Termination
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 13 / 33
Partial Functions
We have silently assumed that the domain of a function is known, so
that f : X → Y means that f (x) is defined for each x ∈ X .
In computer science, however, it is often more appropriate to deal
with functions that are partial.
We write f : X →֒ Y to say that f has a domain which is a subset of
X , but f (x) may be undefined for some x ∈ X .
Note that a total function f : X → Y is by definition also partial:
f : X →֒ Y .
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 14 / 33
Partial Functions: Example 1
The function f defined by
f (n) =
{
42 if n = 0
f (n − 2) if n 6= 0
is a partial function f : Z →֒ Z.
In a natural interpretation, it is undefined if n is odd and/or negative.
Its range is {42}.
In this case, it is not too hard to determine the set of values for
which f is defined. So we could also choose to say that f is a total
function X → Z, where X = {n ∈ Z | n ≥ 0 ∧ n is even}.
However, it is not always easy, or even possible, to determine a
function’s domain.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 15 / 33
Partial Functions: Example 2
The function c defined by
c(n) =
1 if n = 0 or n = 1
c(n/2) if n is even and n > 1
c(3n + 1) if n is odd and n > 1
is a partial function c : N →֒ N with range {1}.
Will the evaluation of c(n) terminate for all n?
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 16 / 33
Partial Functions: Example 2
The function c defined by
c(n) =
1 if n = 0 or n = 1
c(n/2) if n is even and n > 1
c(3n + 1) if n is odd and n > 1
is a partial function c : N →֒ N with range {1}.
Will the evaluation of c(n) terminate for all n?
It is not known whether c is total.
This is the so-called 3n + 1 problem, or Collatz’s problem.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 16 / 33
Program Termination
Here is a Haskell program that produces the list of n-values generated
in successive recursive calls:
c :: Integer -> [Integer]
c 0 = [1]
c 1 = [1]
c n = n : c (if even n then n ‘div‘ 2 else 3*n+1)
Colatz’s sequence for 27: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137,
412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502,
251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644,
1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244,
122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1.
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 17 / 33
Program Termination
Here it is as a flowchart program:
n := n/2 n even n := 3*n+1
n == 0 or n == 1 halt
read n
no
yes
yes no
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 18 / 33
Quiz 1: Does It Terminate?
Here is a variant. Does this halt for all positive input?
n := n/2 n even n := n-3
n == 0 or n == 1 halt
read n
no
yes
yes no
Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 19 / 33
Quiz 2: Does It Terminate?
And how about this? Does it halt for all input?
m,n := m-4,n+1 m > n m,n := m+2,n-1
m < 1 or n < 1 halt read m,n no yes yes no Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 20 / 33 Proving Termination Suppose that, for each loop in a program, we can find some “measure” (a function of the program variables) such that 1 the measure is a natural number, and 2 the measure gets smaller with each loop iteration. Then the program must terminate for all input, because a natural number cannot be made smaller indefinitely. Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 21 / 33 The Termination Question Termination of algorithms is a tricky problem (and the general problem is undecidable). For example, we suggested earlier algorithms for translating propositional formulas to, say, DNF, including rules like ¬(α ∧ β) ¬α ∨ ¬β ¬(α ∨ β) ¬α ∧ ¬β ¬¬α α α ∧ (β ∨ γ) (α ∧ β) ∨ (α ∧ γ) (β ∨ γ) ∧ α (β ∧ α) ∨ (γ ∧ α) Note that some of the rules decrease the size of a term, while others increase it (and some duplicate certain subterms). So why should this process terminate? Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 22 / 33 Quiz 3: A Marble Game You have a bag of red and white marbles, plus a box of red marbles. Repeat this process: If the bag contains exactly one marble, halt; otherwise take two random marbles from the bag. If they are of different colours, put them back. If they are of the same colour, discard both, but put one red marble (from the box) in the bag. Does this terminate? Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 23 / 33 Well-Founded Orderings The binary relation ≺ over some set X is well-founded iff there is no infinite sequence of X -elements x1, x2, x3, . . . such that x1 ≻ x2 ≻ x3 ≻ · · · We say that (X ,≺) is a well-founded structure. For example, (N, <) is a well-founded structure. Given a finite number of well-founded structures (X1,≺1), . . . , (Xn,≺n), we can obtain well-founded orderings of X = X1 × · · · × Xn in a number of different ways. Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 24 / 33 Ordering Pairs: Component-Wise Ordering (x1, x2) � (y1, y2) iff x1 ≤ y1 ∧ x2 ≤ y2 p ≺ q iff p � q ∧ p 6= q (0, 0) (0, 1) (1, 0) (0, 2) (1, 1) (2, 0) (0, 3) (1, 2) (2, 1) (3, 0) ... ... ... ... ... A Hasse diagram for component-wise ordering of N× N. Values increase as you travel up along edges. Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 25 / 33 Ordering Pairs: Lexicographic Ordering On the left: N with the usual ordering. On the right: (N× N,�), where � is lexicographic ordering: (m, n) � (m′, n′) iff m ≤ m′ ∧ (m = m′ ⇒ n ≤ n′). Define again p ≺ q iff p � q ∧ p 6= q. 0 1 2 3 4 ... (0, 0) (0, 1) (0, 2) ... (1, 0) (1, 1) ... (2, 0) (2, 1) ... Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 26 / 33 Well-Founded Orderings on Tuples Theorem: If ≺ is well-founded then so is its component-wise extension to tuples. Theorem: If ≺ is well-founded then so is its lexicographic extension to tuples. Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 27 / 33 Component-Wise Ordering of Tuples Ordering X = X1 × · · · × Xn component-wise: (x1, . . . , xn) � (y1, . . . , yn) iff n ∧ i=1 xi �i yi If each (Xi ,≺i) is well-founded, then so is (X ,≺). Example using component-wise ordering: (2, 2, 2) ≻ (2, 2, 1) ≻ (2, 1, 1) ≻ (2, 0, 1) ≻ (2, 0, 0) ≻ (0, 0, 0) Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 28 / 33 Lexicographic Ordering of Tuples Ordering X = X1 × · · · × Xn lexicographically: (x1, . . . , xn) ≺ (y1, . . . , yn) iff n ∨ i=1 ( xi ≺i yi ∧ i−1 ∧ j=1 xj = yj ) If each (Xi ,≺i) is well-founded, then so is (X ,≺). Example using lexicographic ordering: (2, 2, 2) ≻ (2, 1, 42) ≻ (1, 3, 1000) ≻ (1, 3, 999) ≻ (1, 3, 0) ≻ (0, 0, 15) Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 29 / 33 Well-Founded Induction There is an induction principle to go with well-founded relations. Given a well-founded structure (X ,≺) we can prove a statement “for all x ∈ X , S(x)” as follows: We proceed in one step: Assume that S(x ′) holds for all x ′ ≺ x , and use that to establish S(x). Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 30 / 33 Example 1: The Dutch Flag We have 12 pebbles laid out in a row. Consider three rewrite rules: (for a white left of a red, swap) (for a blue left of a red, swap) (for a blue left of a white, swap) To see that rewriting terminates, use < < together with lexicographic ordering on 12-tuples. Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 31 / 33 Example 2: Ackermann’s Function The following is a definition of Ackermann’s function: ack(0, y ) = y + 1 ack(x + 1, 0) = ack(x , 1) ack(x + 1, y + 1) = ack(x , ack(x + 1, y )) It grows incredibly fast. For example, ack(3, 3) = 61 and ack(4, 4) = 22 22 16 − 3. However, lexicographic well-founded induction allows us to conclude that the function is total—as a Haskell program it will terminate for all input (possibly after a very long time). Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 32 / 33 Example 2: Ackermann’s Function In each recursive call, the argument (x , y ) decreases strictly: ack(x + 1, 0) = x smaller ︷ ︸︸ ︷ ack(x , 1) ack(x + 1, y + 1) = ack(x , ack(x + 1, y ) ︸ ︷︷ ︸ x same, y smaller ) ︸ ︷︷ ︸ x smaller Models of Computation (Sem 2, 2021) Recognisable and Decibale Languages © University of Melbourne 33 / 33