Ejercicios para la evaluación continua
Tema 7: Indecidibilitat, no semidecidibilitat, no computabilitat
Ejercicio 1 Clasifica como decidibles, no decidibles pero semidecidibles, o no semidecidibles, los siguientes conjuntos.
- \{p\ \mid\ {\mathcal L}_p\text{ es finito}\}.
- \{p\ \mid\ {\mathcal L}_p\text{ es infinito}\}.
- \{p\ \mid\ M_p(p)=p\}.
- \{p\ \mid\ \exists y:M_y(p)=p\}.
- \{p\ \mid\ |\mathtt{Dom}(\varphi_p)|\geq 10\}.
- \{p\ \mid\ |\mathtt{Dom}(\varphi_p)|\geq 0\}.
- \{p\ \mid\ |\mathtt{Im}(\varphi_p)|\geq 10\}.
- \{p\ \mid\ |\mathtt{Im}(\varphi_p)|\geq 0\}.
- \{p\ \mid\ |\mathtt{Im}(\varphi_p)|<|\mathtt{Dom}(\varphi_p)|<\infty\}.
- \{p\ \mid\ |\mathtt{Dom}(\varphi_p)|<|\mathtt{Im}(\varphi_p)|<\infty\}.
- \{p\ \mid\ \varphi_p\text{ es inyectiva y total}\}.
- \{p\ \mid\ \varphi_p\text{ es exhaustiva y total}\}.
- \{p\ \mid\ \varphi_p\text{ es creciente y total}\}.
- \{p\ \mid\ \varphi_p\text{ es total y estríctamente decreciente}\}.
- \{p\ \mid\ \varphi_p\text{ es inyectiva parcial}\}.
- \{p\ \mid\ \varphi_p\text{ es exhaustiva parcial}\}.
- \{p\ \mid\ \varphi_p\text{ es creciente parcial}\}.
- \{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.
- \{\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)) \}.
- \{\langle p,z\rangle\ \mid\ \exists y:M_p(y)=z\}.
- \{\langle p,z\rangle\ \mid\ \exists y:M_p(y)\not=z\}.
- \{p\ \mid\ {\mathcal L}_p\text{ es incontextual}\}.
- \{p\ \mid\ {\mathcal L}_p\text{ no es incontextual}\}.
- \{p\ \mid\ \mathtt{Dom}(\varphi_p)\in\mathtt{Dec}\}.
- \{p\ \mid\ \mathtt{Dom}(\varphi_p)\not\in\mathtt{Dec}\}.
- \{p\ \mid\ \mathtt{Dom}(\varphi_p)\not\in\mathtt{semi-Dec}\}.
- \{p\ \mid\ \mathtt{Im}(\varphi_p)\in\mathtt{Dec}\}.
- \{p\ \mid\ \mathtt{Im}(\varphi_p)\not\in\mathtt{Dec}\}.
- \{p\ \mid\ \mathtt{Im}(\varphi_p)\in\mathtt{semi-Dec}\}.
- \{p\ \mid\ \mathtt{Im}(\varphi_p)\not\in\mathtt{semi-Dec}\}.
- \{p\ \mid\ p\leq 100\wedge\mathtt{Dom}(\varphi_p)\in\mathtt{Dec}\}.
- \{p\ \mid\ p\geq 100\wedge\mathtt{Dom}(\varphi_p)\in\mathtt{semi-Dec}\}.
- \{p\ \mid\ \forall y>p:\varphi_y\text{ es biyectiva}\}.
- \{p\ \mid\ \forall y<p:\varphi_y\text{ es biyectiva}\}.
- \{p\ \mid\ \exists y>p:\varphi_y\text{ es biyectiva}\}.
- \{p\ \mid\ \exists y<p:\varphi_y\text{ es biyectiva}\}.
- \{p\ \mid\ \exists y:\mathtt{Dom}(\varphi_p)\subseteq\mathtt{Dom}(\varphi_y)\}.
- \{p\ \mid\ \exists y:\mathtt{Dom}(\varphi_p)\supseteq\mathtt{Dom}(\varphi_y)\}.
- \{p\ \mid\ \mathtt{Dom}(\varphi_p)\subseteq\dot{2}\}.
- \{p\ \mid\ \mathtt{Dom}(\varphi_p)\supseteq\dot{2}\}.
Ejercicio 3 Clasifica como decidibles, no decidibles pero semidecidibles, o no semidecidibles, los siguientes conjuntos.
- K\times K.
- \bar{K}\times K.
- \bar{K}\times \bar{K}.
- \overline{\bar{K}\times K}.
- \{x\;|\;\text{ el decimal $3$ aparece $x$ veces en el número $\pi$}\}.
- \{\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.
\displaystyle f(x)= \left\{\begin{array}{rcl} 1&\ \ \ & \text{si }\exists n:M_n(x)\downarrow\\ \uparrow&\ \ \ & \text{otherwise}\\ \end{array}\right.
\displaystyle f(x)= \left\{\begin{array}{rcl} 1&\ \ \ & \text{si }\forall n:M_n(x)\downarrow\\ \uparrow&\ \ \ & \text{otherwise}\\ \end{array}\right.
\displaystyle f(x)= \left\{\begin{array}{rcl} 1&\ \ \ & \text{si }\exists n:M_x(n)\downarrow\\ \uparrow&\ \ \ & \text{otherwise}\\ \end{array}\right.
\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.
- \varphi_3.
- \{\langle x,y\rangle\ \mid\ M_x(x)=y\}.
- \{\langle x,y\rangle\ \mid\ M_x(x)\leq y\}.
- \{\langle x,y\rangle\ \mid\ M_x(x)\geq y\}.
- \{\langle x,y\rangle\ \mid\ M_x(x)=M_y(y)\}.
- \{\langle x,y\rangle\ \mid\ M_x(x)\text{ para en $y$ pasos o más}\}.
- \{\langle x,y\rangle\ \mid\ M_x(x)\text{ para en exactamente $y$ pasos}\}.
- \{\langle x,1\rangle\ \mid\ M_x(x)\downarrow\}\cup\{\langle x,0\rangle\ \mid\ M_x(x)\uparrow\}.
- \{\langle x,1\rangle\ \mid\ M_x(x)\downarrow\}.
- \{\langle x,0\rangle\ \mid\ M_x(x)\uparrow\}.
- \{\langle x,y\rangle\ \mid\ y=|\{z|M_x(z)\downarrow\}|\}.