Decidir si el siguiente conjunto es i) p.r, ii) c.e. y co-c.e. iii) sólo c.e., iv) sólo co-c.e. o v) ni c.e. ni co-c.e.
\(A = \{ \langle x,y \rangle\) tal que \(P\) no tiene ni etiquetas ni pseudoinstrucciones y \(\Phi_x (y) = long(P) \}\) con \(x = \sharp P\)
Ejercicio 2.
Decidir si el siguiente conjunto es i) p.r, ii) c.e. y co-c.e. iii) sólo c.e., iv) sólo co-c.e. o v) ni c.e. ni co-c.e.
\(A = \{ \langle x,{\langle y,z \rangle} \rangle\) tal que \(\Phi_x (y) \uparrow \vee\ \Phi_x (y) = z \}\)
Ejercicio 3.
Decidir si cada una de las siguientes afirmaciones es verdadera o falsa (justificar o dar demostración):
i) Si \(A\) es un conjunto no computable, entonces \(\exists B \subset A\) no computable.
ii) Si \(A\) es un conjunto no computable, entonces \(\exists B \supset A\) no computable.
Ejercicio 4.
Decidir si el siguiente conjunto es i) p.r, ii) c.e. y co-c.e. iii) sólo c.e., iv) sólo co-c.e. o v) ni c.e. ni co-c.e.
\(B = \{ x \in \mathbb{N}\) tal que \(\forall n \in \mathbb{N}\), \(( \exists k_1 \neq k_2 \in \mathbb{N}\) tal que \(\Phi_x (k_1) = \Phi_x (k_2) = n) \}\)
Veamos que no es computable.
Supongo que si lo es; entonces en particular podría computar \(A_0\) (el subconjunto de \(A\) con \(y = z = 0\)).
Veamos que \(A_0\) es un conjunto de índices no trivial.
Sean \(x_0\) e \(y_0\) tales que \(x_0 \in A_0\) y \(\Phi_{x_0} = \Phi_{y_0}.\)
Por lo tanto \(\Phi_{y_0} (0) = \uparrow\) o \(\Phi_{y_0} (0)\) = 0 ya que \(x_0 \in A_0\)
Luego, \(A_0\) es un conjunto de índices. Es inmediato ver que no es trivial (el programa constantemente cero está, y el constantemente 1 no)
Por lo tanto, por el teorema de Rice, \(A_0\) no es computable. Abs!
Por lo tanto \(A\) no computable (ni p.r.)
Para ver que es co-c.e. podemos armar un predicado con STP y SNAP que "decide" la pertenencia al complemento de \(A\)