« TC: Preliminares « || Inicio || » TC: Funciones Recursi… »

TC: Programas y Funciones Computables

Última modificación: 9 de Noviembre de 2017, y ha tenido 14 vistas

Etiquetas utilizadas: || || ||

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:

  • 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\)

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:

Ejemplo 1: Sea \(P\) el programa

[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\).

Ejemplo 2: Veamos ahora un programa que calcula la función identidad sobre \({\Bbb N}\), es decir \(P(n)=n\)

    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

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:

Zk <- Zk + 1
IF Zk != 0 GOTO L

donde la variable \(Z_k\) no se está utilizando.

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

[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\).

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

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

Ejemplo 5: La función suma:

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

Ejercicio 6: A partir de la función anterior es fácil definir la función producto como:

    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:

     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.

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 etiquetta, \(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\)

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

Nota:

  • 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\).

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\}\)

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

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

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

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.

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

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:

    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}$$

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

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:

     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.

Notas:

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

Nota: Si \(p(x_1,...,x_n)\) es un predicado GOTO-computable podemos considerar la macro:

\(IF\ p(V_1,\dots,V_n)\ GOTO\ L\)

W <- p(V1,...,Vn)
IF W != 0 GOTO L

« TC: Preliminares « || Inicio || » TC: Funciones Recursi… »