0017 Computational Complexity problem sheet 3.
1. Let L1, L2, . . . , Lk be languages over the same alphabet Σ such that:
(a) For all i ̸= j, Li ∩ Lj = ∅, i.e., no string is in two languages.
(b) L1 ∪L2 ∪···∪Lk = Σ⋆, i.e., every string is in one of the languages.
Copyright By PowCoder代写 加微信 powcoder
(c) Each of the languages Li, for i = 1, 2, . . . , k is recognisable. Prove that each of the languages is therefore decidable.
Solution: By symmetry, if we can prove L1 is decidable, we can prove any of the languages to be decidable. Take TM’s M1, M2, . . . , Mk for each of the languages L1,L2,…,Lk, respectively. Design a TM M with k tapes that accepts L1 and always halts. M copies its input to all the tapes and simulates Mi on the i-th tape. If M1 accepts, then M accepts. If any of the other TM’s accepts, M halts and rejects. Since exactly one of the Mis will accept, M is sure to halt.
Here is another solution that relies on results we have seen earlier. In the previous exercise session, we have shown that if L and L′ are recognisable, then so is L∪L′. Applying this to the above, we find that L2 ∪ · · · ∪ Lk is recognisable. In one of the last lectures, we saw that if L and L− are recognisable, then L is decidable. Since L−1 = L2 ∪ · · · ∪ Lk , and the latter is recognisable, we can conclude that L1 is decidable.
2. Suppose that L is recognisable and its complement L− is not recognis- able. Consider the language
L′ ={0w|w∈L}∪{1w|w̸∈L}
Can you say for certain whether L′ or its complement are decidable,
recognisable or not recognisable? Justify your answer.
Solution: L′ is not recognisable. We prove it by contradiction. Sup- pose L′ were recognisable. Then we could design a TM M recognising L− as follows. Given input w, M changes its input to 1w and simulates the hypothetical TM for L′. If that TM accepts, then w is in L−, so M should accept. If the TM for L′ never accepts, then neither does M. Thus, M would accept exactly L−, which contradicts the fact that L− is not recognisable. We conclude that L′ is not recognisable.
Furthermore, L′− is also not recognisable; we prove it again by con- tradiction. Suppose L′− were recognisable. Then we could design a TM M recognising L′ as follows. Given input w, M rejects if the input is empty. Otherwise, if the input is 0w, we run the hypothetical TM for L′− on 1w. If that TM accepts, then 1w must be in L′−, and hence w must be in L; consequently, 0w must be in L′, and we can accept. Likewise, if the input is 1w, we run the hypothetical TM for
L′− on 0w and accept if that TM accepts. We have now constructed a TM recognising L′, which contradicts our earlier proof that L′ is not recognisable; hence, L′− must also not be recognisable.
All of the above implies of course that neither L′ nor L′− is decidable, because any decidable language is also recognisable.
In the sequel you are asked to choose whether certain language are decidable, recognisable but not decidable or not recognisable. Hint: in order to show that a language is not decidable or not recognisable, you may suppose that it was and show that in that case the halting problem (seen in class) would be decidable.
3. Given the decision problem,
Given a TM M, does it halt on input x within 100 steps? Consider a corresponding language L, which is
L = {code(x)code(M) : TM M halts on x within 100 steps} Choose one of three possibilities
(a) L is decidable.
(b) L is recognisable but not decidable.
(c) L is not recognisable.
Give a proof which justifies your answer.
Solution: Upon input code(x)code(M) we use a Universal Turing Machine to simulate M on input x, but we modify it to (a) keep a count of the number of steps simulated on the tape, (b) accept if the simulation ends before the 100th step is reached and (c) if execution has reached the 100th step without halting, stop and reject. This machine clearly recognises the language and always halts, therefore L is decidable.
4. Given the decision problem,
Given a TM M, does it halt for every input I within 100 steps? Consider a corresponding language L, which is
L = {code(M) : ∀ input x TM M halts on x within 100 steps} Choose one of three possibilities
(a) L is decidable.
(b) L is recognisable but not decidable.
(c) L is not recognisable.
Give a proof which justifies your answer.
Solution: L is decidable.
To show this first we observe the following. Suppose that x is an input string such that |x| = 100. In 100 steps the tape head of a TM can reach the end of x but no further. This means that on input xy (i.e., x followed by another string y) the TM will halt under 100 steps if and only if it halts within 100 steps on input x. In other words, only the first 100 symbols of the input string matter in determining whether a TM will halt on it within 100 steps. Therefore, we can check whether a TM M halts within 100 steps for all inputs by checking whether M halts within 100 steps for all input strings that are up to 100 symbols long, which is a finite set.
Thus the TM that recognises L, given code(M) as input, iterates through the set of strings up to 100 symbols long and for each one it uses the method described in the previous question to find out whether M halts under 100 steps with the current string as input. If M halts under 100 steps for all these strings then code(M) is accepted, otherwise it is rejected.
5. Given the decision problem,
Given a TM M, is there an input x s.t. M halts within |x| steps? Consider a corresponding language L, which is
L = {code(M) : ∃ input x s.t. TM M halts on x within |x| steps} Choose one of three possibilities
(a) L is decidable.
(b) L is recognisable but not decidable.
(c) L is not recognisable.
Give a proof which justifies your answer. Solution: L is recognisable but not decidable.
First, we show that it is recognisable. We build a TM ML with three tapes that works as follows:
(1) on tape 2, write non-deterministically some symbol a from the alphabet then move to the right;
(2) on tape 3, write 1, then move to the right;
(3) non-deterministically, either go to step (1) or (4);
(4) perform a step of M on tape 2; (5) erase the rightmost 1 from tape 3; (6) if M has halted, accept;
(7) otherwise, if tape 3 is empty, loop; (8) otherwise, go to step (4).
If code(M) ∈ L, then there exists x such that M halts on x in |x|
steps. There is therefore a run of ML where we write x on tape 2 and
1…1 on tape 3. Then we simulate M on x, and we know this
will halt in less than |x| steps, so we will finish the computation before having emptied tape 3, and therefore accept code(M). If on the other hand ML terminates on some input code(M), it means that some input word x was written on tape 2, and its length was written in unary on tape 3. It also means that the computation of M on x halted before we ran out of 1s, so in less that |x| steps. This entails that code(M) ∈ L.
To show that L is not decidable we reduce the Halting Problem to it. The reduction works as follows: for a TM M and an input x we produce the TM Mx which first erases the input on the tape and replaces it with the string x and then simulates M on that input. Clearly, Mx either halts or not independently of its input, since it erases it.
If code(Mx) ∈ L then it means that there exists an input J such that Mx halts on J within length(J) steps. But Mx is constructed so that it ignores its input, thus this means that M halts on input x. Similarly, if code(Mx) ∈/ L then there is no input J such that Mx halts on J within length(J) steps. As Mx ignores its input, this must be because M does not halt on input x. Therefore we have reduced HP to L, meaning that L is not decidable.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com