The Australian National University Research School of Computer Science
Theory of Computation
Release Date. Tuesday April 28 2020
Due Date. Tuesday May 12 2020, 23.50 Canberra time Maximum credit. 50
Exercise 1 The language of a Turing machine
Consider the Turing machine M = (Q, Σ, Γ, δ, q0, B, F ), where:
• Q = {q0,q1,q2,q3,q4,q5}; • Σ={a,b,c};
• Γ = {a,b,c,X,Y,Z,B}; • F = {q5}; and
and δ is given by the below diagram.
Semester 1, 2020 Assignment 2 of 3
(4 + 5 + 5 credits)
Y/Y,R a/a,R Z/Z,R Y/Y,R Y/Y,R a/X,R
B/B, R X/X, R b/Y, R
q5 q3 q2 c/Z,L
a/a, L Y/Y,L b/b, L Z/Z,L
b/b, R Z/Z,R
The goal of the exercise is to show that the language accepted by the above Turing machine is precisely L={akbkck |k≥1}.
(a) Showthatforalli∈Nandj∈Nwithj≥1
Xiq0ajY ibjZicj ⊢∗M Xi+1q0aj−1Y i+1bj−1Zi+1cj−1.
(b) Prove that all strings in L are accepted by M. (c) Prove that every string accepted by M is in L.
Hint. A possible approach is using the contrapositive: show that every string that is not in L, is not accepted by M.
Programming Help, Add QQ: 749389476
Solution of Exercise 1
(a) Since δ(q0, a) = (q1, X, R) we have
Xiq0ajY ibjZicj ⊢M Xi+1q1aj−1Y ibjZicj. (1)
Applying the transition δ(q1, a) = (q1, a, R) j − 1 times proves that
Xi+1q1aj−1Y ibjZicj ⊢∗M Xi+1aj−1q1Y ibjZicj (2)
and using δ(q1, Y ) = (q1, Y, R) i times shows
Xi+1aj−1q1Y ibjZicj ⊢∗M Xi+1aj−1Y iq1bjZicj. (3)
Since δ(q1, b) = (q2, Y, R) we find
Xi+1aj−1Y iq1bjZicj ⊢∗M Xi+1aj−1Y i+1q2bj−1Zicj. (4)
Using the transition δ(q2, b) = (q2, b, R) j − 1 times followed by using δ(q2, Z) = (q2, Z, R) i times gives
Xi+1aj−1Y i+1q2bj−1Zicj ⊢∗M Xi+1aj−1Y i+1bj−1Ziq2cj. (5) Next, we can apply δ(q2, c) = (q3, Z, L) to find either
Xi+1aj−1Y i+1bj−1Ziq2cj ⊢∗M Xi+1aj−1Y i+1bj−1Zi−1q3Z2cj−1 (6a) Xi+1aj−1Y i+1bj−1Ziq2cj ⊢∗M Xi+1aj−1Y i+1bj−2q3bZcj−1 (6b)
if i ≥ 1, or
if i = 0 and j ≥ 2, or
Xi+1aj−1Y i+1bj−1Ziq2cj ⊢∗M Xi+1aj−1Y iq3Y Zcj−1 (6c) if i = 0 and j = 1. Next, we use δ(q3,Z) = (q3,Z,L), then δ(q3,b) = (q3,b,L) j − 1, then
δ(q3, Y ) = (q3, Y, L) i + 1, then δ(q3, a) = (q3, a, L) to obtain
Xi+1aj−1Y i+1bj−1Zi+1q3cj−1 ⊢∗M Xiq3Xaj−1Y i+1bj−1Zi+1cj−1. (7)
Finally, since δ(q3, X) = (q0, X, R) we have
Xiq3Xaj−1Y i+1bj−1Zi+1cj−1 ⊢∗M Xi+1q0aj−1Y i+1bj−1Zi+1cj−1. (8)
Therefore, concatenating equations (??), (??), (??), (??), (??), (??) or (??) or (??), (??) and (??) (in that order) proves that
Xiq0ajY ibjZicj ⊢∗M Xi+1q0aj−1Y i+1bj−1Zi+1cj−1 (b) As a consequence of Part (??) we have
q0akbkck ⊢∗M Xkq0YkZk (9) Xkq0Y kZk ⊢∗M XkY q4Y k−1Zk. (10)
as required.
Since δ(q0, Y ) = (q4, Y, R), we have
Code Help
Since δ(q4, Y ) = (q4, Y, R) and δ(q4, Z) = (q4, Z, R) we find that
XkY q4Y k−1Zk ⊢∗M XkY kZkq4. (11)
Finally, δ(q4, B) = (qf , B, R) implies
XkYkZkq4 ⊢M XkYkZkBqf. (12)
Combining (??), (??), (??) and (??) yields
q0akbkck ⊢∗M XkY kZkBqf
and since qf ∈ F this proves that akbkck ∈ L(M). (c) By contrapositive. Let w ∈ Σ∗.
Case 1: The string w is empty. Suppose w is empty. Then the TM gets stuck in q0, which is not a final state. So the empty string is not accepted.
Case 2: The letters in w are not ordered alphabetically. In this case the string w con- tains at least two out of the three symbols in Σ. We split this into three subcases, based on the first occurring pair that witnesses the fact that w is not ordered alphabetically. In each case, we only move through non-final states.
Case 2A. The first witness of the fact that w is not ordered alphabetically is the substring ba, i.e., w is of the form aibjaw′ for some w′ ∈ Σ∗.
If i = 0 then we immediately get stuck at q0.
Otherwise, executing M gets us to states q1 and q2, and eventually to the ID Xai−1Y bj−1q2aw′. Since q2 has no outgoing transitions on input a, M gets stuck at this point. Since none of q0,q1 and q2 are in F, the string w is not accepted.
Case 2B. The first witness of the fact that w is not ordered alphabetically is the substring cb, i.e., w is of the form aibjckbw′ for some w′ ∈ Σ∗.
If i = 0 then we immediately get stuck at q0. If i > 0 and j = 0 then we get stuck in state q1. If i > 0 and j > 0 and k = 0 then we get stuck in q2.
Otherwise, executing leads us to the ID Xai−1Ybj−1Zck−1q4bw′. This is sent to Xai−1Y bj−1Zck−2q0cbw′ and the TM now gets stuck in q0 because from here there are no outgoing transitions on c.
Case 2C. The first witness of the fact that w is not ordered alphabetically is the substring cb, i.e., w is of the form aibjckaw′ for some w′ ∈ Σ∗.
If i = 0 then we immediately get stuck at q0. If i > 0 and j = 0 then we get stuck in state q1. If i > 0 and j > 0 and k = 0 then we get stuck in q2.
In this case, executing leads us to the ID Xai−1Ybj−1Zck−1q4aw′. This is sent to Xai−1Y bj−1Zck−2q0caw′ and the TM now gets stuck in q0 because from here there are no outgoing transitions on c.
Case 3: The string w is ordered alphabetically but is not balanced. That is, w = aibjck butwedonothavei=j=k.
Let l = min{i,j,k} be the minimum of i,j and k. Then we have
q0aibjck ⊢∗M Xlq0ai−lYlbj−lZlck−l.
By definition of l, either i − l = 0 or j − l = 0 or k − l = 0. In each of these cases, we do
not reach qf :
Case3A. Ifi−l=0,thentheheadstateiseitherY,b,c.Inthelattertwocasesweget stuck at q0. In the first case, we transition to ID XlY q4Y l−1bj−lZlck−l. Since w is unbalanced, either j − l > 0 or k − l > 0, and this gets us stuck in q4.
Case 3B. If i − l > 0 and j − l = 0 then we transition to Xl+1ai−l−1Y lq1Zlck−l, and since there are no Z-transition or c-transitions from q1, we get stuck.
Case3C.If i−l > 0 and j−l > 0 and k−l = 0, then we transition to Xl+1ai−l−1Y l+1bj−l−1Zlq2, and we get stuck in q2.
Exercise 2 Decidability (6 + 6 + 6 + 6 credits) For each of the following problems, state whether it is decidable. If it is decidable, outline a decision
procedure for it. If not, prove that it is undecidable.
In each case, the input is the code ⟨M⟩ of a Turing machine M = (Q,Σ,Γ,δ,q0,B,F).
(a) Isthereaninputx∈Σ∗ oflength<10suchthatM haltsin<100stepswhenrunonx? (b) Isthereaninputx∈Σ∗ oflength≥10suchthatM haltsin<100stepswhenrunonx?
(c) Isthereaninputx∈Σ∗ oflength<10suchthatM runsfor≥100oninputx?
(d) Isthereaninputx∈Σ∗ oflength≥10suchthatM haltsin≥100stepswhenrunonx?
Solution of Exercise 2
(a) This problem is decidable. Since Σ is finite, there is a finite number of possible inputs of length ≤ 9. Therefore, we can simulate the first 99 steps of running the Turing machine M for each input. If it halts, then we stop simulating and return “yes”, if not then we know that there is no input of length ≤ 9 which halts in under 100 steps and return “no”.
(b) This problem is decidable. Since we require M to stop in under 100 steps, we only need to consider inputs of length ≤ 99. This can be done in a similar way as in part (a), replacing 9 by 99.
(c) We prove that this is undecidable by constructing a reduction from the halting problem. Let M′ be a Turing machine and x′ an input in the alphabet of M′.
Construct a new Turing machine M which ignores its input and simulates M′ on input x′. Note that such a transformation is implementable by a Turing machine (this is a “mind-bending step”). Then M halts (on any input) if and only if M′ halts on input x′. In particular, M′ halts on x′ iff there exists an input of length ≤ 9 such that M halts on x.
Suppose towards a contradiction that the given problem is decidable, then, combining this with part 2(a) proves that the problem “For any Turing machine M, does there exist an input x of length ≤ 9 such that M halts on x” is decidable. But because of the previous paragraph, this would imply that the halting problem is decidable. A contradiction. Therefore the problem in 2(c) is not decidable.
(d) This is completely analogous to item 2(c). We repeat the argument here.
We prove that this is undecidable by constructing a reduction from the halting problem. Let M′
be a Turing machine and x′ an input in the alphabet of M′.
Construct a new Turing machine M which ignores its input and simulates M′ on input x′. Note that such a transformation is implementable by a Turing machine (this is a “mind-bending step”). Then M halts (on any input) if and only if M′ halts on input x′. In particular, M′ halts on x′ iff there exists an input of length ≥ 10 such that M halts on x.
Suppose towards a contradiction that the given problem is decidable, then, combining this with part 2(b) proves that the problem “For any Turing machine M, does there exist an input x of length ≥ 10 such that M halts on x” is decidable. But because of the previous paragraph, this
程序代写 CS代考 加QQ: 749389476
would imply that the halting problem is decidable. A contradiction. Therefore the problem in 2(d) is not decidable.
Exercise 3 Recursive Enumerability (6 + 6 credits)
The problems here are the same as in Part (a) and (b) of the previous exercise, but the goal is to show that they are recursively enumerable. As in the previous exercise, the input is the code ⟨M⟩ of a Turing machine M.
(a) Isthereaninputx∈Σ∗ oflength<10suchthatM runsfor≥100stepsoninputx?
(b) Isthereaninputx∈Σ∗ oflength≥10suchthatM haltsin≥100stepswhenrunonx?
Solution of Exercise 3
(a) There is a finite number of inputs of length ≤ 9. Therefore, given a Turing machine M, we can simulate each of these inputs simultaneously. For the simulation of the first 99 steps, we ignore any simulation that halts and exclude those inputs from the simulation. From step 100 onwards of the simulations, if any simulated input causes M to halt, we return “yes.”
(b) This is similar to part (a), except we cannot simulate each input simultaneously. However, there
are countably many inputs (to see this, enumerate the elements of Σ as a1 , . . . , an and the primes
asp ,p ,...,thenΣ∗ →N:a a ···a →pi1 ×pi2 ×···×pim isaninjectionofΣ∗ intothe
12 i1i2im12 m
natural numbers). Therefore we can use a technique called “dovetailing”.
We enumerate all inputs of Σ∗ of length ≥ 10. We simulate in rounds indexed by n ∈ N, and in
round n we simulate the i-th step of (n − i)-th input of Σ∗≥10.
If an input halts on x ∈ Σ∗≥ 10 in the first 99 steps of its simulation, then we ignore it. If an input x ∈ Σ∗≥10 halts after 100 or more steps of its simulation, we return “yes.” This procedure verifies that every yes-input really is a yes-input, so the problem is recursively enumerable.
Rubric. For Exercise 1 we expect arguments that use the definition of acceptance of a string in a Turing machine, and IDs. For Exercises 2 and 3 we expect a level of detail comparable to that of the lecture slides.