Problem Set 3

Instructions

Resources useful to solve the exercises in this problem set are the following:

Guille Godoy’s video lectures

• Maquinas de Turing (1)
• Maquinas de Turing (2)
• Equivalencia TM-programas
• Asumciones sobre TM-programas
• Operaciones sobre TM-programas

Books

• (Sipser 2013, \S 3 and \S 4.1)
• (Hopcroft, Motwani, and Ullman 2007, \S 8)
• (Kozen 1997, Lectures 28-32)
• (Serna et al. 2004, \S 1, 2, 3)

Cases, Rafel, and Lluís Màrquez. 2003. Llenguatges, Gramàtiques i Autòmats : Curs Bàsic. 2a ed. Edicions UPC.

Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Pearson Addison Wesley.

Kozen, Dexter. 1997. Automata and Computability. Undergraduate Texts in Computer Science. Springer.

Serna, Maria José, Carme Àlvarez, Rafel Cases, and Antoni Lozano. 2004. Els Límits de La Computació : Indecidibilitat i NP-Completesa. 2a ed. Edicions UPC.

Sipser, Michael. 2013. Introduction to the Theory of Computation. 3rd edition. Cengage Learning.

The following exercises use common notation in computability, in particular:

• \mathbf{R} is the set of all decidable (aka recursive) languages.
• \mathbf{RE} is the set of all semi-decidable (aka recursively enumerable) languages.
• \mathbf{coRE} the set of all languages L such that \overline L\in \mathbf{RE}. \mathbf{coRE} is not the complement of \mathbf{RE}. Indeed most of the languages are neither in \mathbf{RE} nor in \mathbf{coRE}.

Recall that \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}.

All exercises

Exercise 1 (Turing machines for simple languages) Describe explicitly a (deterministic) Turing machine deciding the following languages:

1. \{a^nb^nc^n \mid n\in \mathbb N\}
2. \{x\# y \mid x,y\in \{0,1\}^* \land \mathrm{value}_2(x)=\mathrm{value}_2(y)+1\}
3. \{ww \mid w\in \{0,1\}^*\}
4. \{a^{2^n} \mid n\in \mathbb N\}
5. \{a^{n^2} \mid n\in \mathbb N\}
6. \{a^{2^n}b^n \mid n\in \mathbb N\}
7. \{w\in \{a,b\}^* \mid |w|_a=|w|_b^2\}

Tip

For some languages above it might be simpler to describe a Turing machine with two or more tapes instead of a 1-tape Turing machine.

Exercise 2 (Equivalent models of Turing machines) A computation model is Turing-complete if it can be used to compute every Turing-computable function.

1. Show that every partial function computable on a Turing machine with k tapes can be computed on a Turing machine with only 1 tape.
2. Show that every partial function computable on a nondeterministic Turing machine can be computed on a deterministic Turing machine.
3. Consider the following variation of PDAs: one that has two stacks instead of just one. Transitions then depend on the current state and on the top symbol of each stack. At each step, the automaton can remove the top element from either stack or push new symbols onto them. Such a machine can be used to compute functions: at the start of the computation, one of the stacks contains the input, and at the end, the output is left on a stack. Show that every Turing-computable function can be computed with this 2-stack version of PDAs.
4. Consider the following variation of PDAs: one that has a queue instead of a stack. Transitions depend on the current state and on the first element of the queue. At each step, the first element of the queue can be removed and new elements can be added at the end. Such a machine can be used to compute functions: at the start of the computation, the queue contains the input, and at the end, the output is left on the queue. Show that every Turing-computable function can be computed with this queue version of PDAs.

Tip

To show that a certain computational model is Turing-complete, it is enough to show how to simulate the behaviour of a Turing machine. For this exercise there is no need to give a very detailed description of the simulations. Just the general idea is enough.

Computable functions

Recall that a partial function f : \mathbb N^k \to \mathbb N is (Turing-)computable if there exists a Turing machine M_f s.t.

• if f(x_1,\dots,x_k) is defined, then, on input (x_1,\dots,x_k) the machine M_f terminates and the value f(x_1,\dots,x_k) is written in the memory;
• if f(x_1,\dots,x_k) is not defined, the machine M_f does not terminate on input (x_1,\dots,x_k).

Exercise 3 (\mathbf{R}, \mathbf{RE}, and \mathbf{coRE} are closed under union, intersection, and reverse) The goal of this exercise is to show some closure properties of \mathbf{R}, \mathbf{RE}, and \mathbf{coRE}.

Note

Recall that a class \cal C of languages is closed under a binary operation \circ (e.g., union or intersection) if, for any A,B\in {\cal C}, it holds that A \circ B \in {\cal C}. Similarly, \cal C is closed under a unary operation \circ (e.g., complement or reverse) if for any A \in {\cal C}, it holds that \circ A \in {\cal C}.

1. Union. Show the following properties:

   1. \mathbf{R} is closed under union.
   2. \mathbf{RE} is closed under union.
   3. \mathbf{coRE} is closed under union.

2. Intersection. Show the following properties:

   1. \mathbf{R} is closed under intersection.
   2. \mathbf{RE} is closed under intersection.
   3. \mathbf{coRE} is closed under intersection.

3. Set subtraction. Show the following property:

   1. \mathbf{R} is closed under set subtraction.

4. Reverse. Show the following properties:

   1. \mathbf{R} is closed under reverse.
   2. \mathbf{RE} is closed under reverse.
   3. \mathbf{coRE} is closed under reverse.

Exercise 4 (Other closure properties of \mathbf{R}, \mathbf{RE}, and \mathbf{coRE}) The goal of this exercise is to see how \mathbf{R}, \mathbf{RE}, and \mathbf{coRE} behave w.r.t. complementation, concatenation, Kleene star, and shift.

Note

Also recall that a class \cal C of languages is closed under a binary operation \circ (e.g., union or concatenation) if, for any A,B\in {\cal C}, it holds that A \circ B \in {\cal C}. Similarly, \cal C is closed under a unary operation \circ (e.g., complement or Kleene star) if for any A \in {\cal C}, it holds that \circ A \in {\cal C}.

1. Complement.

   1. Show that \mathbf{R} is closed under complement.
   2. Show that if A\in \mathbf{RE}, then \overline A\in \mathbf{coRE}.
   3. Show that if A\in \mathbf{coRE}, then \overline A\in \mathbf{RE}.

2. Concatenation.

   1. Show that \mathbf{R} is closed under concatenation.
   2. Show that \mathbf{RE} is closed under concatenation.
   3. Is \mathbf{coRE} closed under concatenation?

3. Kleene star.

   1. Show that \mathbf{R} is closed under Kleen star.
   2. Show that \mathbf{RE} is closed under Kleen star.
   3. Is \mathbf{coRE} closed under Kleene star?

4. Shift (see Problem Set 1).

   1. Show that \mathbf{R} is closed under shift.
   2. Show that \mathbf{RE} is closed under shift.
   3. Is \mathbf{coRE} closed under shift?

Exercise 5 (\mathbf{R}, \mathbf{RE}, and \mathbf{coRE} and homomorphisms) The goal of this exercise is to investigate how \mathbf{R}, \mathbf{RE}, and \mathbf{coRE} behave under homomorphisms and inverse homomorphisms.

Note

Also recall that a class \cal C of languages is closed under homomorphism if for any A \in {\cal C} and homomorphism \sigma, \sigma(A) \in {\cal C}. Also, {\cal C} is closed under inverse homomorphism if for any A \in {\cal C} and homomorphism \sigma, \sigma^{-1}(A) \in {\cal C}.

1. Homomorphism.

   1. Show that \mathbf{R} is not closed under homomorphism.
   2. Show that \mathbf{RE} is closed under homomorphism.
   3. Is \mathbf{coRE} closed under homomorphism?

2. Inverse homomorphism.

   1. Show that \mathbf{R} is closed under inverse homomorphism.
   2. Show that \mathbf{RE} is closed under inverse homomorphism.
   3. Is \mathbf{coRE} closed under inverse homomorhpism?

Exercise 6 (Some languages in \mathbf{RE}) Show that the following languages belong to \mathbf{RE}:

1. \{\langle x,y\rangle \mid M_x(y)\downarrow\}. In other words, this is the language of all pairs where the first entry x is the Gödel-number of a Turing machine M_x, and the machine terminates when given as input the second entry y.
2. \{x \mid \exists y\ M_x(y)\downarrow\}. In other words, this is the language of all x, where x is the Gödel-number of a Turing machine M_x which terminates on some input.
3. \{\langle u,v,R\rangle \mid u\to^* v\}. In other words, this is the language of all triplets where the first and second entries u,v encode words, the third entry a set of production rules R, and the word v is reachable from u using the production rules in R.
4. \{G\in \mathtt{CFG} \mid G \text{ ambiguous}\}. In other words, this is the language of all ambiguous context-free grammars.
5. \{\langle G_1,G_2\rangle \mid G_1,G_2\in \mathtt{CFG} \land \mathcal L(G_1)\cap \mathcal L(G_2)\neq \emptyset\}. In other words, this is the language of all pairs of context-free grammars with nonempty intersection (i.e., that generate some common word).

Exercise 7 (\mathbf{R}, \mathbf{RE}, \mathbf{coRE}, and symmetric difference) Given two sets A and B recall that the symmetric difference of A and B is A\Delta B=(A\cup B)\setminus (A\cap B). Assume that A\Delta B\in \mathbf{R}.

1. Does A\in \mathbf{R} imply that B\in \mathbf{R}?
2. Does A\in \mathbf{RE} imply that B\in \mathbf{RE}?
3. Does A\in \mathbf{coRE} imply that B\in \mathbf{coRE}?

Exercise 8 (Characterizations of \mathbf{R} and \mathbf{RE}) Let S be an infinite language.

1. S\in \mathbf{RE} if and only if there exists an injective total computable function f such that \mathrm{Im}(f)=S.
2. S\in \mathbf{R} if and only if there exists an injective total computable function f that is monotone increasing and such that \mathrm{Im}(f)=S.
3. S\in \mathbb{R} if and only if the indicator function of S, \chi_S, is computable.

Note

Recall that, given a function f, \mathrm{Im}(f) is the image of f, that is, \mathrm{Im}(f)=\{y \mid \exists x\ y=f(x)\}. The indicator function of a set S is the Boolean valued function \chi_S s.t. \chi_S(x)=1 if and only if x\in S.

Exercise 9 (Projection of \mathbf{RE}) Let A\in \mathbf{RE}. Show that \{x\mid \exists y\ \langle x,y\rangle\in A\}\in \mathbf{RE}\ .

Exercise 10 (On computable functions)  

1. Let f be a function injective and computable. Is f^{-1} an injective and computable function?
2. Let f : \mathbb N\to \mathbb N a strictly decreasing function. Is f computable?

Exercise 11 (Classification — basic properties of TMs) For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. \{p \mid M_{p}(p)=p\}
2. \{p \mid \exists y\ M_{y}(p)=p\}
3. \{\langle p,z\rangle \mid \exists y\ M_{p}(y)=z\}
4. \{\langle p,z\rangle \mid \exists y\ M_{p}(y)\neq z\}
5. \{\langle p,q\rangle \mid \forall z\ (M_p(z)\!\uparrow \text{ if and only if } M_q(z)\!\uparrow)\}
6. \{\langle p,q\rangle \mid \forall z\ (M_p(z)\!\downarrow \text{ if and only if } M_q(z)\!\uparrow)\}

Exercise 12 (Classification — computable languages) For a number p, define \mathcal L_p=\{x \mid M_p(x)\!\downarrow \text{and accepts}\}. For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. \{p \mid \mathcal L_p \text{ is finite}\}
2. \{p \mid \mathcal L_p \text{ is infinite}\}
3. \{p \mid \mathcal L_p \text{ is context-free}\}
4. \{p \mid \mathcal L_p \text{ is not context-free}\}

Exercise 13 (Classification — domain of computable functions)  

For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. \{p \mid |\mathrm{Dom}(\varphi_p)|\geq 0\}
2. \{p \mid |\mathrm{Dom}(\varphi_p)|\geq 10\} (solving this RACSO exercise might give some hints)
3. \{p \mid \mathrm{Dom}(\varphi_p)\subseteq 2\mathbb N\}
4. \{p \mid \mathrm{Dom}(\varphi_p)\supseteq 2\mathbb N\}
5. \{p \mid \exists y\ \mathrm{Dom}(\varphi_p)\subseteq \mathrm{Dom}(\varphi_y)\}
6. \{p \mid \exists y\ \mathrm{Dom}(\varphi_p)\supseteq \mathrm{Dom}(\varphi_y)\}
7. \{p \mid \mathrm{Dom}(\varphi_p)\in \mathbf{R}\}
8. \{p \mid \mathrm{Dom}(\varphi_p)\notin \mathbf{R}\}
9. \{p \mid \mathrm{Dom}(\varphi_p)\in \mathbf{RE}\}
10. \{p \mid \mathrm{Dom}(\varphi_p)\notin \mathbf{RE}\}
11. \{p \mid p\leq 100 \land \mathrm{Dom}(\varphi_p)\in \mathbf{R}\}
12. \{p \mid p\leq 100 \land \mathrm{Dom}(\varphi_p)\in \mathbf{RE}\}

Exercise 14 (Classification — image of computable functions)  

For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. \{p \mid |\mathrm{Im}(\varphi_p)|\geq 0\}
2. \{p \mid |\mathrm{Im}(\varphi_p)|\geq 10\} (solving this RACSO exercise might give some hints)
3. \{p \mid \mathrm{Im}(\varphi_p)\subseteq 2\mathbb N\}
4. \{p \mid \mathrm{Im}(\varphi_p)\supseteq 2\mathbb N\}
5. \{p \mid \exists y\ \mathrm{Im}(\varphi_p)\subseteq \mathrm{Im}(\varphi_y)\}
6. \{p \mid \exists y\ \mathrm{Im}(\varphi_p)\supseteq \mathrm{Im}(\varphi_y)\}
7. \{p \mid \mathrm{Im}(\varphi_p)\in \mathbf{R}\}
8. \{p \mid \mathrm{Im}(\varphi_p)\notin \mathbf{R}\}
9. \{p \mid \mathrm{Im}(\varphi_p)\in \mathbf{RE}\}
10. \{p \mid \mathrm{Im}(\varphi_p)\notin \mathbf{RE}\}
11. \{p \mid p\leq 100 \land \mathrm{Im}(\varphi_p)\in \mathbf{R}\}
12. \{p \mid p\leq 100 \land \mathrm{Im}(\varphi_p)\in \mathbf{RE}\}
13. \{p \mid |\mathrm{Im}(\varphi_p)| < |\mathrm{Dom}(\varphi_p)|< \infty\}
14. \{p \mid |\mathrm{Dom}(\varphi_p)| < |\mathrm{Im}(\varphi_p)|< \infty\}

Exercise 15 (Classification — properties of computable functions)  

For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. \{p \mid \varphi_p \text{ is injective}\}
2. \{p \mid \varphi_p \text{ is total and injective}\} (solving this RACSO exercise might give some hints)
3. \{p \mid \varphi_p \text{ is onto}\}
4. \{p \mid \varphi_p \text{ is total and onto}\}
5. \{p \mid \varphi_p \text{ is increasing}\}
6. \{p \mid \varphi_p \text{ is total and increasing}\}
7. \{p \mid \varphi_p \text{ is strictly decreasing}\}
8. \{p \mid \varphi_p \text{ is total and strictly decreasing}\}
9. \{p \mid \forall y > p\ \varphi_y \text{ is bijective}\}
10. \{p \mid \forall y < p\ \varphi_y \text{ is bijective}\}
11. \{p \mid \exists y > p\ \varphi_y \text{ is bijective}\}
12. \{p \mid \exists y < p\ \varphi_y \text{ is bijective}\}

Exercise 16 (Classificació VI — variacions de K)  

For each of the following languages L, decide whether L\in \mathbf{R}, L\in \mathbf{RE}\setminus \mathbf{R}, L\in \mathbf{coRE}\setminus \mathbf{R}, or L\notin \mathbf{RE}\cup \mathbf{coRE}.

1. L=K\times K
2. L=\overline K\times K
3. L=\overline K \times \overline K
4. L=\overline{\overline K \times K}

Note

Recall that K=\{n\mid M_n(n)\!\downarrow\}\ , where M_n is the Turing machine with Gödel number n and the \downarrow means that the machine terminates.

Exercise 17 (On the image of decidable sets)  

1. Show that if C\in \mathbf{RE} and f is a computable function, then f(C)\in \mathbf{RE}.
2. Show that the previous sentence is not true if we substitute \mathbf{RE} for \mathbf{R}. That is, show that there is a set C\in \mathbf{R} and a computable function f such that f(C)\notin \mathbf{R}.
3. Show that there is a set C\in \mathbf{R} and a total computable function f such that f(C)\notin \mathbf{R}.

Exercise 18 (Are they computable?)  

For each of the following functions f, find whether f is computable, \mathrm{Dom}(f)=\mathbb N (i.e. f is total), and what is \mathrm{Im}(f):

1. f(x)=\begin{cases} 1 &\text{if } \exists n\ M_n(x)\!\downarrow\\ \uparrow &\text{otherwise}\end{cases}
2. f(x)=\begin{cases} 1 &\text{if } \forall n\ M_n(x)\!\downarrow\\ \uparrow &\text{otherwise}\end{cases}
3. f(x)=\begin{cases} 1 &\text{if } \exists n\ M_x(n)\!\downarrow\\ \uparrow &\text{otherwise}\end{cases}
4. f(x)=\begin{cases} 1 &\text{if } \forall n\ M_x(n)\!\downarrow\\ \uparrow &\text{otherwise}\end{cases}

Exercise 19 (Are they (computable) functions?)  

A set S\subseteq \mathbb N\times \mathbb N identifies with the graph of a (partial) function if whenever (x,y)\in S and (x,z)\in S, it holds that y=z. Which of the following subsets of \mathbb N\times \mathbb N are the graph of a function? Are the functions computable?

A relation \mathcal R on \mathbb{N} (that is, a set \mathcal R \subseteq \mathbb{N} \times \mathbb{N}) is a (partial) function if whenever (x,y)\in \mathcal R and (x,z)\in \mathcal R, it holds that y=z. Which of the following relations on \mathbb{N} are functions? Are the functions computable?

1. \{ (x,y) \mid M_x(x)=y\}.
2. \{ (x,y) \mid M_x(x)\leq y\}.
3. \{ (x,y) \mid M_x(x)\geq y\}.
4. \{ (x,y) \mid M_x(x)=M_y(y)\}.
5. \{ (x,y) \mid M_x(x) \text{ stops in } y \text{ steps or more}\}.
6. \{ (x,y) \mid M_x(x) \text{ stops in exactly } y \text{ steps}\}.
7. \{ (x,1) \mid M_x(x)\!\downarrow\}\cup \{ (x,0) \mid M_x(x)\!\uparrow\}.
8. \{ (x,1) \mid M_x(x)\!\downarrow\}.
9. \{ (x,0) \mid M_x(x)\!\uparrow\}.
10. \{ (x,y) \mid y= \lvert\{z\mid M_x(z)\!\downarrow\}\rvert\ \}.