Llista de problemes 3

Intruccions

Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:

Vídeos de G. Godoy

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

Llibres

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

Cases, Rafel, i Lluís Màrquez. 2003. Llenguatges, gramàtiques i autòmats : curs bàsic. 2a ed. Edicions UPC.

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

Kozen, Dexter. 1997. Automata and computability. Undergraduate texts a computer science. Springer.

Serna, Maria José, Carme Àlvarez, Rafel Cases, i 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.

Els exercicis següents fan servir notació habitual en computabilitat. En particular:

• \mathbf{R} és el conjunt de tots els llenguatges decidibles (també dits recursius).
• \mathbf{RE} és el conjunt de tots els llenguatges semidecidibles (també dits enumerables recursivament).
• \mathbf{coRE} és el conjunt de tots els llenguatges L tals que \overline L\in \mathbf{RE}. \mathbf{coRE} no és el complementari de \mathbf{RE}. De fet, la majoria de llenguatges no són ni a \mathbf{RE} ni a \mathbf{coRE}.

Recordeu que \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}.

Tots els exercicis

Exercici 1 (Màquines de Turing per llenguatges senzills) Descriviu màquines de Turing deterministes que decideixin els llenguatges següents:

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\}

Consell

Per alguns dels llenguatges definits més amunt, podria ser més senzill descriure una màquina de Turing amb dues o més cintes en lloc d’una màquina d’una sola cinta.

Exercici 2 (Models equivalents de màquines de Turing) Un model de càlcul és Turing-complet si pot ser usat per computar qualsevol funció Turing-computable.

1. Argumenteu que tota funció parcial computable amb una màquines de Turing amb k cintes pot ser computada per una màquina de Turing d’una cinta.
2. Argumenteu que tota funció computable en una màquina de Turing indeterminista pot ser computada per una màquina de Turing determinista.
3. Considereu la variació següent dels PDAs: un que té dues piles en lloc de només una. Aleshores, les transicions depenen de l’estat actual i del símbol del cim de cada pila. A cada pas, l’autòmat pot eliminar el cim de cada pila o empilar nous símbols en cadascuna. Una màquina com aquesta es pot utilitzar per computar funcions: a l’inici de la computació, una de les piles conté l’entrada; al final, la sortida és en una de les piles. Argumenteu que tota funció Turing-computable és computable amb aquesta versió de dues piles dels PDAs.
4. Considereu la variació següent dels PDAs: un que té una cua en lloc d’una pila. Les transicions depenen de l’estat actual i del primer element de la cua. A cada pas, el primer element de la cua es pot esborrar i es poden encuar nous elements al final. Una màquina com aquesta es pot utilitzar per computar funcions: a l’inici de la computació, la cua conté l’entrada; al final, la sortida és a la cua. Argumenteu que tota funció Turing-computable és computable amb aquesta versió de cua dels PDAs.

Consell

Per mostrar que un cert model de càlcul és Turing-complet, n’hi ha prou a descriure la simulació del comportament d’una màquina de Turing. Per aquest exercici, no cal donar una descripció gaire detallada de les simulacions. Només la idea general és suficient.

Funcions computables

Recordeu que una funció parcial f : \mathbb N^k \to \mathbb N és (Turing-)computable si existeix una màquina de Turing M_f t.q.

• si f(x_1,\dots,x_k) està definida, llavors, amb entrada (x_1,\dots,x_k) la màquina M_f s’atura i el valor f(x_1,\dots,x_k) està escrit en la memòria;
• si f(x_1,\dots,x_k) no està definida, la màquina M_f no s’atura amb entrada (x_1,\dots,x_k).

Exercici 3 (\mathbf{R}, \mathbf{RE} i \mathbf{coRE} són tancades per unió, intersecció i revessat) L’objectiu d’aquest exercici és demostrar algunes propietats de tancament de \mathbf{R}, \mathbf{RE} i \mathbf{coRE}.

Nota

Recordeu que una classe \cal C de llenguatges és tancada per una operació binària \circ (per exemple, la unió o la intersecció) si per a tot A,B\in {\cal C}, es compleix que A \circ B \in {\cal C}. Similarment, \cal C és tancada per una operació unària \circ (per exemple, el complementari o el revessat) si per a tot A \in {\cal C}, es compleix que \circ A \in {\cal C}.

1. Unió. Demostreu les propietats següents:

   1. \mathbf{R} és tancada per unió.
   2. \mathbf{RE} és tancada per unió.
   3. \mathbf{coRE} és tancada per unió.

2. Intersecció. Demostreu les propietats següents:

   1. \mathbf{R} és tancada per intersecció.
   2. \mathbf{RE} és tancada per intersecció.
   3. \mathbf{coRE} és tancada per intersecció.
      

3. Diferència de conjunts. Demostreu la propietat següent:

   1. \mathbf{R} és tancada per la diferència de conjunts.

4. Revessat. Demostreu les propietats següents:

   1. \mathbf{R} és tancada pel revessat.
   2. \mathbf{RE} és tancada pel revessat.
   3. \mathbf{coRE} és tancada pel revessat.

Exercici 4 (Altres propietats de tancament de \mathbf{R}, \mathbf{RE} i \mathbf{coRE}) L’objectiu d’aquest exercici és veure com es comporten les classes \mathbf{R}, \mathbf{RE} i \mathbf{coRE} respecte de la complementació, la concatenació, l’estrella de Kleene i el shift.

Nota

Recordeu també que una classe \cal C de llenguatges és tancada per una operació binària \circ (per exemple, la unió o la intersecció) si per a tot A,B\in {\cal C}, es compleix que A \circ B \in {\cal C}. Similarment, \cal C és tancada per una operació unària \circ (per exemple, el complementari o el revessat) si per a tot A \in {\cal C}, es compleix que \circ A \in {\cal C}.

1. Complementari.

   1. Demostreu que \mathbf{R} és tancada per complementació.
   2. Demostreu que si A\in \mathbf{RE}, llavors \overline A\in \mathbf{coRE}.
   3. Demostreu que si A\in \mathbf{coRE}, llavors \overline A\in \mathbf{RE}.

2. Concatenació.

   1. Demostreu que \mathbf{R} és tancada per concatenació.
   2. Demostreu que \mathbf{RE} és tancada per concatenació.
   3. És \mathbf{coRE} tancada per concatenació?

3. Estrella de Kleene.

   1. Demostreu que \mathbf{R} és tancada per l’estrella de Kleene.
   2. Demostreu que \mathbf{RE} és tancada per l’estrella de Kleene.
   3. És \mathbf{coRE} tancada per l’estrella de Kleene?

4. Desplaçament (vegeu la Tasca 1).

   1. Demostreu que \mathbf{R} és tancada per desplaçament.
   2. Demostreu que \mathbf{RE} és tancada per desplaçament.
   3. És \mathbf{coRE} tancada per desplaçament?

Exercici 5 (\mathbf{R}, \mathbf{RE} i \mathbf{coRE}, i els homomorfismes) L’objectiu d’aquest exercici és investigar com es comporten les classes \mathbf{R}, \mathbf{RE} i \mathbf{coRE} per homomorfisme i homomorfisme invers.

Nota

Recordeu també que una classe de llenguatges \cal C és tancada per homomorfisme si per tot llenguatge A \in {\cal C} i homomorfisme \sigma, \sigma(A) \in {\cal C}. També, {\cal C} és tancada per homomorfisme invers si per tot llenguatge A \in {\cal C} i homomorfisme \sigma, \sigma^{-1}(A) \in {\cal C}.

1. Homomorfisme.

   1. Demostreu que \mathbf{R} no és tancada per homomorfisme.
   2. Demostreu que \mathbf{RE} és tancada per homomorfisme.
   3. És \mathbf{coRE} tancada per homomorfisme?

2. Homomorfisme invers.

   1. Demostreu que \mathbf{R} és tancada per homomorfisme invers.
   2. Demostreu que \mathbf{RE} és tancada per homomorfisme invers.
   3. És \mathbf{coRE} tancada per homomorfisme invers?

Exercici 6 (Alguns llenguatges a \mathbf{RE}) Demostreu que els llenguatges següents pertanyen a \mathbf{RE}:

1. \{\langle x,y\rangle \mid M_x(y)\downarrow\}. En altres paraules, aquest és el llenguatge de tots els parells on el primer component x és el nombre de Gödel d’una màquina de Turing M_x i la màquina s’atura quan se li dona com a entrada el segon component y.
2. \{x \mid \exists y\ M_x(y)\downarrow\}. En altres paraules, aquest és el llenguatge de tots els x tals que x és el nombre de Gödel d’una màquina de Turing M_x que s’atura en alguna entrada.
3. \{\langle u,v,R\rangle \mid u\to^* v\}. En altres paraules, aquest és el llenguatge de totes les triples on el primer i el segon components u,v codifiquen mots, el tercer component codifica un conjunt de regles de producció R i el mot v és derivable a partir de u aplicant les regles de R.
4. \{G\in \mathtt{CFG} \mid G \text{ és ambigua}\}. En altres paraules, aquest és el llenguatge de totes les gramàtiques incontextuals ambigües.
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\}. En altres paraules, aquest és el llenguatge de tots els parells de gramàtiques incontextuals amb intersecció no buida (és a dir, que generen algun mot en comú).

Exercici 7 (\mathbf{R}, \mathbf{RE}, \mathbf{coRE} i la diferència simètrica) Donats dos conjunts A i B, recordeu que la diferència simètrica de A i B és A\Delta B=(A\cup B)\setminus (A\cap B). Suposeu que A\Delta B\in \mathbf{R}.

1. Si A\in \mathbf{R}, es compleix que B\in \mathbf{R}?
2. Si A\in \mathbf{RE}, es compleix que B\in \mathbf{RE}?
3. Si A\in \mathbf{coRE}, es compleix que B\in \mathbf{coRE}?

Exercici 8 (Characteritzacions de \mathbf{R} i \mathbf{RE}) Sigui S un llenguatge infinit.

1. S\in \mathbf{RE} si i només si existeix una funció computable, total i injectiva f tal que \mathrm{Im}(f)=S.
2. S\in \mathbf{R} si i només si existeix una funció computable, total i injectiva f que és monòtona creixent i tal que \mathrm{Im}(f)=S.
3. S\in \mathbf{R} si i només si la funció característica de S, \chi_S, és computable.

Nota

Recordeu que, donada una funció f, \mathrm{Im}(f) és la imatge de f, és a dir, \mathrm{Im}(f)=\{y \mid \exists x\ y=f(x)\}. La funció característica d’un conjunt S és la funció booleana \chi_S tal que \chi_S(x)=1 si i només si x\in S.

Exercici 9 (Projecció de \mathbf{RE}) Sigui A\in \mathbf{RE}. Demostreu que \{x\mid \exists y\ \langle x,y\rangle\in A\}\in \mathbf{RE}\ .

Exercici 10 (Funcions computables)  

1. Sigui f una funció injectiva i computable. És f^{-1} una funció injectiva i computable?
2. Sigui f : \mathbb N\to \mathbb N una funció estrictament decreixent. És f computable?

Exercici 11 (Classificació — propietats bàsiques de les màquines de Turing) Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o 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{ si i només si } M_q(z)\!\uparrow)\}
6. \{\langle p,q\rangle \mid \forall z\ (M_p(z)\!\downarrow \text{ si i només si } M_q(z)\!\uparrow)\}

Exercici 12 (Classificació — llenguatges computables) Per a un nombre p, definim \mathcal L_p = \{x \mid M_p(x)\!\downarrow \text{ i accepta}\}. Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o L \notin \mathbf{RE} \cup \mathbf{coRE}.

1. \{p \mid \mathcal L_p \text{ és finit}\}
   
2. \{p \mid \mathcal L_p \text{ és infinit}\}
   
3. \{p \mid \mathcal L_p \text{ és incontextual}\}
   
4. \{p \mid \mathcal L_p \text{ no és incontextual}\}

Exercici 13 (Classificació — domini de les funcions computables)  

Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o 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\} (resoldre aquest exercici de RACSO pot donar algunes pistes)
   
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}\}

Exercici 14 (Classificació — imatge de les funcions computables)  

Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o 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\} (resoldre aquest exercici de RACSO pot donar algunes pistes)
   
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\}

Exercici 15 (Classificació — propietats de les funcions computables)  

Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o L \notin \mathbf{RE} \cup \mathbf{coRE}.

1. \{p \mid \varphi_p \text{ és injectiva}\}
   
2. \{p \mid \varphi_p \text{ és total i injectiva}\} (resoldre aquest exercici de RACSO pot donar algunes pistes)
   
3. \{p \mid \varphi_p \text{ és sobrejectiva}\}
   
4. \{p \mid \varphi_p \text{ és total i sobrejectiva}\}
5. \{p \mid \varphi_p \text{ és creixent}\}
   
6. \{p \mid \varphi_p \text{ és total i creixent}\}
   
7. \{p \mid \varphi_p \text{ és estrictament decreixent}\}
   
8. \{p \mid \varphi_p \text{ és total i estrictament decreixent}\}
   
9. \{p \mid \forall y > p\ \varphi_y \text{ és bijectiva}\}
   
10. \{p \mid \forall y < p\ \varphi_y \text{ és bijectiva}\}
    
11. \{p \mid \exists y > p\ \varphi_y \text{ és bijectiva}\}
    
12. \{p \mid \exists y < p\ \varphi_y \text{ és bijectiva}\}

Exercici 16 (Classification VI — variations on K)  

Per a cada un dels següents llenguatges L, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R}, o 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}

Nota

Recordeu que
K = \{ n \mid M_n(n)\!\downarrow \}\ ,
on M_n és la màquina de Turing amb nombre de Gödel n i \downarrow indica que s’atura.

Exercici 17 (Sobre la imatge dels conjunts decidibles)  

1. Demostreu que si C \in \mathbf{RE} i f és una funció computable, aleshores f(C) \in \mathbf{RE}.
   
2. Demostreu que la frase anterior no és certa si substituïm \mathbf{RE} per \mathbf{R}. És a dir, demostreu que existeix un conjunt C \in \mathbf{R} i una funció computable f tal que f(C) \notin \mathbf{R}.
   
3. Demostreu que existeix un conjunt C \in \mathbf{R} i una funció computable total f tals que f(C) \notin \mathbf{R}.

Exercici 18 (Són computables?)  

Per a cadascuna de les següents funcions f, determineu si f és computable, si \mathrm{Dom}(f)=\mathbb{N} (és a dir, si f és total), i quina és \mathrm{Im}(f):

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

Exercici 19 (Són funcions (computables)?)  

Un conjunt S \subseteq \mathbb{N} \times \mathbb{N} s’identifica amb el graf d’una funció (parcial) si sempre que (x,y) \in S i (x,z) \in S, es compleix que y = z. Quins dels subconjunts següents de \mathbb{N} \times \mathbb{N} són el graf d’una funció? Són les funcions computables?

Una relació \mathcal R sobre \mathbb{N} (és a dir, un conjunt \mathcal R \subseteq \mathbb{N} \times \mathbb{N}) és una funció (parcial) si sempre que (x,y)\in \mathcal R i (x,z)\in \mathcal R, es compleix y=z. Quines de les relacions següents sobre \mathbb{N} són funcions? Són les funcions computables?

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{ s'atura en } y \text{ passos o més}\}.
   
6. \{ (x,y) \mid M_x(x) \text{ s'atura en exactament } y \text{ passos}\}.
   
7. \{ (x,y) \mid M_x(x)\!\downarrow\} \cup \{ (x,y) \mid M_x(x)\!\uparrow\}.
   
8. \{ (x,y) \mid M_x(x)\!\downarrow\}.
   
9. \{ (x,y) \mid M_x(x)\!\uparrow\}.
   
10. \{ (x,y) \mid y = \lvert\{z \mid M_x(z)\!\downarrow\}\rvert\}.