The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 11 and
Foundations of Computation
The tutorial contains a number of exercises designed for the students to practice the course content. During the lab, the tutor will work through some of these exercises while the students will be responsible for completing the remaining exercises in their own time. There is no expectation that all the exercises will be covered in lab time.
Covers: Lecture Material Weeks 11, and Weeks 5 – 11
Exercise 1
Consider the sets and
Recursive Enumerability
E={w∈Σ∗ |wisacodeofaTMthatacceptsε} A={w∈Σ∗ |wisacodeofaTMthatacceptsatleastonestring}
(practice)
Are the sets E and A recursive?
Solution. First consider the set E. We claim that it is not recursive. If it were recursive, there would be a total (i.e. it terminates on all inputs) Turing machine T such that L(T ) = E . This would allow us to construct a new Turing machine H that would solve the halting problem.
The Turing machine H would implement the following algorithm.
1. Given input (M,w) to the halting problem, it constructs a new Turing machine M′ that operates as follows:
• If the input to M′ is not ε, halt and reject
• Otherwise, run M on input w and accept after the execution of M on w has terminated.
2. Run the Turing machine T on input M′.
Note that the TM H always terminates, as T always terminates by assumption. We then have that H accepts (M,w) iff T accepts M′ iff ε ∈ L(M′) iff the execution of M on w terminates. That is, H indeed solves the halting problem, contradiction.
For the set A we use a similar argument to show that A is not decidable. Suppose that A were decidable. Then there would be a total Turing machine T with L(T ) = A. This would allow us to construct a Turing machine H that solves the Halting problem. The TM H operates precisely as above, and in particular terminates for all inputs. For the TM M’ constructed above, note that L(M′) ⊆ {ε} so that
M′ accepts any string ⇐⇒ M′accepts ε.
In summary we have that H accepts (M, w) iff T accepts M ′ iff M ′ accepts any string iff M ′ accepts ε iff the execution
of M on input w terminates. In other words, H indeed solves the Halting Problem which is the intended contradiction. Exercise 2 Recursive Enumerability (useful)
Consider the alphabet Σ = {0, 1}. Show that if S ⊆ {0, 1}∗ is recursively enumerable and nonempty, then there exists a TM E (for ‘enumeration’) such that
• E terminates on all inputs
• for every input w, the tape content after running E on w is an element of S.
• for each element s ∈ S, there is an input w such that running E on w gives the output s.
In other words, E generates all elements of S, possibly with repetitions. Solution.
To see this, note that because S is recursively enumerable, there is a TM M with S = L(M ). As we just assume that S is recursively enumerable, the TM M does not necessarily terminate for all inputs.
Because S is not empty, there is an element c0 ∈ S. We say that w ∈ {0, 1}∗ is the n-th string in {0, 1}∗ if it appears at the n-th position in the following enumeration
’’
01
00 01 10 11
000 001 010 011 100 101 111 111 …
i.e. the 0-th string is the empty string ε, the third string is 1 and the 9th string is 001. Crucially, all w ∈ Σ∗ appear in this enumeration.
The TM E operates as follows. Given input string i that is not of the form 0n1k, the machine E replaces its input with c0.
Otherwise, if the input is of the form 0n 1k , it runs the TM M on input w for k steps, where w is the n-th string in {0, 1}∗ as given above. If M terminates on input w in k steps or fewer, the machine E replaces the input with w. Otherwise, the input is replaced with c0.
From the construction, it is clear that E satisfies the two requirements above:
• theoutputofEiseitherc0 ∈SorwwhereweknowthatwisacceptedbyM,i.e.w∈L(M)=S.
• ifw∈S=L(M),thenMterminatesoninputw,sayinksteps.Ifwisthenth-stringin{0,1}∗,thenEterminates with output w on the input 0n1k.
This concludes the proof.
Exercise 3 Recursive Enumerability (hard)
Consider the alphabet Σ = {0, 1}. In the lectures, we have seen that the set
T ={w∈Σ∗ |wisthecodeofaTMthatterminatesonallinputs}
is not recursive. Is it recursively enumerable? ‘
Solution. It is not recursively enumerable. To see this, assume, for a contradiction, that T is recursively enumerable. As T is not empty, we obtain a TM E from the previous exercise that always terminates, and replaces its input with a binary string w such that:
• wisthecodeofatotalTM,i.e.w∈T
• everycodeofatotalTMarisesinthisway,i.e.foreachw∈T thereisi∈Σ∗ suchthatrunningEonigivesw.
Wewritef(w)fortheoutputoftheTMEoninputw,andnotethatf :Σ∗ →Σ∗ isatotalfunction,andT ={f(w)| w ∈ Σ∗}.
Now consider the TM P (‘P’ for paradox): given input w, run the (total) TM with code f(w) on input w and flip the result, i.e. accept if the TM f(w) rejects w, and accept if the TM f(w) rejects w. Because f is a total function, and we can use the TM E to compute f, this defines a total TM P.
As the range {f(w) | w ∈ Σ∗} contains all codes of total TMs, we have that P = f(w), for some w ∈ Σ∗. We can now ask whether P accepts w, or not.
Case 1. P accepts w. Then the TM with code f(w) rejects w (because of the flipping). But P is the TM with code f(w), so that P rejects w, contradiction.
Case 2. Similarly, if P rejects w, then the TM with code f(w) accepts w, i.e. P accepts w, contradiction.
In conclusion, our construction was based on the existence of M, i.e. the fact that T is recursively enumerable, and the
contradiction shows that M cannot exist, i.e. T is not recursively enumerable.
Exercise 4 Total Programming Languages (informal)
In view of the last exercise, do you agree or disagree with the statement
There is no programming language that only defines total functions, and allows to define all total functions.
and if so, why, and if not, why not?
Solution. The least requirement of a programming language would be that the set of syntactically correct programs in this language is recursively enumerable. As the language allows to define all total functions, this would mean, by the Church- Turing thesis, that the set of total recursive functions is recursively enumerable. The last exercise has demonstrated that this is not the case.
Alternatively, we can repeat the argument made in the previous exercise, but replace the concept of ’total TM” by the notion of definable functions in the given language.
Exercise 5 Decimal Expansion of π Consider the function
(insightful)
1 if there are n consecutive zeros in the decimal expansion of π 0 otherwise.
f(n) =
Is this function computable, i.e. does there exist a TM Mf over the alphabet Σ = {0, 1} such that:
• Mf terminates on all inputs
• after running fM on the binary coding of n, the tape contains the binary coding of f (n)?
Solution. The function is computable. There are two cases.
Case 1. The binary expansion of π contains n consecutive zeros for all n. Then the TM that erases the input, and replaces
it with 1 is a witness for the computability of f .
Case 2. The decimal expansion of π contains 0m but not 0m+1. Then the TM that
• replaces its input by 1 if the input is a binary coding of a number ≤ m • replaces its input by 0 if the input is a binary coding of a number > m
witnesses the computability of f.
The point here is that we don’t need to know or be able to compute whether the decimal expansion of π contains n
consecutive zeros or not. We know that there exists a TM for each case, we just don’t know which one is correct.
Exercise 6 Hoare Logic (revision) Consider the Hoare Triple:
[x>0] while (x ̸= 0) do x := x – 1 [true] 1. What is a suitable invariant P ?
Solution.
2. What is a suitable variant E? Solution.
x≤0
x
3. We wish to use Hoare Logic to prove the total correctness of the triple
[x>0] while (x ̸= 0) do x := x – 1 [true]
Solution.
1. x≥0∧x̸=0→x≥0(TrivialFact)
2. [x−1≥0∧x−1
For your reference the while-rule for total correctness is as follows:
P ∧ b → E ≥ 0 [P ∧ b ∧ E = n] S [P ∧ E < n] [P ] while b do S [P ∧ ¬b]
where n is an auxiliary variable not appearing anywhere else.
Exercise 7 Deterministic Finite Automata (revision)
Design a minimal DFA that recognises the language
{w ∈ {a,b}∗ | in w, every a is followed by bb}
Solution.
b
start S a S b S
b
a
a
012
To see that this automaton is minimal, we just need to demonstrate that the three non-accepting states are not equivalent. • S1 and S2 are not equivalent, as N∗(S1,b) ∈/ F but N∗(S2,b) ∈ F;
• S1 and S3 are not equivalent, as N∗(S1,bb) ∈ F but N∗(S3,bb) ∈/ F;
• S2 and S3 are not equivalent, as N∗(S2,b) ∈ F but N∗(S3,b) ∈/ F.
It is easy to see that the automaton recognises the given language.
Exercise 8 Push-down Automata (revision)
1. Design a (deterministic or non-deterministic) pushdown automaton that recognises precisely all odd length palin- dromes over the alphabet Σ = {a, b, c}. A palindrome is a word that reads the same backwards and forwards, e.g. “racecar” or “reviver”. Briefly explain the design of your automaton.
Solution. We design the following PDA where q0 is the starting state, and q3 is the only final state.
(q0, ♦, Z) (q1, , ♦) (q1, , ♦) (q2, , ) (q2, ε, Z)
→ q1, ♦Z → q1/♦, → q2, ♦ → q2, ε → q3, ε)
start push phase, all ♦ ∈ Σ continue push phase, all , ♦ ∈ Σ guess middle of string
match reverse
accept if fully read
2. Is your PDA deterministic or non-deterministic? Justify your answer.
Solution. It is non-deterministic, as there are two possible transitions from state q1 reading the same symbol with the same top of stack.
3. Give an execution trace of your PDA that shows that the word “accca” is accepted by your automaton.
Solution.
(q0, accca, Z) ⇒ (q1, ccca, aZ) ⇒ (q1, cca, caZ)
⇒ (q2, ca, caZ) ⇒ (q2,a,aZ) ⇒ (q2,ε,Z)
⇒ (q3,ε,ε)
S3 a,b
4. Argue why there cannot be an execution trace that accepts the word “acca” (which is an even-length palindrome).
Solution. The automaton pops one symbol for each symbol it pushes, with the exception of the second transition from state q1 (which consumes precisely one symbol of the input string). This transition occurs precisely once, so that the total number of characters in an accepted string must be odd.
Exercise 9 Regular Expressions (revision) In this exercise, we conceptualise regular expressions as string, and we add parentheses. Over the finite alphabet Σ =
{a, b, . . . , z}, a regular expression with parentheses is defined by the following: • ε, ∅ and each a ∈ Σ is a regular expression
• if r and s are regular expressions, the so are r|s, rs, r∗, and (r).
That is, the strings “abc”, “a|(bcd) ∗ e′′ and “a ∗ (b|c)d” are regular expressions with parentheses, but “∗ ∗ ba|′′ and “(ba(∗”
are not.
1. Design a context-free grammar that generates precisely all strings over the alphabet Σ ∪ {(, ), ∗, |, ∅, ε} that are regular expressions with parentheses.
Solution. We have the following grammar that is directly derived from the definition of regular expressions with parentheses. Note that the symbol “ε” carries a double meaning here: we use ε as a symbol in our grammar, and as a notation for the empty string. To avoid the confusion, we underline ε to mean the regular expression that matches the empty string.
S→ε S→∅ S→a
... S→z
S →SS S →S|S S →S∗ S →(S)
2. Hence, or otherwise, construct a pushdown automaton that accepts precisely all regular expressions with parenthe- ses.
Solution. We use the construction from the lectures to turn the grammar into a non-deterministic PDA. The PDA is given as A = (Q, q0, F, Σ, Γ, Z, δ) where the components are as follows:
• Q = {q0,q1,q2}
• F = {q1}
• Σ = {ε,∅,(,),∗,|,a,...,z} • Γ=Σ∪{S,Z}
and δ is the transition relation contains the initialisation transition
the termination transition:
the transition that expand the non-terminals:
(q0, ε, Z) (q1, ε, Z)
(q1, ε, S) (q1, ε, S) (q1, ε, S)
(q1, ε, S) (q1, ε, S) (q1, ε, S) (q1, ε, S) (q1, ε, S)
→ q1/SZ → q2/ε
→ q1/ε → q1/∅ → q1/a
→ q1/z → q1/SS → q1/S|S → q1/S∗ → q1/(S)
...
Exercise 10
→ q1/ε Turing Machine
(revision)
and the transitions that match the terminal symbols
(q1, ε, ε) (q1 , ∅, ∅) (q1, (, () (q1, ), )) (q1, |, |) (q1 , ∗, ∗) (q1 , a, a)
→ q1/ε → q1/ε → q1/ε → q1/ε → q1/ε → q1/ε → q1/ε
... (q1,z,z)
Specify a Turing machine which will multiply the binary number on its tape by 3. Assume (as above) that the head is initially somewhere over the data.
When doing this operation manually, we would work from right to left and compute a new value and a carry at each bit position. The carry can be 0, 1, or 2. The pair (new bit, carry-out) is a simple function of old bit value and carry-in. The following table captures this function.
012 0 0,0 1,0 0,1 1 1,1 0,2 1,2 Λ 0,0 1,0 0,1
We suggest that you try multiplying a few numbers by hand, using the above table, before starting on the Turing machine.
Solution.
001
0,R
c Λ
Λ,L
0,L c 1
1,L
1 0,L
1,L c
E C1 ' 0Λ0
E S0
E C0 ' ΛΛ
E C2
T
1 1,R
1,L 0,L 0,L Λ,R 1,S
c c Halt Halt
• Overview: The TM works from right to left along the binary number, multiplying each digit by 3, adding the “carry-in” from the previous step, and passing on the “carry-out” to the next step. Thus when 3n + i = k + 2j, and n is on the tape in state Ci, write k and go to state Cj; carry-in is i and carry-out is j.
• State S0: In this state the TM scans right to find the least significant bit.
• State Ci: This state indicates that the carry currently is i. The TM is to multiply the number whose rightmost digit (blank treated as 0) is under the head by 3, and add i (which is the “carry” from the previous step of the multiplication).
The important lesson here is that the state of the finite control is being used as memory.
Exercise 11 Another Undecidable Problem (revision) Show that the language
L = {w | w is an encoding of a TM that accepts all strings in Σ∗}
is undecidable.
Solution. Suppose the language L were decidable, so that we would have a TM T (for trivial) that decides L. We argue that this is impossible, as we could then decide the halting problem.
First note that L contains the code of (at least) one Turing machine: any Turing machine without transitions and where the initial state is final accepts all input strings. Pick any such machine M0.
To see that T would allow us to decide the halting problem, consider an arbitrary TM M and an input string w. We understand (M, w) as an input to the halting problem, and show that we can decide whether or not M terminates on input w, or not.
For this, we convert the pair (M, w) into a Turing machine Mw that we can then test to see whether it accepts all strings or not.
The machine Mw performs the following computation on an input string x. 1. run M on the string w
2. if the above step terminates, accept the string x.
We now claim that M terminates on w if and only if Mw accepts all strings in Σ∗.
First assume that M terminates on w. Then the computation in step 1 terminates, and the string x is accepted in step 2, i.e the machine Mw accepts all strings (as x was arbitrary).
Now suppose that M does not terminate on w. Then the computation gets stuck in point 1, hence Mw does not accept x, and is therefore not a machine that accepts all strings.
Note that the construction of Mw from M and w is clearly effective, and allows us to decide the halting problem: To decide whether machine M halts on w, check whether the machine Mw accepts all strings.
• if yes, then M terminates on w
• if no, then M does not terminate on w.