0017 Computational Complexity problem sheet 2.
Reminder: a language is decidable if and only if there is a Turing machine that halts on a state Y when the input string is in the language, and halts in a state N when the input string is not in the language. A language is recognisable if and only if there is a Turing machine that halts when the input is in the language, and fails to halt when the input is not in the language.
1. This week we proved closure properties of decidable and recognisable languages under some operations. Now you are asked to give a detailed proof that decidable languages are closed under union. What we mean is that, as opposed to the proof sketch seen in class, you have to define in all its components a TM M = ⟨Σ, Q, q0, H, δ⟩ deciding L1 ∪L2, given TMs M1 = ⟨Σ, Q1, q01, H1, δ1⟩ deciding L1 and M2 = ⟨Σ, Q2, q02, H2, δ2⟩ deciding L2. You may assume that H1 = {Y1, N1} and H2 = {Y2, N2}, with acceptance of input strings defined by which halting state the computation ends in. You are also allowed to let M use multiple tapes.
Solution: The global idea of M is as follows:
Copyright By PowCoder代写 加微信 powcoder
(i) Use two tapes, and start by copying the input to the second tape. (ii) Rewind the heads back to the start of the two tapes.
(iii) Let M1 run on the first tape, leaving the second tape unchanged. (iv) If M1 accepts, then accept; otherwise, run M2 on the second tape.
(v) If M2 accepts, then accept; otherwise, reject.
Let us now give a concrete definition for M. We begin by choosing:
Q=Q ⊎Q ⊎{q,q,q,Y,N} H={Y,N} δ=δ ̃∪δ ̃∪δ′. 12012 12
As can be seen above, δ is made up of three parts; we define each part in such a way that δ remains a deterministic TM. First, we define δ ̃ :
(q′,σ1′,σ2) q∈Q1∧δ1(q,σ1)=(q′,σ1′) 1 1 2 undefined if δ1(q, σ1) is undefined
δ ̃ ( q , σ , σ ) =
That is, δ ̃ performs the actions of δ on the first tape, and leaves the
second tape unchanged. We define δ ̃ analogously, i.e., it performs the 2
actions of δ2 on the second tape, leaving the first tape unchanged.
The component δ′ acts as “glue” between the machines. First, it describes the transitions that copy the input string to the second tape, as preparation for the actual simulation of the two machines. In q0 we say that δ′ moves right on both tapes, entering q1:
δ′(q0, σ1, σ2) = (q1, →, →) (∀σ1, σ2 ∈ Σ) 1
Answers Not to be printed
If we are in q1 and read an input symbol, we copy that symbol to the second tape, and go back to q0; if we read a blank symbol on the second tape, we have reached the end of the input and move to q2:
δ′(q1,a,⊔) = (q0,a,a) ∀a ∈ ΣI δ′(q1, ⊔, ⊔) = (q2, ←, ←)
In q2, we rewind the tape back to the starting position; if we read a blank cell, it means we have reached the start of the input again, and we can continue in q01:
δ′(q2,a,a) = (q2,←,←) ∀a ∈ ΣI δ′(q2, ⊔, ⊔) = (q01, ⊔, ⊔)
Once we hit the end of the input in q1, by reading a ⊔, we proceed to
state q2, in which we rewind both tapes to the beginning of the input.
Now the computation is like a simulation of M1 using the extended
δ ̃ . If the state N (which is not an halting state anymore) is reached, 11
we define δ′ to enter state q02 and continue with the simulation of M2; likewise, if we reach Y1, the machine enters the accepting state Y :
δ′(N1, σ1, σ2) = (q02, σ1, σ2) ∀σ1, σ2 ∈ Σ δ′(Y1, σ1, σ2) = (Y, σ1, σ2) ∀σ1, σ2 ∈ Σ
In the former case, note that the head for the second tape is still on
the first position. This will begin a simulation of M2 on the second
tape, using δ ̃. Once we reach N , we reject the input by moving to N; 22
otherwise, if we reach Y2, we accept the input by moving to Y : δ′(N2, σ1, σ2) = (N, σ1, σ2) ∀σ1, σ2 ∈ Σ
δ′(Y2, σ1, σ2) = (Y, σ1, σ2) ∀σ1, σ2 ∈ Σ One can check this description meets the specification given in class
for a machine deciding L1 ∪ L2.
Non-deterministic solution We build a machine with states Q = Q1 ∪Q2 ∪{q0,Y,N}, where the initial state is q0, the accepting state is Y and the rejecting state is N.
The transition relation is defined as follows:
δ = δ1 ∪ δ2 ∪ ((q0, ⊔), (q01, ⊔)), ((q0, ⊔), (q02, ⊔))
∪ {((Y1, a), (Y, a)) : a ∈ Σ} ∪ {((Y2, a), (Y, a)) : a ∈ Σ} ∪ {((N1, a), (N, a)) : a ∈ Σ} ∪ {((N2, a), (N, a)) : a ∈ Σ}
In essence, this machine follows the following pattern: 2
Answers Not to be printed
a/a q01M1 Y
N2 a/a Deterministic solution with parallelism The idea is as follows:
(i) We copy the input on the first tape to the second tape; this can be done in a manner similar to the first solution.
(ii) We run M1 on the first tape parallel with M2 on the second tape.
(iii) Whenever one of the machines halts on its accepting state, we move to a global accepting state Y , and if both machines halt on their rejecting states, we reject.
The precise solution goes as follows. The set of states is Q=(Q1 ×Q2)∪{q0,q1,q2,Y,N}
The initial state is q0. The part of δ responsible for copying the input and rewinding the tape is given as follows:
Y2 a/a q02M2 N
δ(q0,σ1,σ2) = (q1,→,→) δ(q1,a,⊔) = (q0,a,a)
δ(q1,⊔,⊔) = (q2,←,←) δ(q2,a,a) = (q2,←,←)
The part that simulates M1 and M2 in parallel is:
δ(q2, ⊔, ⊔) = ((q01, q02), ⊔, ⊔) δ((q1, q2), σ1, σ2) = ((q1′ , q2′ ), σ1′ , σ2′ )
δ((N1, q2), σ1, σ2) = ((N1, q2′ ), σ1, σ2′ ) δ((q1, N2), σ1, σ2) = ((q1′ , N2), σ1′ , σ2)
The part that translates the accepting states is:
δ((N1, N2), σ1, σ2) = (N, σ1, σ2) δ((q1, Y2), σ1, σ2) = (Y, σ1, σ2) δ((Y1, q2), σ1, σ2) = (Y, σ1, σ2)
∀σ1,σ2 ∈ Σ ∀a ∈ ΣI
δi(qi, σi) = (qi′, σi′) δ2(q2, σ2) = (q2′ , σ2′ ) δ1(q1, σ1) = (q1′ , σ1′ )
∀σ1, σ2 ∈ Σ ∀σ1, σ2 ∈ Σ ∀σ1, σ2 ∈ Σ
Answers Not to be printed
2. We now consider one more operation on languages: the Kleene star. Given L, applying the Kleene star to L yields
L⋆ ={ε}∪{a1a2…ak |ai ∈L,k∈N}
(a) Prove that decidable languages are closed under Kleene star. Idea of the solution: Suppose M is a TM deciding L. We design a non-deterministic TM M′ deciding L⋆. For simplicity our TM M′ has two tapes, and it uses a separator character ♯ on the tape. Essentially M′ non-deterministically guesses a splitting a1a2 ···ak of the input string a, and test if every ai is in L using M.
In a bit more detail, assume that initially the first tape has input string a, and the second tape is empty. If the input is empty, let M′ immediately accept. When the input is non-empty we do the following. First M′ goes through the input a on the first tape, and writes ♯ at both the beginning and the end of the input. On the first tape we now have ♯a♯. Next, M′ non-deterministically inserts the separator character ♯ into the input a such that ♯ does not appear twice in a row. On the first tape we now have ♯a1♯a2♯ · · · ♯ak♯. Then, M′ copies each of the strings between two adjacent separators ♯ on the first tape, say a1, . . . , ak, to the second tape in turn, and run M on the second tape. If M accepts the input for all of a1,…,ak, then accepts; otherwise rejects (i.e. when at least one of a1, . . . , ak is rejected).
We claim that M′ defined above decides L⋆. Clearly M′ accepts ε. For non-empty input a, on one hand, M′ accepts a if and only if there exists a non-deterministic choice of splitting a into a1 · · · ak such that each ai is accepted by M. By the definition of M, this means M′ accepts a if and only if M ∈ L⋆. On the other hand, M′ rejects a if and only if for all splitting of a into a1 ···ak, at least one ai among a1,…,ak is rejected by M. This means M′ rejects a if and only if a ̸∈ L ⋆. Therefore we know M′ decides L⋆.
(b) Prove the same, but now for recognisable languages.
Idea of the solution: Non-deterministically guess a splitting a1a2 . . . ak of a, similar to the proof of concatenation seen in class. First, such a TM could walk through the input, placing a separator ♯ at the beginning and end of the input, as well as between input characters nondeterministically, in such a way that ♯ does not occur twice in a row. Then, we copy each of the strings between separators on the first tape to the second tape in turn, where we run M; if M accepts the input each time, our TM also accepts. In the special case where the input is empty, the first phase should
Answers Not to be printed
not write any ♯ on the first tape, and thus the second phase succeeds immediately — there is nothing to check!
Note in particular that if M loops indefinitely on one of the strings that we feed it, this is not a problem — if the input is in L⋆, there is some way of splitting it such that we never cause M to loop.
3. A multi-head Turing machine is defined as a regular Turing machine, except the tape now has k heads. As usual, the computation begins with all the heads at the blank cell of the tape between the ◃ symbol and the input, and ends when reaching an halting state. During the computation, the heads move independently. However, in each state, only one of the heads is allowed to make an action (move or write). Formally this means that the k heads h1, h2, . . . , hk determine a partition Q1,Q2,…,Qk of the set of states Q, and when in state q ∈ Qi the associated action (move or write) concerns the head hi.
Prove that multi-head Turing machines are equivalent to classical (single-head) Turing machines. In the proof, the same level of precision
as in Lecture 4 will suffice. Solution: See this page.
4. Define unlimited register machines computing the following functions.
(a) f(n) = n if n is odd, f(n) = 0 otherwise.
Solution: The idea is to use the second register to “count to” the contents of the first register. If the contents of the two registers are equal after increasing the second number an odd number of times, then the first register must contain an odd number; we can then jump “out of” the program, leaving the first register intact. Otherwise, i.e., if the contents of the two registers are equal after increasing the second register an even number of times, then the first register must contain an even number; we then jump to a part of the program that sets the first register to zero, and exit.
1. J(1,2,6)
3. J(1, 2, 7)
5. J (1, 1, 1)
(R1 = R2, and R2 is even; jump to 6) (Increase R2 by one — R2 is now odd) (R1 = R2, and R2 is odd; stop program) (Increase R2 by one — R2 is now even) (Always jumps to start of program) (Set R1 to zero; terminate the program)
Answers Not to be printed
(b) f(n,m)=min(n,m).
Solution: The idea is to count with R3, and see whether R3 first becomes equal to R1 or R2. At each iteration, we check whether R1 = R3; if this is the case, then R1 must hold the minimum, and we can stop. If however R2 = R3, then R2 must hold the minimum; we swap the contents of R1 with R2, and stop.
1. J(1,3,6)
2. J(2,3,5)
4. J (1, 1, 1)
(If R1 = R3, then R1 is minimal; stop) (If R2 = R3, then R2 is minimal; jump to 5) (Increase our hypothesised minimum) (Always jumps to start of program) (Swap R1 with R2; terminate the program)
5. Recall the syntax of the programming language WHILE defined in class (page 23 of the slides of Lecture 6). This language does feature a primitive while command for controlling program flow, but not an if
…then, which is also typical of imperative programming languages. However, this is not really an issue: If-then can be defined as a macro, in terms of the existing constructs.
Show how you would give such definition, in the form of a construct if TEST then CMD of type CMD (cf. page 23 of Lecture 6), and motivate your answer.
Hint: for simplicity in your definition you may assume an extended grammar for TEST, including the boolean conjunction of tests and the check of whether a variable has value 0.
TEST::= X ̸= Y|X = 0|TEST&TEST
It is worth observing that this extension is pure syntactic sugar: just as the if …then construct, also these extra tests can be defined as macros from the primitive language.
Idea of the solution: Define if TEST then CMD as
V := 0; while TEST & (V = 0) do (begin CMD; V := s(V) end)
When the program first reaches the loop, V = 0 always succeeds; whether the loop starts depends solely on whether TEST succeeds. If CMD runs, we increase the contents of V, which means that V = 0 always fails; the program will not execute CMD a second time.
Note in particular that we can still use this if …then inside CMD, because whatever V becomes while executing CMD, the line V := s(V)
Answers Not to be printed
makes sure that V is not zero. We should, however, make sure that the program does not rely on V as a variable to store anything else, because any if …then will destroy its contents.
Answers Not to be printed
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com