Ejercicios para la evaluación continua

Tema 7: Indecidibilitat, no semidecidibilitat, no computabilitat

Leyenda

= el ejercicio ha sido asignado a un/una estudiante/a y será resuelto en clase.
Para ver la asignación (y la fecha de entrega) consulta el racó.

Ejercicio 1 Clasifica como decidibles, no decidibles pero semidecidibles, o no semidecidibles, los siguientes conjuntos.

  1. \{p\ \mid\ {\mathcal L}_p\text{ es finito}\}.
  2. \{p\ \mid\ {\mathcal L}_p\text{ es infinito}\}.
  3. \{p\ \mid\ M_p(p)=p\}.
  4. \{p\ \mid\ \exists y:M_y(p)=p\}.
  5. \{p\ \mid\ |\mathtt{Dom}(\varphi_p)|\geq 10\}.
  6. \{p\ \mid\ |\mathtt{Dom}(\varphi_p)|\geq 0\}.
  7. \{p\ \mid\ |\mathtt{Im}(\varphi_p)|\geq 10\}.
  8. \{p\ \mid\ |\mathtt{Im}(\varphi_p)|\geq 0\}.
  9. \{p\ \mid\ |\mathtt{Im}(\varphi_p)|<|\mathtt{Dom}(\varphi_p)|<\infty\}.
  10. \{p\ \mid\ |\mathtt{Dom}(\varphi_p)|<|\mathtt{Im}(\varphi_p)|<\infty\}.
  11. \{p\ \mid\ \varphi_p\text{ es inyectiva y total}\}.
  12. \{p\ \mid\ \varphi_p\text{ es exhaustiva y total}\}.
  13. \{p\ \mid\ \varphi_p\text{ es creciente y total}\}.
  14. \{p\ \mid\ \varphi_p\text{ es total y estríctamente decreciente}\}.
  15. \{p\ \mid\ \varphi_p\text{ es inyectiva parcial}\}.
  16. \{p\ \mid\ \varphi_p\text{ es exhaustiva parcial}\}.
  17. \{p\ \mid\ \varphi_p\text{ es creciente parcial}\}.
  18. \{p\ \mid\ \varphi_p\text{ es estríctamente decreciente parcial}\}.

Ejercicio 2 Clasifica como decidibles, no decidibles pero semidecidibles, o no semidecidibles, los siguientes conjuntos.

  1. \{\langle p,q\rangle\ \mid\ \forall z:((M_p(z)\downarrow\wedge M_q(z)\uparrow)\vee (M_p(z)\uparrow\wedge M_q(z)\downarrow)) \}.
  2. \{\langle p,z\rangle\ \mid\ \exists y:M_p(y)=z\}.
  3. \{\langle p,z\rangle\ \mid\ \exists y:M_p(y)\not=z\}.
  4. \{p\ \mid\ {\mathcal L}_p\text{ es incontextual}\}.
  5. \{p\ \mid\ {\mathcal L}_p\text{ no es incontextual}\}.
  6. \{p\ \mid\ \mathtt{Dom}(\varphi_p)\in\mathtt{Dec}\}.
  7. \{p\ \mid\ \mathtt{Dom}(\varphi_p)\not\in\mathtt{Dec}\}.
  8. \{p\ \mid\ \mathtt{Dom}(\varphi_p)\not\in\mathtt{semi-Dec}\}.
  9. \{p\ \mid\ \mathtt{Im}(\varphi_p)\in\mathtt{Dec}\}.
  10. \{p\ \mid\ \mathtt{Im}(\varphi_p)\not\in\mathtt{Dec}\}.
  11. \{p\ \mid\ \mathtt{Im}(\varphi_p)\in\mathtt{semi-Dec}\}.
  12. \{p\ \mid\ \mathtt{Im}(\varphi_p)\not\in\mathtt{semi-Dec}\}.
  13. \{p\ \mid\ p\leq 100\wedge\mathtt{Dom}(\varphi_p)\in\mathtt{Dec}\}.
  14. \{p\ \mid\ p\geq 100\wedge\mathtt{Dom}(\varphi_p)\in\mathtt{semi-Dec}\}.
  15. \{p\ \mid\ \forall y>p:\varphi_y\text{ es biyectiva}\}.
  16. \{p\ \mid\ \forall y<p:\varphi_y\text{ es biyectiva}\}.
  17. \{p\ \mid\ \exists y>p:\varphi_y\text{ es biyectiva}\}.
  18. \{p\ \mid\ \exists y<p:\varphi_y\text{ es biyectiva}\}.
  19. \{p\ \mid\ \exists y:\mathtt{Dom}(\varphi_p)\subseteq\mathtt{Dom}(\varphi_y)\}.
  20. \{p\ \mid\ \exists y:\mathtt{Dom}(\varphi_p)\supseteq\mathtt{Dom}(\varphi_y)\}.
  21. \{p\ \mid\ \mathtt{Dom}(\varphi_p)\subseteq\dot{2}\}.
  22. \{p\ \mid\ \mathtt{Dom}(\varphi_p)\supseteq\dot{2}\}.

Ejercicio 3 Clasifica como decidibles, no decidibles pero semidecidibles, o no semidecidibles, los siguientes conjuntos.

  1. K\times K.
  2. \bar{K}\times K.
  3. \bar{K}\times \bar{K}.
  4. \overline{\bar{K}\times K}.
  5. \{x\;|\;\text{ el decimal $3$ aparece $x$ veces en el número $\pi$}\}.
  6. \{\langle x,y\rangle\;|\;0\leq x\leq 9\;\wedge \text{ el decimal $x$ aparece $y$ veces consecutivas en la secuencia de decimales del número $\pi$}\}.

Ejercicio 4 Demuestra que K no se puede reducir a \bar{K}.

Ejercicio 5 Demuestra que puede ocurrir que C sea decidible, f computable, y sin embargo f(C) no sea decidible.

Ejercicio 6 Demuestra que puede ocurrir que C sea decidible, f computable y total, y sin embargo f(C) no sea decidible.

Ejercicio 7 Demuestra que si C es semidecidible y f es computable, entonces f(C) es semidecidible.

Ejercicio 8 Para cada una de las siguientes funciones indica si son computables, totales y cuál es su imagen.

  1. \displaystyle f(x)= \left\{\begin{array}{rcl} 1&\ \ \ & \text{si }\exists n:M_n(x)\downarrow\\ \uparrow&\ \ \ & \text{otherwise}\\ \end{array}\right.

  2. \displaystyle f(x)= \left\{\begin{array}{rcl} 1&\ \ \ & \text{si }\forall n:M_n(x)\downarrow\\ \uparrow&\ \ \ & \text{otherwise}\\ \end{array}\right.

  3. \displaystyle f(x)= \left\{\begin{array}{rcl} 1&\ \ \ & \text{si }\exists n:M_x(n)\downarrow\\ \uparrow&\ \ \ & \text{otherwise}\\ \end{array}\right.

  4. \displaystyle f(x)= \left\{\begin{array}{rcl} 1&\ \ \ & \text{si }\forall n:M_x(n)\downarrow\\ \uparrow&\ \ \ & \text{otherwise}\\ \end{array}\right.

Ejercicio 9 La función característica de un conjunto C se define como:

\chi_C(x)= \left\{\begin{array}{rcl} 1&\ \ \ & \text{si }x\in C\\ 0&\ \ \ & \text{si }x\not\in C\\ \end{array}\right.

Demuestra que C es decidible si y solo si su función característica \chi_C es computable.

Ejercicio 10 Justifica si los siguientes conjuntos de parejas son funciones, y si son funciones computables.

  1. \varphi_3.
  2. \{\langle x,y\rangle\ \mid\ M_x(x)=y\}.
  3. \{\langle x,y\rangle\ \mid\ M_x(x)\leq y\}.
  4. \{\langle x,y\rangle\ \mid\ M_x(x)\geq y\}.
  5. \{\langle x,y\rangle\ \mid\ M_x(x)=M_y(y)\}.
  6. \{\langle x,y\rangle\ \mid\ M_x(x)\text{ para en $y$ pasos o más}\}.
  7. \{\langle x,y\rangle\ \mid\ M_x(x)\text{ para en exactamente $y$ pasos}\}.
  8. \{\langle x,1\rangle\ \mid\ M_x(x)\downarrow\}\cup\{\langle x,0\rangle\ \mid\ M_x(x)\uparrow\}.
  9. \{\langle x,1\rangle\ \mid\ M_x(x)\downarrow\}.
  10. \{\langle x,0\rangle\ \mid\ M_x(x)\uparrow\}.
  11. \{\langle x,y\rangle\ \mid\ y=|\{z|M_x(z)\downarrow\}|\}.