Edición de «Práctica 3 (LyC Verano)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 1: Línea 1:
__NOTOC__
= Ejercicios =
{{Back|Lógica y Computabilidad}}
 
== Ejercicio 1 ==
== Ejercicio 1 ==
Sea <math>f: \mathbb{N} \rightarrow \mathbb{N}</math> computable.  
 
Sea f: N -> N computable.  


=== Item A ===
=== Item A ===
Línea 8: Línea 9:
Demostrar que la función
Demostrar que la función


<math> g(x) = \begin{cases} min_y\; f(y) = x & \textrm{si existe } y \textrm{ tal que } f(y) = x \\
g(x) = min {y : f(y) = x}  si existe y tal que f(y) = x
\uparrow & \textrm{si no}
        se cuelga          si no
\end{cases}
</math>


es parcialmente computable.
es parcialmente computable.
Línea 20: Línea 19:


  Z1 <- X1
  Z1 <- X1
  [A] Z3 <- f(Z2)  //Dado que f es computable, supongo que tengo el programa homónimo que la calcula,  
  [A] Z3 <- f(Z2)  //Dado que f es computable, supongo que tengo el progama homónimo que la calcula,  
                   //y además sé que no se cuelga.
                   //y además sé que no se cuelga.
  IF Z3 = Z1 GOTO B
  IF Z3 = Z1 GOTO B
Línea 28: Línea 27:


La idea es sencillamente chequear si f(y) = x, empezando con y = 0 e incrementando de a uno. Si en algún momento esto ocurre, ese y es el que busca la minimización de la primer rama de g. Si no ocurre nunca, el programa sigue incrementando el valor chequeado infinitamente, o sea se cuelga.
La idea es sencillamente chequear si f(y) = x, empezando con y = 0 e incrementando de a uno. Si en algún momento esto ocurre, ese y es el que busca la minimización de la primer rama de g. Si no ocurre nunca, el programa sigue incrementando el valor chequeado infinitamente, o sea se cuelga.


=== Item B ===
=== Item B ===


Demostrar que si f es además biyectiva, <math>f^{-1}</math> es computable.  
Demostrar que si f es además biyectiva, f^-1 es computable.  


'''Solución'''
'''Solución'''


<math>f^{-1}(x) = min_y\; f(y) = x</math>
Notar que el programa que dimos computa f^-1. Como f es biyectiva, es inyectiva. Esto asegura que el resultado de la expresión min{y:f(y) = x} devuelve no sólo el mínimo y, sino el único. Además, la sobreyectividad nos asegura la existencia de tal y, con lo cual el programa no puede colgarse.
 
Notar que el programa que dimos computa <math>f^{-1}</math>. Como f es biyectiva, es inyectiva. Esto asegura que el resultado de la expresión min {y:f(y) = x} devuelve no sólo el mínimo y, sino el único. Además, la sobreyectividad nos asegura la existencia de tal y, con lo cual el programa no puede colgarse.


== Ejercicio 2 ==
== Ejercicio 2 ==


Sea <math>f: \mathbb{N} \rightarrow \mathbb{N}</math> una función computable y sobreyectiva. Probar que existe una función computable e inyectiva <math>g: \mathbb{N} \rightarrow \mathbb{N}</math> tal que <math>g(f(x)) \le x</math> para todo x perteneciente a <math>\mathbb{N}</math>.
Sea f: N -> N una función computable y sobreyectiva. Probar que existe una función computable e inyectiva g: N -> N tal que g(f(x)) <= x para todo x perteneciente a N.


'''Solución'''
'''Solución'''


Es casi el mismo problema que en el ejercicio 1. Podríamos ver a g como una especie de generalización de <math>f^{-1}</math>. Si f es inyectiva y sobreyectiva (i.e. biyectiva) se puede definir una <math>f^{-1}</math> tal que <math>f^{-1}(x) = g(f(x)) = x</math>, para todo x natural.
Es casi el mismo problema que en el ejercicio 1. Podríamos ver a g como una especie de generalización de f^-1. Si f es inyectiva y sobreyectiva (i.e. biyectiva) se puede definir una f^-1 tal que f^-1(x) = g(f(x)) = x, para todo x natural.
 
Si debilitamos la hipótesis sobre f, y sólo pedimos que sea sobreyectiva, pasa a haber más de un <math>x_i</math> tal que <math>g(f(x_i)) = x</math>. Pero siempre habrá un único <math>x_1</math> tal que <math>g(f(x_1)) = x</math> y además <math>x_1</math> es más chico que todos los <math>x_i</math>. Este <math>x_1</math> se encuentra con la minimización:
 
<math>min_y\; f(y) = x</math>
 
Por otra parte, esta minimización es computable, dado que está garantizado por la sobreyectividad de f la existencia de al menos un y que verifique f(y) = x. Nuevamente, esta función se computa con el programa del ejercicio 1, item A. Por último, g es inyectiva porque en la expresión f(y) = x, dos valores <math>x_1</math> y <math>x_2</math> distintos no pueden provenir del mismo y, dado que esto violaría la definición de función.
 
== Ejercicio 3 ==
Sea <math>f: \mathbb{N} \rightarrow \mathbb{N}</math> una función computable biyectiva. Probar que Halt(f(x), x) no es computable. Sugerencia: considerar la función:
 
<math>
h(x) = \begin{cases} 1 & \textrm{si\ } \neg\textrm{HALT}(x, f^-1(x)) \\
\uparrow & \textrm{si no}
\end{cases}
</math>
 
'''Solucion'''
 
El siguiente programa computa h, suponiendo que HALT(f(x),x) sea computable:
 
[A] IF HALT(f(f^-1(x)), f^-1(x)) GOTO A
Y <- 1
 
que es equivalente a:
 
[A] IF HALT(x, f^-1(x)) GOTO A
Y <- 1


Llamemos P a este programa, entonces existe e tal que #(P) = e
Si debilitamos la hipótesis sobre f, y sólo pedimos que sea sobreyectiva, pasa a haber más de un xi tal que g(f(xi)) = x. Pero siempre habrá un único x1 tal que g(f(x1)) = x y además x1 es más chico que todos los xi. Este x1 se encuentra con la minimización:


Ahora bien, por la definición de HALT:
min{y : f(y) = x}


<math>HALT(f(e), e)  \Longleftrightarrow h(f(e)) \downarrow</math>
Por otra parte, esta minimización es computable, dado que está garantizado por la sobreyectividad de f la existencia de al menos un y que verifique f(y) = x. Nuevamente, esta función se computa con el programa del ejercicio 1, item A. Por último, g es inyectiva porque en la expresión f(y) = x, dos valores x1 y x2 distintos no pueden provenir del mismo y, dado que esto violaría la definición de función.
 
Y por la definición de h:
 
<math>h(f(e))\downarrow \;\Longleftrightarrow \neg HALT(f(e), e)</math>
 
Lo que nos lleva a un absurdo, que proviene de la única suposición que hicimos, que es que HALT(f(x), x) es computable.
 
== Ejercicio 4 ==
 
Sean f, g y h las funciones dadas por:
 
<math> f(x) = \begin{cases} \Phi(x,x) + 1 & si\; \Phi(x,x)\downarrow \\
\uparrow & sino
\end{cases}
</math>
 
<math> g(x) = \begin{cases} 1 & \textrm{si\ } x \in Dom(f) \\
\uparrow & sino
\end{cases}
</math>
 
<math> h(x) = \begin{cases} 0 & \textrm{si\ } \Phi(x,x)\downarrow \\
\uparrow & sino
\end{cases}
</math>
 
Probar que son parcialmente computables.
 
'''Solucion'''
 
Para resolver esto es suficiente con dar 3 programas que computen cada una de estas funciones.
 
Este programa computa f:
 
Y <- fi(x,x) + 1
 
Este programa computa g:
 
Z <- f(x)
Y <- 1
 
Y este computa h:
 
Y <- not(g(x))


== Ejercicio 5 ==
== Ejercicio 5 ==
Línea 128: Línea 55:
Probar que la siguiente función es primitiva recursiva:
Probar que la siguiente función es primitiva recursiva:


<math> f(x) = \begin{cases} 1 & \textrm{si\ } x = \langle\langle a,b\rangle ,c\rangle \; y\; \Phi(b,a) \textrm{\ termina\ en\ menos\ de\ c\ pasos} \\
f(x) = 1 si x = <<a,b>,c> y fi(b,a) termina en menos de c pasos
         0 & sino
         0 en otro caso
\end{cases}
</math>


'''Solución'''
'''Solución'''


f(x) es pr porque tanto los valores que devuelve como las funciones utilizadas en las guardas lo son. La decodificación de x en a, b y c es pr. y el predicado "<math>\phi(b,a)</math> termina en menos de c pasos" es computado por el programa STP(b,a,c), que es pr.
f(x) es pr porque tanto los valores que devuelve como las funciones utilizadas en las guardas lo son. La decodificación de x en a, b y c es pr. y el predicado "fi(b,a) termina en menos de c pasos" es computado por el programa STP(b,a,c), que es pr.
 


== Ejercicio 6 ==
== Ejercicio 6 ==


Decimos que una funcion parcialmente computable f es extensible si existe g computable tal que g(x) = f(x) para todo x en el dominio de f. Probar que existe una funcion f parcialmente computable que no es extensible.
Decimos que una funcion parcialmente computable f es extensible si existe g computalbe tal que g(x) = f(x) para todo x en el dominio de f. Probar que existe una funcion f parcialmente computable que no es extensible.


'''Solucion'''
¿<math>f(x) = \Phi _x(x)</math>?


Sea <math>f(x_1, \dots, x_n, y) = \begin{cases} min_t STP(x_1,\dots,x_n,y,t)\ si \  \Phi_y (x_1,\dots,x_n) \downarrow \\
Sea <math>g(x_1, \dots, x_n, y) = \begin{cases} min_t STP(x_1,\dots,x_n,y,t)\ si \  \Phi_y (x_1,\dots,x_n) \downarrow \\
\uparrow \ sino \end{cases}</math>
\uparrow \ sino \end{cases}</math>


Supongamos ahora <math>f</math> es extensible y sea <math>g</math> computable la función que la extiende. Podríamos reescribir la función HALT con <math>g</math> de la siguiente manera:
Supongamos ahora <math>g</math> es extensible y sea <math>f</math> computable la función que la extiende. Pero entonces, podríamos reescribir la función <math>Halt</math> con <math>f</math>


<math>Halt(x_1,\dots,x_n,y) = STP(x_1,\dots,x_n,y, g(x_1,\dots,x_n,y))</math>
<math>Halt(x_1,\dots,x_n,y) = STP(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y))</math>
Lo cual es absurdo, ya que <math>Halt</math> no es computable y con esta definición es claramente computable. (la idea es que como <math>g</math> te devuelve en qué número de "iteración" <math>y</math> termina, no importa qué te devuelva la extensión <math>f</math> ya que podés chequear si es fruta o es uno de los valores de <math>g</math>, chequeando con <math>STP</math> si efectivamente <math>x</math> terminó en la cantidad de pasos que te dijo f)


Lo cual es absurdo, ya que HALT no es computable y con esta definición es claramente computable.
== Ejercicio 10 ==
 
La idea es que como ''f'' te devuelve el número de pasos necesarios para terminar la ejecución de ''y'' termina, no importa qué te devuelva la extensión ''g'' ya que podés chequear si es efectivamente el número de pasos o si es uno de los casos en que ''f'' se colgaba y ''g'' llenó el agujero.
 
== Ejercicio 7 ==
Probar que existen funciones ''g'' y ''h'' primitivas recursivas tal que
# <math>g: \mathbb{N}^3 \rightarrow \mathbb{N}, \Phi_z(u,v,w) = \Phi_{g(u,v,w)}(z)</math>
# <math>h: \mathbb{N} \rightarrow \mathbb{N}, \Phi_{h(n,m)}(x) = \Phi_n(x) + \Phi_m(x)</math>
 
'''Solucion Item 1'''


Definimos una función <math>\xi(z, u, v, w) = \Phi_z(u,v,w)\,\!</math>
Esta función es parcialmente computable por lo tanto existe un programa que la computa y un número ''e'' asociado a tal programa. Ahora sabemos que se cumple la igualdad
<math>\Phi_e(z, u,v,w) = \Phi_z(u,v,w)\,\!</math>
Usando el teorema del parámetro sabemos que existe una función ''f'' tal que
<math>\Phi_{f(e, u, v, w)}(z) = \Phi_e(z, u,v,w) = \Phi_z(u,v,w)\,\!</math>
La función ''f'' es PR ya que es la que nos dá el Teorema del Parámetro. Esta función toma 4 parámetros pero como nosotros ya conocemos el ''e'' del programa anterior podemos definir la función ''g''
<math>g(u,v,w) = f(e,u,v,w)\,\!</math>
Y así nos queda una función ''g'' primitiva recursiva con la aridad necesaria que cumple
<math>\Phi_{f(e, u, v, w)}(z) = \Phi_{g(u,v,w)}(z) = \Phi_z(u,v,w)\,\!</math>
'''Solucion Item 2'''
De la misma manera que en el punto anterior definimos <math>\xi(x, n, m) = \Phi_n(x) + \Phi_m(x)\,\!</math>
Y como es parcialmente computable sabemos que existe un programa P con número ''e'' que la computa. Entonces
<math>\Phi_e(x, n, m) = \Phi_n(x) + \Phi_m(x)\,\!</math>
Usando el Teorema del Parámetro existe una función ''f'' primitiva recursiva tal que
<math>\Phi_{f(e,n,m)}(x) = \Phi_e(x, n, m) = \Phi_n(x) + \Phi_m(x)\,\!</math>
Definimos la función
<math>h(n,m) = f(e,n,m)\,\!</math>
que cumple con lo pedido.
== Ejercicio 8 ==
Probar que las siguientes funciones no son computables
Probar que las siguientes funciones no son computables


<math>
==== Item A ====
f_1(x) =
\begin{cases}
1 & si\ \Phi_x(x) \neq x \\
0 & \textrm{sino}
\end{cases}
</math>
 
<math>
f_2(x,y) =
\begin{cases}
1 & si\ y \in \textrm{ran}\ \Phi_x \\
0 & \textrm{sino}
\end{cases}
</math>
 
'''Solución del primer caso'''
 
Definimos una función
 
<math>
g(x,y) =
\begin{cases}
x & si\ f_1(x) \\
x + 1 & \textrm{sino}
\end{cases}
</math>
 
Por el teorema de la recursión sabemos que existe un ''e'' tal que
 
<math>\Phi_e(y) = g(e,y) =  
\begin{cases}
e & si\ f_1(e) \\
e + 1 & \textrm{sino}
\end{cases}
</math>
 
Como la igualdad debe valer para todo ''y''' podemos fijar y = e. Entonces podemos deducir que hay dos casos
 
1. <math>\Phi_e(e) \neq e \Longleftrightarrow g(e, e) \neq e \Longleftrightarrow \neg f_1(e) \Longleftrightarrow \Phi_e(e) = e</math>. '''Absurdo!'''
 
2. <math>\Phi_e(e) = e \Longleftrightarrow g(e, e) = e \Longleftrightarrow f_1(e) \Longleftrightarrow \Phi_e(e) \neq e</math>. '''Absurdo!'''


La función no puede ser computable.
f(x) = 1 si <math>\Phi _x(x) = 2x</math>
 
        0  si no
 
'''Solución del segundo caso'''
 
Si fuera computable podemos escribir a HALT(x,y) = <math>f_2</math>(x,y). No puede ser computable.
 
== Ejercicio 9 ==
Probar usando el teorema de la recursion que la siguiente funcion no es computable
 
<math>f(x, y) = \begin{cases} 1\ si \  \Phi_x (y) > x \\
0 \ sino \end{cases}</math>
 
Sugerencia: considerar la funcion
 
<math>g(x, y) = \begin{cases} x\ si \  f(x,y) = 1 \\
x + 1 \ sino \end{cases}</math><br>
 
'''Solucion'''
 
Supongo f computable, entonces g tambien lo es. Por el teorema de la recursion se que existe e tal que <math>\Phi_e(y) = g(e,y)\,\!</math>, pero entonces:
 
<math>g(e, y) = \begin{cases} e\ si \  f(e,y) = 1\\
e + 1 \ sino \end{cases}</math><br>
<br>
donde <math>f(e,y) = 1 \Rightarrow \Phi_e(y) > e</math>
<br><br>
Si <math>\Phi_e(y) = g(e,y) = e \Rightarrow \Phi_e(y) > e.</math> Absurdo<br>
Si <math> \Phi_e(y) = e+1 \Rightarrow \Phi_e(y) \leq e.</math> Absurdo<br><br>
El absurdo viene de suponer f computable.
 
== Ejercicio 10 ==
Probar que las siguientes funciones no son computables
 
==== Item A ====
<math>
f(x) =
\begin{cases}
1 & si\ \Phi _x(x) = 2x \\
0 & \textrm{sino}
\end{cases}
</math>


Supongo f es computable, por ende es total
Supongo f es computable, por ende es total


Sea g(x,y) tal que
Sea g(x,y) tal que
<math>
g(x,y) = 2x+1 si f(x)
g(x,y) =
          2x   si no
\begin{cases}
2x+1 & si f(x) \\
2x & \textrm{sino}
\end{cases}
</math>


Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math>
Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math>
Línea 311: Línea 105:


==== Item B ====
==== Item B ====
<math>
 
  f(x) =
  f(x) = 1 si <math>dom(\Phi _x) = \emptyset</math>
\begin{cases}
        0  si no
1 & si\ dom(\Phi _x) = \emptyset \\
0 & \textrm{sino}
\end{cases}
</math>


Supongo f es computable
Supongo f es computable


Sea g(x,y) tal que
Sea g(x,y) tal que
<math>
g(x,y) = 1 si f(x)
g(x,y) =
          <math>\uparrow</math> si no
\begin{cases}
1 & si\ f(x) \\
\uparrow & \textrm{sino}
\end{cases}
</math>


Por teorema de la recursion, <math>\exists e / \Phi _e = g(e)</math>
Por teorema de la recursion, <math>\exists e / \Phi _e = g(e)</math>
Línea 335: Línea 120:


==== Item C ====
==== Item C ====
<math>
 
  f(x,y) =
  f(x,y) = 1  si <math>\Phi _x = \Phi _y</math>
\begin{cases}
          0  si no
1  & si\ \Phi _x = \Phi _y \\
0 & \textrm{sino}
\end{cases}
</math>


Supongo f es computable, por ende tambien total
Supongo f es computable, por ende tambien total


Sea g(x,y) tal que
Sea g(x,y) tal que
<math>
g(x,y) = <math>\Phi _y + 1</math> si f(x,y)
g(x,y) =
          <math>\Phi _y</math> si no
\begin{cases}
\Phi _y + 1 & si\ f(x,y) \\
\Phi _y & \textrm{sino}
\end{cases}
</math>


Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math>
Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math>
Línea 363: Línea 139:


==== Item D ====
==== Item D ====
<math>
 
f(x) =
f(x) = 1 si <math>Im(\Phi _x)</math> es infinita
\begin{cases}
        0 si no
1 & si\ Im(\Phi _x)\ \textrm{es\ infinita} \\
0 & \textrm{sino}
\end{cases}
</math>


Supongo f es computable, por ende tambien es total
Supongo f es computable, por ende tambien es total


Sea g(x,y) tal que
Sea g(x,y) tal que
<math>
g(x,y) = 0 si f(x)
g(x,y) =
          y si no
\begin{cases}
0 & si\ f(x) \\
y & \textrm{sino}
\end{cases}
</math>


Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math>
Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math>


Supongo <math>Im(\Phi _e)</math> infinita,
Supongo <math>Im(\Phi _e) infinita</math>,
<math>\Rightarrow f(e) \Rightarrow (\forall y) g(e,y) = \Phi _e(y) = 0 \Rightarrow Im(\Phi _e) = {0}</math>
<math>\Rightarrow f(e) \Rightarrow (\forall y) g(e,y) = \Phi _e(y) = 0 \Rightarrow Im(\Phi _e) = {0}</math>


Supongo <math>Im(\Phi _e)</math> finita,
Supongo <math>Im(\Phi _e) no infinita</math>,
<math>\Rightarrow \alpha(f(e)) \Rightarrow (\forall y) g(e,y) = \Phi _e(y) = y \Rightarrow Im(\Phi _e) = \mathbb{N}</math>
<math>\Rightarrow \alpha(f(e)) \Rightarrow (\forall y) g(e,y) = \Phi _e(y) = y \Rightarrow Im(\Phi _e) = Naturales</math>


==== Item E ====
==== Item E ====
<math>
 
  f(x) =  
  f(x) = 1 si <math>1 \in dom(\Phi _x)</math>
\begin{cases}
        0  si no
1 & si\ 1 \in dom(\Phi _x) \\
0 & \textrm{sino}
\end{cases}
</math>


La condicion equivale a decir que <math>\Phi _x(1)\downarrow</math>
La condicion equivale a decir que <math>\Phi _x(1)\downarrow</math>
Línea 404: Línea 167:


Sea g(x,y) tal que
Sea g(x,y) tal que
<math>
  g(x,y) = <math>\uparrow</math>  si f(x)
  g(x,y) =
          0 si no
\begin{cases}
\uparrow & si\ f(x) \\
0 & \textrm{sino}
\end{cases}
</math>


Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math>
Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math>


Evaluando g en (e,y) para todo y, se llega al absurdo
Evaluando g en (e,y) para todo y, se llega al absurdo
== Ejercicio 11 ==
Probar que la siguiente función es parcialmente computable:
<math>
f_2(x,y) =
\begin{cases}
1 & si\ y \in \textrm{ran}\ \Phi_x \\
\uparrow & \textrm{sino}
\end{cases}
</math>
(comparar con la funcion f2 del Ejercicio 8)
'''Solución'''
La función es computada por el programa
<math>\Phi_x(y)</math><br>
Y <- 1


== Ejercicio 12 ==
== Ejercicio 12 ==
Analizar la validez de las siguientes afirmaciones
==== Item A ====
Si B es r.e., entonces B es computable o su complemento es computable.
'''Solucion'''
Falso.
<math>B = \{ x : \Phi _x(x)\downarrow \} </math> <br/>
B es r.e., pero no es computable, ni tampoco su complemento. Si lo fueran, entonces el Halting problem seria computable.
==== Item B ====
Si <math>B_1,...,B_k</math> son r.e., entonces la union tambien lo es.
'''Solucion'''
Verdadero.
Basta construir un programa que vaya evaluando en paralelo todas las posibilidades, hasta que alguno termine.
==== Item C ====
Idem anterior, pero si la cantidad de conjuntos es infinita.
'''Solucion'''
Falso.
Si la proposición fuera verdadera, entonces cualquier conjunto de naturales sería r.e.:
Sea <math>A</math> un conjunto de naturales cualquiera. Definimos la familia de conjuntos <math>B_i = \{ x: x\in A\land x < i \}</math>. Los <math>B_i</math> son todos finitos, por lo tanto son todos computables, por lo tanto son todos r.e.  Además, es claro que <math>A = \cup_{i=1}^\infty B_i</math>. Por lo tanto, si la proposición fuera verdadera, <math>A</math> tendría que ser r.e.
Pero sabemos que existen conjuntos de naturales que no son r.e. (por ejemplo el complemento de <math>K</math>). Por lo tanto, la proposición debe ser falsa.


== Ejercicio 13 ==
== Ejercicio 13 ==
Sea B un conjunto infinito
==== Item A ====
Probar que B es c.e. sii existe una funcion f inyectiva computable tal que la imagen de f sea B.
'''Solucion'''
<math>\Rightarrow</math>)
Como B es c.e., existe una funcion g primitiva recursiva (por lo tanto, computable) tal que su imagen sea B. Defino f en funcion de g:
<math>f(0) = g(0)</math> <br/>
<math>f(n+1) = g(min_t((\forall i \leq n) g(t) \neq f(i))</math>
Intuitivamente, f va seleccionando todos los valores de g tal que no se hayan repetido anteriormente. Como B es infinito, siempre existira algun nuevo valor t  que no sea repetido. Por lo tanto, la minimizacion es propia y f resulta computable e inyectiva, pues no repite valores; y su imagen es igual a B.
<math>\Leftarrow</math>)
<br>Existe una funcion f inyectiva computable tal que su imagen es igual a B, por lo tanto, B es r.e.
<br>Se puede usar la funcion del 1.a para probarlo.
==== Item B ====
Probar que B es computable sii existe una funcion f de una variable computable y creciente tal que Im f = B.
'''Solucion'''
<math>\Rightarrow</math>)
B = {x : B(x)} = {f(0), f(1), ... }
<math>f(0) = min_t (B(t))</math> <br/>
<math>f(n+1) = min_t (f(n) < t \wedge B(t))</math>
La idea de f es que va probando con todos los numeros naturales y para cada uno de ellos chequea si B(i) es verdadero o no. Si lo es, entonces lo devuelve como valor de la funcion, si no, sigue probando.
<math>\Leftarrow</math>)
B es computable sii su funcion caracteristica B(x) lo es. <br/>
<math>B(x) = (\exists t \leq x) f(t) = x</math>
Como f es computable, entonces B lo es.
== Ejercicio 14 ==


Probar que todo conjunto re infinito contiene un subconjunto computable infinito.
Probar que todo conjunto re infinito contiene un subconjunto computable infinito.
Línea 530: Línea 185:


Defino la funcion g tal que:
Defino la funcion g tal que:
  g(0) = f(0)
  g(0) = 0
  g(n+1) = f(min(t) (f(t) > g(n)))
  g(n+1) = f(min(t) (f(t) > g(n)))


Intuitivamente, la funcion g selecciona los valores que estan en orden creciente en la imagen de f. Como B es infinito, para cualquier indice elegido siempre existira otro mayor tal que la funcion resulte creciente. Por lo tanto, la minimizacion es propia y la funcion g resulta computable ademas de creciente.
Intuitivamente, la funcion g selecciona los valores que estan en orden creciente en la imagen de f. Como B es infinito, para cualquier indice elegido siempre existira otro mayor tal que la funcion resulte creciente. Por lo tanto, la minimizacion es propia y la funcion g resulta computable ademas de creciente.


Como g es computable y creciente, entonces su imagen define un conjunto, contenido en B, que es computable e infinito (vale por ej 12).
Como g es computable y creciente, entonces su imagen define un conjunto, contenido en B, que es computable e infinito (vale por ej 12).  


== Ejercicio 15 ==
== Ejercicio 14 ==


Probar que si B es re y f es una funcion parcialmente computable, entonces <math>A = \{x : f(x) \in B\}</math> es re.
Probar que si B es re y f es una funcion parcialmente computable, entonces <math>A = {x : f(x) \in B}</math> es re.


'''Solución'''


Como B es re, existe g parcialmente computable tal que  
Como B es re, existe g parcialmente computable tal que  
<math>B = \{x : g(x)\downarrow\}</math>
<math>B = {x : g(x)\downarrow}</math>


Para que A sea re, tiene que existir una funcion h parcialmente computable tal que <math>A = \{x : h(x)\downarrow\}</math>.
Para que A sea re, tiene que existir una funcion h parcialmente computable tal que <math>A = {x : h(x)\downarrow}</math>.


Sea h = g(f(x)), parcialmente computable por ser composicion de pc.  
Sea h = g(f(x)), parcialmente computable por ser composicion de pc.  
Línea 552: Línea 206:


Entonces A es re.
Entonces A es re.
== Ejercicio 16 ==


== Ejercicio 17 ==
== Ejercicio 17 ==
<br> =>) Sea A = We = {x: Φx↓} => x є A si existe un tiempo t tal que Φe(x)↓, entonces
<br> A = {x: (<math>\exists</math> t) STP<sup>(1)</sup>(x,e,t)}, y se sabe que STP es un predicado PR
<br> <=) Sea el predicado PR J(x) = (<math>\exists</math> y) P(x,y), y el siguiente programa P:
<pre>
[A] IF J(Z)=1 GOTO F
    Z++
    GOTO A
[F] Y <- 1
</pre>
Como puede verse, P computa la funcion parcialmente computable
<pre>
f(x) = {1  si J(x)=1
      {↑  sino
</pre>
Con lo cual B = dom f => B es RE
== Ejercicio 18 ==


Definir un predicado pr P tal que <math>A = {x : (\forall y)P(x,y)}</math> no sea re.
Definir un predicado pr P tal que <math>A = {x : (\forall y)P(x,y)}</math> no sea re.
Línea 583: Línea 216:
<math>B=\{x | \Phi_x (x)\uparrow\}</math>  , o sea, es el complemento del famoso conjunto <math>K</math> (x tal que Halt(x,x)), que ya sabíamos que no es r.e. porque lo probamos en la teórica/práctica.
<math>B=\{x | \Phi_x (x)\uparrow\}</math>  , o sea, es el complemento del famoso conjunto <math>K</math> (x tal que Halt(x,x)), que ya sabíamos que no es r.e. porque lo probamos en la teórica/práctica.


== Ejercicio 19 ==
== Ejercicio 18 ==
 
Sea <math>B=\{ x \ : \  \Phi_x \ es\ una\ funcion\ total\}</math>
Sea <math>B=\{ x \ : \  \Phi_x \ es\ una\ funcion\ total\}</math>


Línea 591: Línea 223:
b. Probar que <math>N - B</math> no es r.e.
b. Probar que <math>N - B</math> no es r.e.


====Item A====
====Item a)====
 
Este lo hicimos en clase.
Este lo hicimos en clase.
 
====Item b)====
====Item B====
 
Lo que nos piden probar es que el complemento de B no es r.e. O sea, que el conjunto <math>A=\{ x \ : \  \Phi_x \ es\ una\ funcion\ parcial\}</math> no es r.e. Supongamos entonces lo contrario. Esta suposición implica que la pertenencia a B es parcialmente computable (devuelve 1 si es true, se cuelga sino).
Lo que nos piden probar es que el complemento de B no es r.e. O sea, que el conjunto <math>A=\{ x \ : \  \Phi_x \ es\ una\ funcion\ parcial\}</math> no es r.e. Supongamos entonces lo contrario. Esta suposición implica que la pertenencia a B es parcialmente computable (devuelve 1 si es true, se cuelga sino).


Línea 611: Línea 240:
Pero entonces superabsurdo, que partió de suponer que A era un conjunto r.e.
Pero entonces superabsurdo, que partió de suponer que A era un conjunto r.e.


==Ejercicio 20 ==
== Ejercicio 20 ==
Probar que existe un <math>e</math> tal que <math>W_e=\{e\}</math>.
Tal e existe,por definición de <math>W_e</math>, si y sólo si existe un <math>e</math> tal que <math>\{e\}=\{x \in N\ |\ \Phi_e(x)\downarrow\}</math>.
 
'''Solucion'''
 
Definimos
 
<math>f(x,y) = \begin{cases} 1\ si\ y = x \\ \uparrow\ sino \end{cases}</math>
 
Por el teorema de la recursión, existe un e tal que:
<math>\Phi_e(y) = f(e,y)</math>, pero entonces:
 
<math>\Phi_e(y)</math> estará definida solo si y=e, es decir, el dominio de <math>\Phi_e(y)</math> será e, eso significa que <math>W_e=\{e\}</math> que era lo que queriamos probar.
 
== Ejercicio 21 ==


Demostrar que las funciones definidas en el Ejercicio 10 no son computables aplicando el Teorema de Rice
Demostrar que las funciones definidas en el Ejercicio 10 no son computables aplicando el Teorema de Rice
Línea 678: Línea 292:
   
   
El resto sale de la misma forma :)
El resto sale de la misma forma :)
[[Category:Prácticas]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Práctica_3_(LyC_Verano)»