**TC: Programas y Funciones Computables** Como ya comentamos en el capítulo anterior, para abordar cuestiones acerca de la computabilidad necesitamos elegir un _modelo de computación_, que nos permita precisar lo que entendemos por _procedimiento efectivo_ o _algoritmo_. De esta forma, los algoritmos estarán bien definidos y, por tanto, serán susceptibles de ser estudiados en Matemáticas como cualquier otra teoría. En general, la expresión formal de un algoritmo en un modelo concreto se denomina _programa_, si el modelo está basado en un _lenguaje de programación_, o _máquina_, si el modelo es una representación formal orientada a un tipo especial de procedimiento mecánico, en el que se hace referencia explícita a la gestión de la memoria de trabajo donde se almacenan datos. # El lenguaje de programación GOTO En esta sección introducimos el lenguaje GOTO, que proporciona el modelo de computación con el que trabajaremos durante el curso. Está diseñado para manejar números naturales. En una primera aproximación podemos decir que este lenguaje consta de: !!!def: El lenguaje GOTO * **Variables**: * (a) Variables de entrada: $X\equiv X_1, X_2,...,X_n,...$ * (b) Variables locales: $Z\equiv Z_1,Z_2,...,Z_n,...$ * (c) Una variable de salida: $Y$ * **Etiquetas**: $A\equiv A_1,B\equiv B_1,C\equiv C_1,D\equiv D_1,E\equiv E_1,A_2,B_2,C_2,D_2,E_2,...$ * **Instrucciones**: (Con o sin etiquetar) * (a) Incremento: $V \leftarrow V + 1$ * (b) Decremento: $V \leftarrow V - 1$ * (c) Condicional: $IF\ V \neq 0\ GOTO\ L$ * (d) $V\leftarrow V$ !!!def: Programas GOTO Un programa de GOTO es una sucesión finita de instrucciones con o sin etiquetas. Cada instrucción se interpretará como una cierta operación básica del siguiente modo: Las instrucciones de un programa se interpretan secuencialmente salvo que alguna instrucción condicional cambie esto. Precisando: * Cada variable usada por el programa almacena un número natural (inicialmente $0$, salvo para las variables de entrada). * Las instrucciones actúan como sigue: * $V \leftarrow V + 1$: incrementa en $1$ el valor de $V$. * $V \leftarrow V - 1$: resta $1$ al valor de $V$ si es distinto de $0$, y deja dicho valor igual si es $0$. * $IF\ V \neq 0\ GOTO\ L$: * Si $V \neq 0$ se ejecuta la primera instrucción etiquetada por $L$ (si no existe tal instrucción, el programa para); * si $V \neq 0$, se ejecuta la siguiente instrucción. * $V\leftarrow V$: No tiene ningún efecto. Un programa permite calcular una función dando a las variables de entrada, $X_1,...,X_k$ unos valores iniciales $n_1,...,n_k$ y ejecutando el programa. Si se para (porque no hay próxima instrucción o una instrucción condicional nos envía a una etiqueta que no aparece en el programa etiquetando una instrucción) el valor de la función es el valor de la variable de salida $Y$. ## Ejemplos Veamos unos ejemplos de programas en este lenguaje, junto a las funciones que calculan: !!!tip: Ejemplo 1 Sea $P$ el programa ```none [A] X <- X - 1 Y <- Y + 1 IF X != 0 GOTO A ``` Entonces $P(n)=\begin{cases} 1& \text{si \(n=0$,}\\ n& \text{si $n \neq 0$} \end{cases}\); es decir, este programa_copia_ el valor de $X$ en $Y$, si el valor no es $0$. !!!Tip: Ejemplo 2 Veamos ahora un programa que calcula la función identidad sobre ${\Bbb N}$, es decir $P(n)=n$ ```none IF X != 0 GOTO B Z <- Z + 1 IF Z != 0 GOTO E [B] X <- X - 1 Y <- Y + 1 IF X != 0 GOTO B ``` En este programa se ha utilizado un bloque de instrucciones del tipo ```none Z <- Z + 1 IF Z != 0 GOTO L ``` cuya ejecución es equivalente a ir incondicionalmente a la etiqueta $L$. Para simplificar la escritura de los programas, este bloque lo abreviaremos como $GOTO\ L$. Pero debe resaltarse que no hemos añadido ninguna instrucción nueva al lenguaje, sino que es una simple abreviatura de un par de líneas a las que sustituye, es lo que llamamos una_macro_. Más adelante comentaremos cómo se pueden introducir estas macros en los programas, por ahora todo lo que necesitamos para poder sustituir una macro por su valor real es utilizar en ella variables de trabajo que no ocurran en ninguna otra instrucción del programa en el que se encuentre. Así, si en un programa ya se utilizara la variable $Z$, bastaría considerar un bloque $GOTO\ L$ del tipo: ```none Zk <- Zk + 1 IF Zk != 0 GOTO L ``` donde la variable $Z_k$ no se está utilizando. !!!Tip: Ejemplo 3 Damos a continuación un conjunto de líneas en el lenguaje GOTO que nos permite_asignar_ a una variable el valor nulo. Si $V$ es la variable que queremos anular, entonces ```none [A] V <- V - 1 IF V != 0 GOTO A ``` es un bloque que, insertado convenientemente en un programa (es decir, sustituyendo $V$ por la variable que queremos anular, y $A$ por una etiqueta que no se esté utilizando en dicho programa), produce el efecto de anular la variable. Este bloque de instrucciones lo abreviaremos por $V\leftarrow 0$. !!!Tip: Ejemplo 4 El programa dado en el ejemplo 2, en principio, podría ser interpretado por una asignación de una variable en otra. Sin embargo, este programa destruye el valor de la variable $X$, y por tanto su acción no sería la deseada de asignar solamente el valor de $X$ al de $Y$. Para obtener un programa que realice la asignación, seguiremos dos pasos, uno primero en que el valor de $X$ se copia en dos variables, $Y$ y $Z$, y se pierde el de $X$, y un segundo paso en el que se copia el valor de $Z$ en $X$, perdiéndose el de $Z$; el resultado final es que $X$ mantiene su valor, e $Y$ (la variable de salida) toma el valor de $X$. ```none [A] IF X != 0 GOTO B GOTO C [B] X <- X - 1 Y <- Y + 1 Z <- Z + 1 GOTO A [C] IF Z != 0 GOTO D GOTO E [D] Z <- Z - 1 X <- X + 1 GOTO C ``` De esta forma, podemos hablar de la asignación: $V \leftarrow V'$, cuyo bloque correspondiente sería el programa anterior sustituyendo $X$ por $V'$, $Y$ por $V$ y teniendo cuidado con las variables auxiliares y las etiquetas para que no aparezcan en el programa en que usamos la macro. !!!Tip: Ejemplo 5 La función suma: ```none Y <- X1 Z <- X2 [B] IF Z != 0 GOTO A GOTO E [A] Z <- Z - 1 Y <- Y + 1 GOTO C ``` Considerándola como macro, la notaremos como $$V\leftarrow V_1+V_2$$ !!!Tip: Ejercicio 6 A partir de la función anterior es fácil definir la función producto como: ```none Z2 <- X2 [B] IF Z2 != 0 GOTO A GOTO E [A] Z2 <- Z2 - 1 Z1 <- x1 + Y Y <- Z1 GOTO B ``` Al programa anterior, considerándolo como macro, lo notaremos: $$V\leftarrow V_1 \cdot V_2$$ Como ejemplo, veamos como quedaría este programa si no hubiéramos usado la abreviatura (macro) de la suma. Obsérvese cómo ha habido que renombrar las variables y las etiquetas para que no coincidan con las que ya existen en las restantes líneas del programa: ```none Z2 <- X2 [B] IF Z2 != 0 GOTO A GOTO E [A] Z2 <- Z2 - 1 Z1 <- X1 Z3 <- Y [B2] IF Z3 != 0 A2 GOTO E2 [A2] Z3 <- Z3 - 1 Z1 <- Z1 + 1 GOTO B2 [E2] Y <- Z1 GOTO B ``` Evidentemente, el programa anterior se podría seguir expandiendo, sustituyendo las asignaciones por bloques que realicen esa operación (que ya hemos visto), y las ramificaciones incondicionales por el bloque correspondiente (teniendo cuidado siempre con las variables y etiquetas que se usen en la {\it expansión}). # Sintaxis de GOTO Demos ahora la definición formal del lenguaje GOTO. !!!def:Definición El lenguaje GOTO consta de: * Un símbolo que denominaremos_variable de salida_, y que denotaremos por $Y$, y dos conjuntos numerables de símbolos: $\{X_1,...,X_n,...\},\ \ \{Z_1,...,Z_n,...\}$ que denominaremos, respectivamente,_variables de entrada_ y _variables de trabajo o auxiliares_, respectivamente. * Un conjunto de símbolos, también numerable, distinto de los anteriores, y que denominaremos _etiquetas_: $\{A_1,B_1,C_1,D_1,E_1,A_2,...,E_2,...\}$ * Para cada variable de GOTO, $V$, y etiqueta, $L$, las siguientes expresiones son instrucciones: * $V \leftarrow V + 1$ * $V \leftarrow V - 1$ * $V\leftarrow V$ * $IF\ V \neq 0 \ GOTO\ L$ * Si $K$ es una etiqueta, e $I$ es una de las instrucciones anteriores, entonces la siguiente expresión es una instrucción: * $[K]\ I$ !!!def:Definición Un programa de GOTO es una sucesión finita de instrucciones con o sin etiquetas. Es decir, un programa, $P$, es una sucesión $I_1,...,I_k$, donde $I_j \in Ins$. Al número $k$ se le denomina la_longitud_ de $P$. !!!Note Tenemos que: * Como única salvedad, prohibiremos que la última instrucción de $P$ sea la instrucción $Y\leftarrow Y$, por motivos que veremos en temas posteriores. De hecho, debido a su interpretación (no tiene efecto), una instrucción de este tipo al final de un programa puede ser eliminada sin alterar el comportamiento de éste. * Un caso límite de programa es el programa vacío, es decir, el programa sin instrucciones, que se considera de longitud $0$. !!!def:Definición Para cada instrucción, $I$, de un programa, $P$, definimos $var(I)$ como: $$var(I)=V \mbox{ si } I\ \in \{V\leftarrow V,\ V\leftarrow V + 1,\ V \leftarrow V - 1,\ IF\ V \neq 0 \ GOTO \ L\}$$ El conjunto de variables del programa $P=I_1,...,I_k$ es: $$var(P)=\{var(I_j):\ j=1,...,k\}$$ !!!def:Definición Dado un programa, $P$, de GOTO, un estado de $P$ es un conjunto finito, GOTO, de pares ordenados, $\sigma \subseteq Var\times {\Bbb N}$, tal que para cada variable $V\in var(P)$ existe un único par $(V,m)\in \sigma$. Esencialmente, GOTO se puede ver como una función $\sigma:Var\ - \to {\Bbb N}$, con $var(P)\subseteq dom(\sigma)$. Como es habitual cuando tratamos con funciones, denotaremos por $\sigma(V)$ al único número natural tal que $(V,\sigma(V))\in \sigma$, y diremos que es el valor de $V$ en GOTO. Una forma de representar habitualmente los estados de un programa es como un conjunto finito de ecuaciones de la forma $V=m$. !!!Tip: Ejemplo Si $P$ es el programa del ejemplo 2, entonces $\{X=5,\ Y=7,\ Z=3\}$ es un estado de $P$ (aunque nunca se llegue a alcanzar), $\{X=5,\ Y=3,\ Z=3\}$ es otro estado; sin embargo, $\{X=5,\ Z=3\}$ y $\{X=5,\ X=3,\ Z=2,\ Y=0\}$ no son estados de $P$. !!!def:Definición Dado un programa, $P$, de longitud $n$, una descripción instantánea de $P$ es un par $(i,\sigma)$, donde GOTO es un estado de $P$, y $1\leq i \leq n+1$. Si $i=n+1$ diremos que $(i,\sigma)$ es terminal. Si $V \in var(P)$, el valor de $V$ en la descripción instantánea $s=(i,\sigma)$ es $\sigma(V)$, y se denota por $sigma(V)$. !!!def:Definición Sea $P=I_1,...,I_n$ un programa en GOTO. Dada un descripción instantánea no terminal, $s=(i,\sigma)$, definimos el sucesor de $sigma$ como la descripción instantánea $(j,\tau)$ dada como: * Caso 1: Si $I_i$ es $V\leftarrow V$, entonces $j=i+1$, y $\tau=\sigma$. * Caso 2: Si $I_i$ es $V\leftarrow V + 1$ entonces $j=i+1$ y $\tau(W)=\begin{cases} \sigma(V)+1& \mbox{si } W=V\\ \sigma(W) & \mbox{si } W \neq V\end{cases}$ * Caso 3: Si $I_i$ es $V\leftarrow V - 1$, entonces $j=i+1$ y $\tau(W)=\begin{cases} \sigma(W) & \mbox{si }W \neq V\\ 0 & \mbox{si } \sigma(V)=0\\ \sigma(V)-1 & \mbox{si } \sigma(V)\neq 0\end{cases}$. * Caso 4: Si $I_i$ es $IF\ V\neq 0\ GOTO\ L$, entonces $\tau=\sigma$ y * Si $\sigma(V)=0$ entonces $j=i+1$. * Si $\sigma(V)\neq 0$ y existe una instrucción de $P$ con la etiqueta $L$, entonces $j=\min\{i:\ I_i\mbox{ tiene \(L$ como etiqueta}\}\) * En otro caso $j=n+1$. Para instrucciones etiquetadas la definición es la misma. !!!def:Definición Una computación de un programa $P$ es una sucesión finita $s_1,...,s_k$ de descripciones instantáneas tal que: * Para cada $i=1,...,k-1$, $s_{i+1}$ es el sucesor de $s_i$. * $s_k$ es una descripción instantánea terminal. * $s_1=(1,\sigma)$, donde $s$ es un estado de $P$. !!!Tip: Ejemplo Para el ejemplo 2 visto anteriormente, si tomamos $s_1=(1,\{X=3,\ Y=0 ,\ Z=0\})$, la computación que se obtiene es: ```none IF X != 0 GOTO B Z <- Z + 1 IF Z != 0 GOTO E [B] X <- X - 1 Y <- Y + 1 IF X != 0 GOTO B ``` $$\begin{array}{l} s_1=(1,\{X=3,\ Y=0,\ Z=0\})\\ s_2=(4,\{X=3,\ Y=0,\ Z=0\})\\ s_3=(5,\{X=2,\ Y=0,\ Z=0\})\\ s_4=(6,\{X=2,\ Y=1,\ Z=0\})\\ s_5=(1,\{X=2,\ Y=1,\ Z=0\})\\ s_6=(4,\{X=2,\ Y=1,\ Z=0\})\\ s_7=(5,\{X=1,\ Y=1,\ Z=0\})\\ s_8=(6,\{X=1,\ Y=2,\ Z=0\})\\ s_9=(1,\{X=1,\ Y=2,\ Z=0\})\\ s_{10}=(4,\{X=1,\ Y=2,\ Z=0\})\\ s_{11}=(5,\{X=0,\ Y=2,\ Z=0\})\\ s_{12}=(6,\{X=0,\ Y=3,\ Z=0\})\\ s_{13}=(7,\{X=0,\ Y=3,\ Z=0\})\end{array}$$ !!!def:Definición Dado un programa $P$, y $k\geq 1$, $P$ define una función $\psi_P^{(k)}: {\Bbb N}^k - \to {\Bbb N}$ como sigue: Dado $(n_1,...,n_k) \in {\Bbb N}^k$, sea $s$ el estado de $P$ definido por: * $\sigma(X_i)=n_i,\ 1\leq i \leq k$. * $\sigma(Y)=0$. * $\sigma(V)=0,\ \forall\ V\in var(P),\ V \neq X_i\ (i=1,...,k)$. Sea $s_1=(1,\sigma)$. Distinguimos dos casos: * Caso 1: Existe una computación $s_1,...,s_r$ de $P$. Entonces $\psi_P^{(k)}(n_1,...,n_k) \downarrow$ y $\psi_P^{(k)}(n_1,...,n_k)=s_r(Y)$. * Caso 2: No existe una computación de $P$ cuya descripción instantánea inicial sea $s_i$. Entonces $\psi_P^{(k)}(n_1,...,n_k) \uparrow$. $\psi_P^{(k)}$ es la función $k$-aria calculada por el programa $P$. !!!def:Definición Diremos que una función $f:{\Bbb N}^k - \to {\Bbb N}$ es GOTO-computable si existe un programa $P$ de GOTO tal que $\psi_P^{(k)}=f$, es decir, $\forall \vec{x} \in {\Bbb N}^k,\ f(\vec{x})\simeq \psi_P^{(k)}(\vec{x})$ # Macros Sea $P$ un programa de GOTO que calcula una función $f:{\Bbb N}^k - \to {\Bbb N}$. Podemos suponer que $var(P)=\{Y,X_1,...,X_n,Z_1,...,Z_k\}$ y que todas las etiquetas que aparecen en $P$ son $E,A_1,...,A_r$. Cumpliéndose además que para cada instrucción de la forma $IF\ V\neq 0\ GOTO\ A_i$ existe otra instrucción en $P$ etiquetada por $A_i$. (En caso de que $P$ no verificase estas instrucciones podemos conseguir otro programa $P'$ a partir de él sustituyendo convenientemente las etiquetas que aparecen en $P$ y trabajaríamos con este nuevo programa $P'$, que calcula la misma función). Escribiremos este programa como $P=P(Y;X_1,...,X_n,Z_1,...,Z_k;E,A_1,...,A_r)$, para cada $m$ sea $$Q_m=P(Z_m;Z_{m+1},...,Z_{m+n},Z_{m+n+1},...,Z_{m+n+k};E_m,A_{m+1},...,A_{m+r})$$ el programa obtenido sustituyendo convenientemente variables y etiquetas. Ahora podemos definir el siguiente procedimiento para la expansión de la macro: $$W \leftarrow f(V_1,...,V_n)$$ (donde $W,V_1,...,V_n$ son variables distintas entre sí). Cuando aparece la macro anterior en un programa, deberá sustituirse por: ```none Zm <- 0 Z_{m+1} <- V1 ... Z_{m+n} <- Vn Z_{m+n+1} <- 0 ... Z_{m+n+k} <- 0 Q_m [Em] W <- Z_m ``` Siendo $m \in {\Bbb N}$ tal que no existe $j\geq m$ tal que $X_j$ o $Z_j$ esté entre las variables del programa en que estamos realizando la expansión de la macro, ni $A_j$ entre las etiquetas. !!!note Tenemos que: * La expansión anterior evidentemente no es válida para el caso en que la macro sea la de asignación, en cuyo caso habrá que usar la vista en el ejemplo 4, teniendo presente las observaciones hechas con respecto al uso de las etiquetas y variables auxiliares. * La expansión de macros debe llevarse a cabo de modo que cada vez sólo se realice sobre una macro. * Las variables de la macro $W\leftarrow f(V_1,...,V_n)$ son distintas entre sí. Es peligroso identificar variables. * Por ejemplo, el siguiente programa, que usa la macro de asignación, calcula la función $f(x)=2x+1$, junto a él, damos su expansión: ```none Z <- X Y <- Y + 1 [A1] IF Z != 0 GOTO A2 GOTO E [A2] Y <- Y + 1 Y <- Y + 1 Z <- Z - 1 GOTO A1 ... [A3] IF X != 0 GOTO B1 GOTO C1 [B1] X <- X - 1 Z <- Z + 1 Z2 <- Z2 + 1 GOTO A3 [C1] IF Z2 != 0 GOTO D1 GOTO E2 [D1] Z2 <- Z2 - 1 X <- X + 1 GOTO C1 [E2] Y <- Y + 1 [A1] IF Z != 0 GOTO A2 GOTO E [A2] Y <- Y + 1 Y <- Y + 1 Z <- Z - 1 GOTO A1 ``` Si $p(x_1,...,x_n)$ es un predicado GOTO-computable podemos considerar la macro: $$IF\ p(V_1,\dots,V_n)\ GOTO\ L$$ ```none W <- p(V1,...,Vn) IF W != 0 GOTO L ``` (insert menu.md.html here)