Funciones S-computablesFacundo Carreiro

Martes 8 de Febrero de 2011

Ejercicio 1.

a. Mostrar que el producto (x, y) = x.y es S-computable. Pueden usarse las macros definidas enla teorica (V 0,GOTO L, Y X,V V , Y X1 +X2, Y X1 X2).

b. Instanciar uno de los macros usados teniendo cuidado de hacer los reemplazos pertinentes.

Resolucion (a). Recordemos que los macros son expresiones que no pertenecen al lenguaje S y seusan como abreviaciones de conjuntos de instrucciones que si pertenecen al lenguaje.

1 Z X22 IF Z 6= 0 GOTO A3 GOTO E4 [A] Y Y +X15 Z Z 16 IF Z 6= 0 GOTO A

El anterior programa calcula el producto usando otros macros vistas en la teorica.

Resolucion (b). Vamos a expandir el macro de la lnea 1 del programa. Notaremos que aparecenetiquetas y variables que ya estaban en el programa original o que deben ser cambiadas paraobtener el resultado deseado (marcadas en negrita). La definicion de este macro nos dice comodebemos reemplazarlas.

1 Y 02 [A] IF X 6= 0 GOTO B3 GOTO C4 [B] X X 15 Y Y + 16 Z Z+ 17 GOTO A8 [C] IF Z 6= 0 GOTO D9 GOTO E10 [D] Z Z 111 X X+ 112 GOTO C13 IF Z 6= 0 GOTO A14 GOTO E15 [A] Y Y +X116 Z Z 117 IF Z 6= 0 GOTO A

1 Z 02 [A] IF X2 6= 0 GOTO B3 GOTO C

4 [B] X2 X2 15 Z Z + 16 Z2 Z2 + 17 GOTO A

8 [C ] IF Z2 6= 0 GOTO D9 GOTO S10 [D] Z2 Z2 111 X2 X2 + 112 GOTO C

13 [S] IF Z 6= 0 GOTO A14 GOTO E15 [A] Y Y +X116 Z Z 117 IF Z 6= 0 GOTO A

Del lado derecho se encuentra el programa resultante luego de instanciar correctamente el macro.Es importante notar que, en el macro original haba un GOTO E que pretenda escapar delcodigo del macro. Si hubieramos dejado esa intruccion tal cual el comportamiento sera distinto:terminara el programa. Por esa razon tuvimos que agregar una nueva etiqueta [S] y cambiar

1

el salto para que siga con la proxima instruccion. Observar tambien que, luego de expandir laprimera lnea, siguen usandose muchos macros y por lo tanto el programa aun no esta escrito(estrictamente) en S.Ejercicio 2. Sea etiquetasUND : N N la funcion que toma la codificacion de un programa #py devuelve la codificacion de una secuencia (sin repetidos) con las etiquetas que son usadas en p(en algun GOTO) pero que no estan definidas en el mismo. Demostrar que es p.r.

Resolucion. Primero que nada pensemos que herramientas tenemos para probar esto. Podemosescribir un programa en S para probar que es p.r? No! Eso solo probara que es S-computable.No tenemos manera de, a partir de un programa en S, asegurar que una funcion sea p.r.

Otra manera posible sera usar la definicion de funcion primitiva recursiva: construirla a partirde las funciones iniciales, composicion y recursion primitiva. Esta opcion parece demasiado tra-bajosa. Recordemos que podemos (y esta fuertemente recomendado) usar nuestras herramientasmas poderosas: minimizacion acotada, cuantificadores acotados, etc.

Sin importar que tan poderosas sean nuestras herramientas parece muy dificil calcular lafuncion pedida de manera constructiva. Intentaremos una tecnica conocida como Generate andTest (generar y probar) que consiste en lo siguiente. Si podemos

Generar posibles soluciones (en este caso, secuencias de etiquetas).Describir la solucion que buscamos y verificar si una solucion dada es correcta.

Entonces

Generamos todas las posibles soluciones y verificamos hasta encontrar la que queremos.

Intentemos, por lo tanto, describir la solucion que buscamos de manera primitiva recursiva. Vaya-mos de a poco completando la especificacion de nuestra funcion

etiquetasUND(#p) = secuencia s tal que: sinRepetidos(s) ypara toda etiqueta e: e s si y solo siesUsada(e,#p) estaDefinida(e,#p)

Recordemos que las secuencias son numeros naturales entonces si recorremos los naturales ylos interpretamos como secuencias estaramos recorriendo las posibles soluciones al problema. Lomismo ocurre con las etiquetas. Entonces, escribamos la funcion de una manera mas precisa.

etiquetasUND(#p) = minsk1 sinRepetidos(s) ek2 (esEtiqueta(e) (e s (esUsada(e,#p) estaDefinida(e,#p))))

Para que la funcion sea p.r. solo podemos usar minimizacion y operadores acotados. La lista deetiquetas no puede ser mas grande que el programa ya que el programa es una lista de instruccionesque incluyen a las etiquetas. Por lo tanto, k1 = #p es una buena cota. Por la misma razon, solo nosinteresa considerar las etiquetas que podran aparecer en el programa. De esta manera, k2 = #pdebera ser una buena cota.

Solo nos queda definir las funciones auxiliares de manera primitiva recursiva. Recordemos quela codificacion de un programa P como un numero natural es

#(P ) = [#(I1), . . . ,#(Ik)] 1y codificamos a la instruccion I con #(I) = a, b, c donde

1. si I tiene etiqueta L, entonces a = #(L); si no a = 0 (las etiquetas tienen # > 0)2. si la variable mencionada en I es V entonces c = #(V ) 13. si la instruccion I es

a) V V entonces b = 0

2

b) V V + 1 entonces b = 1c) V V 1 entonces b = 2d) IF V 6= 0 GOTO L entonces b = #(L) + 2

Las funciones auxiliares que dependen de la codificacion de programas quedaran definidas como

estaDefinida(e,#p) = n|p+1| l((p+ 1)[n]) = eesUsada(e,#p) = n|p+1| l(r((p+ 1)[n])) = e+ 2

El resto de los auxiliares pueden definirse como

sinRepetidos(s) = i|s|j|s|(i 6= j si 6= sj)esEtiqueta(e) = e > 0

Esto prueba que la funcion que definimos es primitiva recursiva. Aun faltara probar que se com-porta exactamente como queremos. En este caso, como el objetivo del ejercicio era aprender latecnica de Generate and Test, dejaremos esa demostracion como tarea para el lector.

Ejercicio 3. Demostrar que la funcion f : N2 N

f(#p, z) =

1 si para alguna entrada x y algun momento t de

la ejecucion de p pasa que la variable Y > z si no

es parcial computable.

Resolucion. Siempre es recomendable evitar programar en S ya que es engorroso, facil de equi-vocarse y difcil de probar su correctitud. En cambio, trataremos de atacar el problema como elpunto anterior.

h(#p, z) = existe x, existe t tal que en el paso t de ejecutar p vale Y > z

En este caso no parece haber una cota para x y t. Ya que el tamano de la entrada y el tiempo quetome el programa en alcanzar Y > z puede ser arbitrariamente grande. Incluso podra suceder quepara toda entrada y tiempo pase Y z, en tal caso el programa debera colgarse. Reescribamosesta ultima ecuacion usando minimizaciones no acotadas.

h(#p, z) = xt en el paso t de ejecutar p vale Y > zPara saber el valor de alguna variable en un momento dado podemos usar la funcion

SNAP(x,#p, t) = i, donde [#V ] = el valor de la variable V que devuelve un par con el numero de instruccion y el estado de las variables luego de ejecutar tpasos del programa p con entrada x. Esta funcion fue probada p.r. en la teorica. Reescribiendo loanterior quedara

h(#p, z) = xt(r(SNAP(x,#p, t) i,

)[0] > z)

Listo? Observemos lo siguiente: Los existenciales no estan acotados porque queremos que bus-quen todas las combinaciones posibles de valores x, t. Tenemos un problema con el comportamientode los existenciales. No debemos olvidar que, en el fondo hay un programa en S que simula losexistenciales. Segun la definicion de la teorica de la minimizacion no acotada, el comportamientode nuestro programa sera el siguiente:

1. Inicia x = 0, intenta validar el predicado que esta luego de x.2. Inicia t = 0. Valida la condicion SNAP(x,#p, t))[0] > z. Si es verdadera devuelve 1.

3

3. Si era falsa prueba con t = 1.4. Si era falsa prueba con t = 2.

...

No prueba todas las combinaciones! Se queda probando los distintos valores de t pero no cambianunca el x. Esto puede ser un gran problema ya que si justo la funcion devolva 1 en (x = 1, t = 1)en nuestro caso quedara indefinida. Como podemos, entonces, recorrer todas las combinaciones?

Podemos aprovechar que la codificacion de pares esta en biyeccion con los naturales. Por lotanto si n recorre los naturales y luego lo interpretamos como n = a, b estaramos recorriendotodas las combinaciones de posibles a, b. Esta tecnica se llama dovetailing. Podemos reescribirnuestra funcion como

h(#p, z) = nx,t

(r(SNAP(l(n)x

,#p, r(n)t

))[0] > z)

Tambien admitiremos el siguiente abuso de notacion para simplificar la notacion

h(#p, z) = x,t(r(SNAP(x,#p, t))[0] > z)

Ya que formamos h a partir de funciones p.r. mas un operador no acotado con esto probamos queh es parcial computable. Solo nos queda demostrar la correctitud, es decir, que f = h. Para la idaveamos que si f(#p, z) = 1 entonces h(#p, z) = 1.

Si f(#p, z) = 1, entonces existe una entrada x1 y un tiempo t1 en el que Y > z. Por lo tantor(SNAP(x1,#p, t1))[0] > z es verdadero. Como el existencial no acotado recorre todos losvalores de x y t, cuando llegue a (x = x1, t = t1) sera verdadero el predicado interno y elprograma devolvera 1. Entonces h(#p, z) = 1.

Para la vuelta probemos que si h(#p, z) = 1 entonces f(#p, z) = 1.

Si h(#p, z) = 1, entonces existen x1, t1 para los cuales r(SNAP(x1,#p, t1))[0] > z esverdadero. Ya vimos que esa expresion es verdadera justamente cuando a los t1 pasos de laejecucion de p con entrada x1 la variable Y > z. Entonces f(#p, z) = 1.

Ejercicio 4. Demostrar que si al lenguaje S le sacamos la instruccion V V + 1 hay funcionespreviamente parcial computables que dejan de serlo.

Resolucion. Intuitivamente notamos que, como la variable de salida Y empieza en 0, si escribo unprograma donde no puedo sumar entonces hay solo dos opciones para la salida: Devuelve 0 o seindefine.

Para facilitar la demostracion es interesante observar que para esta demostracion podemos res-tringirnos a las funciones totales. Es decir, si encuentro una funcion total que es S-computable perono puedo computarla sin la suma entonces estara probando lo pedido. Esto es porque computabletotal implica parcial computable. En este escenario, si escribo un programa (que no se indefine) yque no usa la suma entonces debera devolver siempre 0.

Como formalizar esta intuicion? Recordemos que podemos pensar la ejecucion de un programa(que termina1) con entrada x como una sucesion de estados

d1I1 d2 I2 Ik1 dk

donde d1 = (1, 1) es el estado inicial, dk = (|p| + 1, k) es el estado final e Ii es la instruccionejecutada para pasar de un estado a otro. Y que la funcion (n)p computada por el programa pesta definida como el valor de la variable Y en dk. Probaremos entonces, por induccion, que entodo estado di de la ejecucion vale Y = 0.

1Si el programa no termina la sucesion es infinita

4

1. Caso base (i = 1): Como dijimos previamente, en el estado inicial por definicion Y = 0.

2. Caso inductivo (i = n): Por hipotesis inductiva sabemos que en el estado anterior dn1 valaY = 0. Tenemos que dividir en casos dependiendo de que instruccion fue ejecutada parallegar al nuevo estado.

V V 1. Si V 6= Y es claro que el valor de Y se mantiene (en 0 por HI). Si V = Yel valor de Y debera decrecer en 1 pero como Y era 0 se mantiene en 0.

IF V 6= 0 GOTO L. En este caso no importa si V = Y o no. La semantica del IF nosdice que cambia el numero de instruccion pero que el estado se mantiene igual. Por lotanto, como por HI sabamos que Y = 0, el valor de Y se mantiene en 0.

De esta manera probamos que, durante la ejecucion de cualquier programa que escribamos sinusar la suma, el valor de la variable Y se mantiene en 0. En particular, en el estado final valeY = 0. Por lo tanto solo podemos calcular la funcion constante f(x) = 0.

Usando el lenguaje completo podamos calcular, entre otras cosas, cualquier funcion constante(las mayores a 0 tambien). De esta manera dimos una funcion previamente S-computable totalque, al sacar la suma, no puede ser computada.

5