Solved–Assignment 3– Solution

Description

1. (10pt) Consider the alphabet = fa; b; cg and de ne the function succ : ! , succ(w) is the word immediately following w in lexicographic order. Construct a deterministic Turing machine M that computes the function succ, that is, M starts with the initial con guration (s; w) and halts with the con guration (h; succ(w)). Describe M in details using a directed graph whose edges are labelled by transitions (such as the one in Example 17.2, p. 268 of textbook).

Solution:

2. (10pt) Construct a deterministic Turing machine M that adds one to its binary input if it is even and subtracts one if it is odd. M starts with the initial con guration (s; w), where w 2 f0; 1g ; the binary input w is interpreted as an integer number. Possible leading 0’s have to be removed as well. The machine halts in the appropriate con guration (h; (w 1)(2)), where w(2) is the binary representation of w.

Here are some examples of M’s behaviour:

(s; ) ‘ (h; 1)

(s; 000) ‘ (h; 1) (s; 01) ‘ (h; 0) (s; 111) ‘ (h; 110)
(s; 001100) ‘ (h; 1101)

Describe M using the macro language (such as the one in Example 17.8, p. 275 of textbook). Solution:

>R ❑ 1L h
0
1 ❑R ❑ 1L

0 1
R❑L 0 1L❑

1

0L❑

3. (20pt) Construct a Turing Machine M that semidecides, but does not decide, each of the following languages over the alphabet = fa; bg:
(a) L1 = fag,

(b) L2= ,

(c) L3=;.

1

In each case, describe M using the macro language.

Solution:

(a) The machine accepts a and loops for any other input:
>R a R ❑ y

b,❑ a,b

R

(b) This is impossible. A machine semideciding would accept everything, thus deciding .

(c) The machine always loops, accepting nothing:

>R

4. (20pt) Describe in clear English a Turing machine that semidecides the language

L = f< M >j M accepts the binary encodings of at least 3 prime numbersg :

Solution:

TM that semidecides L:

1. Generate all binary encodings of natural numbers in lexicographical order.

2. For each number, check if it is prime and keep the primes only.

3. On input , run M on all primes in dovetailing mode.

4. If three computations accept, then accept.

5. (20pt) Is the set SD closed under:

(a) Intersection?

(b) Concatenation?

Prove your answers. Clear English description of any Turing machines is su cient. (That is, you don’t have to e ectively build the machine, instead explain how the machine behaves.)

Solution:

(a) SD is closed under intersection. To prove this, assume L1; L2 2 SD are arbitrary semidecidable languages and assume they are semidecided by M1 and M2, resp. We construct M\ that semidecides L1 \ L2 as follows:
On input w
Run M1 on w
If M1 rejects, then reject
If M1 accepts, then
Run M2 on w
If M2 rejects, then reject
If M2 accepts, then accept

Another solution for M\:

On input w

2

Run in parallel M1 on w and M2 on w

If both accept, then accept

(b) SD is closed under concatenation. To prove this, assume L1; L2 2 SD are arbitrary semide-cidable languages and assume they are semidecided by M1 and M2, resp. We construct Mc that semidecides L1L2 as follows:

On input w

Run in parallel, in dovetailing mode:

For each w = w1w2; w1; w2 2
Run M1 on w1 and M2 on w2

If both accepts, then accept

Another solution for Mc:

On input w

Nondeterministically guess a factorization w = w1w2; w1; w2 2
Run in parallel M1 on w1 and M2 on w2

If both accepts, then accept

6. (20pt) Let L1 and L2 be two languages that are not decidable.

(a) Is it possible that L1 L2 is regular and L1 L2 6= ;? Prove your answer.

(b) Is it possible that L1 [ L2 is decidable but L1 6= :L2? Prove your answer.

Solution:

(a) Yes. Consider TM ML that always loops. Then 62Hany. Choose L1 = Hany [fg, L2 = Hany. Since Hany is not decidable, L1 and L2 are also not decidable. But L1 L2 = f< ML>g is nite, hence regular; and nonempty.
(b) Yes. Choose L1 = Hany [ fg, L2 = :Hany. Then L1 [ L2 = fj M is a TMg is

decidable but L1 6= :L2.

Note Submit your solution as a (typed) pdf le on owl.uwo.ca.

3