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

{{Back|Lógica y Computabilidad}}

== Ejercicio 1 ==

Sea f: N -> N computable. 

=== Item A ===

Demostrar que la función

 g(x) = min {y : f(y) = x}  si existe y tal que f(y) = x
        se cuelga           si no

es parcialmente computable.

'''Solución'''

Damos un programa que computa g.

 Z1 <- X1
 [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.
 IF Z3 = Z1 GOTO B
 Z2 <- Z2 + 1
 GOTO A
 [B] Y <- Z2

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 ===

Demostrar que si f es además biyectiva, f^-1 es computable. 

'''Solución'''

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.

== Ejercicio 2 ==

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'''

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 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:

 min{y : f(y) = x}

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.

== Ejercicio 3 ==

Sea f: N -> N una función computable biyectiva. Probar que Halt(f(x), x) no es computable. Sugerencia: considerar la función:

 h(x) = 1 si       fi(x, f^-1(x)) se cuelga
        se cuelga  en otro caso

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 perteneciente a N tal que #(P) = e

Ahora bien, por la definición de HALT:

HALT(f(e), e)  <=> P(f(e)) termina

Y por el código de P:

P(f(e)) termina <=> -(HALT(f(e), e)

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:

 f(x) = fi(x,x) + 1   si fi(x,x) termina
        se cuelga     si no

 g(x) = 1             si x pertenece al dominio de f
        se cuelga     si no

 h(x) = 0             si fi(x,x) termina
        se cuelga     si no

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 ==

Probar que la siguiente función es primitiva recursiva:

 f(x) = 1 si x = <<a,b>,c> y fi(b,a) termina en menos de c pasos
        0 en otro caso

'''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 "fi(b,a) termina en menos de c pasos" es computado por el programa STP(b,a,c), que es pr.


== Ejercicio 6 ==

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.

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

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>

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,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)

== Ejercicio 7 ==

== Ejercicio 8 ==

== 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:'''<br>
supongo f computable, entonces g tambien lo es.<br>
por el teorema de la recursion se que existe e tal que <math>\Phi_e(y) = g(e,y)</math>, pero entonces:<br><br>

<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 ====

 f(x) = 1  si <math>\Phi _x(x) = 2x</math>
        0  si no

Supongo f es computable, por ende es total

Sea g(x,y) tal que
 g(x,y) = 2x+1  si f(x)
          2x    si no

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

Supongo <math>\Phi _e(e) = 2e</math>
<math>\Rightarrow f(e) \Rightarrow g(e,e) = \Phi _e(e) = 2e+1 \neq 2e</math>

Supongo <math>\Phi _e(e) \neq 2e</math>
<math>\Rightarrow \alpha(f(e)) \Rightarrow g(e,e) = \Phi _e(e) = 2e</math>

Absurdo que proviene de suponer que f es computable

Todos los items siguientes se resuelven con el mismo mecanismo

==== Item B ====

 f(x) = 1  si <math>dom(\Phi _x) = \emptyset</math>
        0  si no

Supongo f es computable

Sea g(x,y) tal que
 g(x,y) = 1  si f(x)
          <math>\uparrow</math>  si no

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

Evaluando g en e se llega al absurdo

==== Item C ====

 f(x,y) = 1  si <math>\Phi _x = \Phi _y</math>
          0  si no

Supongo f es computable, por ende tambien total

Sea g(x,y) tal que
 g(x,y) = <math>\Phi _y + 1</math>  si f(x,y)
          <math>\Phi _y</math>  si no

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

Sea a tal que <math>\Phi _a\downarrow</math>

Por teorema del parametro, <math>\exists s / \Phi _s = g(e,a) = \Phi _e(a)</math>

Evaluando g en (s,a) se llega al absurdo

==== Item D ====

 f(x) = 1  si <math>Im(\Phi _x)</math> es infinita
        0  si no

Supongo f es computable, por ende tambien es total

Sea g(x,y) tal que
 g(x,y) = 0  si f(x)
          y  si no

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

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>

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) = Naturales</math>

==== Item E ====

 f(x) = 1  si <math>1 \in dom(\Phi _x)</math>
        0  si no

La condicion equivale a decir que <math>\Phi _x(1)\downarrow</math>

Supongo f es computable, por ende tambien es total

Sea g(x,y) tal que
 g(x,y) = <math>\uparrow</math>  si f(x)
          0  si no

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


== Ejercicio 11 ==

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 1'''

Verdadero.

Se deberia poder construir un programa utilizando la tecnica de Dove Tailing que vimos en la teorica.<br/>
Es decir, para determinar si ''x'' pertenece, evaluo ''STP(b1, x, 1)''.<br/>
Si es falso, pruebo con ''STP(b1, x, 2)'' y ''STP(b2, x, 2)''.<br/>
Si dan falso, pruebo con ''STP(b1, x, 3)'', ''STP(b2, x, 3)'' y ''STP(b3, x, 3)''.<br/>
Asi sucesivamente hasta hallar un valor que verifique, o colgarse si no pertenece al conjunto.

En forma recursiva, la funcion seria:
<math>U(x) = (\exists t)(\exists y) STP(B_y, x, t)</math><br/>
Como la minimizacion es no acotada (ni tampoco propia), el programa es parcialmente computable y caracteriza un conjunto r.e.

'''Solucion 2'''

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.


==== Item D ====

Encontrar el error en alguna de las soluciones del item C.

== Ejercicio 12 ==

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 13 ==

Probar que todo conjunto re infinito contiene un subconjunto computable infinito.

'''Solucion'''

Sea f p.r. tal que la imagen de f sea igual al conjunto B (r.e. e infinito).

Defino la funcion g tal que:
 g(0) = f(0)
 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.

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 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.


Como B es re, existe g parcialmente computable tal que 
<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>.

Sea h = g(f(x)), parcialmente computable por ser composicion de pc. 
<math>g(f(x)) = f(x) \in B</math>

Entonces A es re.

== Ejercicio 15 ==

== Ejercicio 16 ==

<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 17 ==

Definir un predicado pr P tal que <math>A = {x : (\forall y)P(x,y)}</math> no sea re.

Sea <math>P(x,y) := STP(x,x,y)=0</math>
Como STP es p.r., <math>P(x,y)</math> es claramente p.r. también
Notemos ahora que <math>B=\{x: (\forall y) STP(x,x,y)=0\}</math> es lo mismo que 
<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 18 ==

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

a. Probar que B no es r.e.

b. Probar que <math>N - B</math> no es r.e.

====Item A====

Este lo hicimos en clase.

====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).

Definamos entonces:

<math>f(x,y) = \begin{cases} 1\ si\ x \in A \\ \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:

Si <math>e \in A \rightarrow \Phi_e(y)=1 \rightarrow e\ es\ total</math> (Absurdo porque partimos de que e era parcial y por eso estaba en A)

Si <math>e \notin A \rightarrow \Phi_e(y)\uparrow \rightarrow e\ es\ parcial</math> (Absurdo porque partimos de que e era total y por eso no estaba en A).

Pero entonces superabsurdo, que partió de suponer que A era un conjunto r.e.

==Ejercicio 19==
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>.

[... EN CONSTRUCCIÓN ...]
<br><br>
''Posible resolucion'' '''(Sin verificar)'''
<br><br>
<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 20 ==

Demostrar que las funciones definidas en el Ejercicio 10 no son computables aplicando el Teorema de Rice

==== Item C ====

 f(x,y) = 1  si <math>\Phi _x = \Phi _y</math>
          0  si no

A = {x: <math>\Phi _x = \Phi _0</math>}

Quiero ver que A no es computable por Rice. Para esto tengo que probar que:

1. <math>A \neq \emptyset</math>

A representa el conjunto de los programas que computan el programa 0 (aquel que devuelve 0 para toda entrada).

Ejemplo: 
el programa que computa f(x,y) donde

f(x,y) =  (x>y).(y-x)+(x<=y).(x-y)

claramente, esta función hace lo mismo que #P=0
donde P es el programa que computa a 

n(x) = 0

Entonces, <math>A \neq \emptyset</math>

2. <math>A \neq N</math>

Ejemplo: 
el programa que computa la función constante 

g(x) = 8

Además, puede verse que hay programas que no están en A

Entonces, <math>A \neq N</math>

3. A es un conjunto de índices

Se dice que A es un conjunto de índices si dado C una clase de funciones parcialmente computables A es el conjunto de los programas que computan a dichas funciones. 
En este caso, A es el conjunto de los programas que computan lo mismo que <math>\Phi _0</math> (la función nula). 
Entonces dado x perteneciente a A y <math>\Phi _x = \Phi _y</math> --> y pertenece a A.

Muy bien, ahora, por Rice, A no es computable

Supongo f computable. Entonces f(x,0) es computable. 
Pero f(x,0) = g(x) es la función característica de A. Absurdo, porque A no es computable --> f no es computable :)
 
El resto sale de la misma forma :)

[[Category:Prácticas]]