CS 154 Introduction to Automata and Complexity Theory Handout 18

Winter 1996  R. van Glabbeek  February 28, 1996

Problem Set 7 Date Due: March 6, 1996

Reading: Floyd and Beigel, Chapter 0-8, to be read by Wednesday March 6’th.

Homework: Do the following exercises (FB refers to Floyd and Beigel The Language of Machines). Each problem must be submitted on a separate sheet. The homeworks must be solved without any collaboration. You are, naturally, more that welcome to discuss anything other than than solutions to the homeworks with others. In response to student requests, we will accept solutions to extra credit problems (only) at any time prior to their solutions being handed out.

1. (10 points) 7.1-3 (c) (page 450). Your simulation does NOT have to be in lockstep. Be sure to give an informal description of your idea before you get rigorous.

2. (10 points) 7.6-3 (page 476).

3. (10 points) 7.6-9 (page 477).

4. (15 points) 7.8-2 (page 483).

5. (15 points) 7.9-3 (page 498). Let K_{P Q} = {(P, Q) : P and Q encode equivalent DTA }. Show furthermore, as parts (c) and (d) of this question

(c) K_{inatt} ≤ K_{P Q}.

(d) K_{P Q} ≰ K_{inatt}

6. (10 points) A linearly bounded automaton (lba) is a deterministic 1-tape Turing machine whose head is not permitted to move off the input portion of the tape (except to read one blank symbol past the right hand end of the input so that it can detect where the input ends). Let K_{lba} = {⟨M, w⟩ : M is an lba accepting W }.

(a) Let the length of an input word w be n , that is, |w| = n, assume a given lba has k states, and alphabet Σ of m letters, that is, w is composed by letters from Σ, and lba only prints characters from Σ. Produce an expression u(n, k, m) in n, k and m that is an upper bound (even very coarse) such that if the lba runs for more than u(n, k, m) steps, then it will run forever. Prove your answer.

(b) Use the answer from (a) to settle the question: Is K_{lba} recursive?

(Over for extra credit and chapter summary)

Extra credit (optional) 1. 6.1-2 (e) (page 405).

2. 7.6-4 (page 476).

3. Let A be an r.e. language consisting of description of Turing machines, {⟨M_{1}⟩, ⟨M_{2}⟩, …}. Show that there is a recursive language B consisting of descriptions of Turing machines such that every machine described in A has an equivalent one in B.

4. The subject of this excercise is to define creative sets. These are r.e. sets, whose complements fail to be r.e. in a “strong” sense.

Let W_{x} {def \atop =} \{y : (x, y) ∈ K_{xy}\}.

Let E_{x} {def \atop =} \{z : Turing machine x halts for some input with z on the output tape.\}. A set A is productive if there is a total computable function g such that whenever W_{x} ⊆ A, then g(x) ∈ (A \ W_{x}). The function g is called a productive function for A. A set A is creative if it is r.e. and its complement \overline{A} is productive.

(a) Show that {x : x ∉ W_{x}} is productive.

(b) Show that {x : W_{x} is finite } is productive.

(c) (*) Prove the following theorem: Suppose that A and B are sets such that A is productive, and there is a total computable function f such that x ∈ A iff f(x) ∈ B. Then B is productive. Hint: Use the fact that f^{−1}(W_{x}) ⊆ f^{−1}(B) = A and f^{−1}(W_{x}) is r.e. (i.e., for some z, f^{−1}(W_{x}) = W_{z}).

(d) Prove that if B is r.e. and A ∩ B is productive, then A is productive.

(e) Show that {x : x ∈ E_{x}} is creative.

(f) Prove that if C is a creative set and A is an r.e. set such that A ∩ C = ∅, then

C ∪ A is creative.

Chapter summary Make sure you are familiar with the following concepts when having finished Chapter 7:

• Equivalent notions of computability: 2 stacks, 2 counters, n-stacks, n-counters, RAMS Turing machines.

• The halting problem.

• K_{xy}, K_{inatt}, K_{diag}, …

• Recursive, r.e. and co-r.e. sets.

• Diagonalization.

• Many one reductions (covered in depth in the discussion hour Friday March 1).

• Undecidability of First Order Logic (also to be presented in the discussion hour).