El paradigma imperativo de Neumann: El lenguaje \mathcal{S}^{\Sigma}

En esta sección daremos una modelización matemática del concepto de función \(\Sigma\)-efectivamente computable utilizando un lenguaje de programación teórico el cual depende del alfabeto \(\Sigma\). Lo llamaremos \(\mathcal{S}^{\Sigma}\) a dicho lenguaje. Dado que fue el matemático Von Neumann quien contribuyo al desarrollo de la primera computadora de propósito general (es decir a la cual se le pueden hacer correr programas tal como a las computadoras actuales), nos referiremos a este paradigma de computabilidad efectiva como el paradigma de Von Neumann. También lo llamaremos algunas veces el paradigma imperativo.

4.3.1 Sintaxis de \(\mathcal{S}^{\Sigma}\)

Recordemos que llamamos numerales a los siguientes símbolos \[0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\] Usaremos \(Num\) para denotar el conjunto de numerales. Nótese que \(Num\cap\omega=\emptyset\). Sea \(Sig:Num^{\ast}\rightarrow Num^{\ast}\) definida de la siguiente manera \[\begin{aligned} Sig(\varepsilon) & =1\\ Sig(\alpha0) & =\alpha1\\ Sig(\alpha1) & =\alpha2\\ Sig(\alpha2) & =\alpha3\\ Sig(\alpha3) & =\alpha4\\ Sig(\alpha4) & =\alpha5\\ Sig(\alpha5) & =\alpha6\\ Sig(\alpha6) & =\alpha7\\ Sig(\alpha7) & =\alpha8\\ Sig(\alpha8) & =\alpha9\\ Sig(\alpha9) & =Sig(\alpha)0 \end{aligned}\] Definamos \(Dec:\omega\rightarrow Num^{\ast}\) de la siguiente manera \[\begin{aligned} Dec(0) & =\varepsilon\\ Dec(n+1) & =Sig(Dec(n)) \end{aligned}\] Nótese que para \(n\in\mathbf{N}\), la palabra \(Dec(n)\) es la notación usual decimal de \(n\). Para hacer mas ágil la notación escribiremos \(\bar{n}\) en lugar de \(Dec(n)\). Nótese que, en virtud de esta convención notacional se tiene que \(Dec=\lambda n[\bar{n}]\). La sintaxis de \(\mathcal{S}^{\Sigma}\) será dada utilizando solo símbolos del alfabeto \(\Sigma\cup\Sigma_{p}\), donde \[\Sigma_{p}=Num\cup\left\{ \leftarrow,+,\dot{-},.,\neq,^{\curvearrowright},\varepsilon,\mathrm{N},\mathrm{K},\mathrm{P},\mathrm{L},\mathrm{I},\mathrm{F},\mathrm{G},\mathrm{O},\mathrm{T},\mathrm{B},\mathrm{E},\mathrm{S}\right\} .\] Cabe aclarar que la palabra de longitud \(0\) no es un elemento de \(\Sigma_{p}\) sino que la letra griega \(\varepsilon\) que usualmente denota esta palabra, lo es. También nótese que en \(\Sigma_{p}\) hay símbolos que a veces representan operaciones como por ejemplo \(+\) , \(^{\curvearrowright}\) y \(\dot{-}\), pero debería quedar claro que en \(\Sigma_{p}\) están los símbolos \(+\), \(^{\curvearrowright}\) y \(\dot{-}\) y no las operaciones que ellos usualmente denotan.

Las palabras de la forma \(\mathrm{N}\bar{k}\) con \(k\in\mathbf{N}\), son llamadas variables numéricas de \(\mathcal{S}^{\Sigma}\). Las palabras de la forma \(\mathrm{P}\bar{k}\) con \(k\in\mathbf{N}\), son llamadas variables alfabéticas de \(\mathcal{S}^{\Sigma}\). Las palabras de la forma \(\mathrm{L}\bar{k}\) con \(k\in\mathbf{N}\), son llamadas labels de \(\mathcal{S}^{\Sigma}\).

Una instrucción básica de \(\mathcal{S}^{\Sigma}\) es una palabra de \((\Sigma\cup\Sigma_{p})^{\ast}\) la cual es de alguna de las siguientes formas

donde \(a\in\Sigma\) y \(k,n\in\mathbf{N}\). Como puede observarse para que las instrucciones básicas sean mas legibles usamos espacios entre ciertos símbolos. Por ejemplo, hemos escrito \(\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{k}+1\) pero en realidad nos referimos a la palabra \[\mathrm{N}\bar{k}\mathrm{\leftarrow}\text{N}\bar{k}\mathrm{+1}\] cuya longitud es \(2\left\vert \bar{k}\right\vert +5\). Otro ejemplo, hemos escrito \(\mathrm{IF}\;\mathrm{P}\bar{k}\;\mathrm{BEGINS}\;a\;\mathrm{GOTO}\;\mathrm{L}\bar{n}\) pero en realidad nos referíamos a la palabra \(\mathrm{IFP}\bar{k}\mathrm{BEGINS}a\mathrm{GOTOL}\bar{n}\) cuya longitud es \(\left\vert \bar{k}\right\vert +\left\vert \bar{n}\right\vert +15\).

Una instrucción de \(\mathcal{S}^{\Sigma}\) es ya sea una instrucción básica de \(\mathcal{S}^{\Sigma}\) o una palabra de la forma \(\alpha I\), donde \(\alpha\in\{\mathrm{L}\bar{n}:n\in\mathbf{N}\}\) y \(I\) es una instrucción básica de \(\mathcal{S}^{\Sigma}\). Usaremos \(\mathrm{Ins}^{\Sigma}\) para denotar el conjunto de todas las instrucciones de \(\mathcal{S}^{\Sigma}\). Cuando la instrucción \(I\) es de la forma \(\mathrm{L}\bar{n}J\) con \(J\) una instrucción básica, diremos que \(\mathrm{L}\bar{n}\) es el label de \(I\). Damos a continuación, a modo de ejemplo, la interpretación intuitiva asociada a ciertas instrucciones básicas de \(\mathcal{S}^{\Sigma}\): \[\begin{aligned} \text{INSTRUCCION} & :\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{k}\dot{-}1\\ \text{INTERPRETACION} & :\begin{array}[t]{c} \text{Si el contenido de }\mathrm{N}\bar{k}\text{ es }0\text{ dejarlo sin modificar; en}\\ \text{caso contrario disminuya en 1 el contenido de }\mathrm{N}\bar{k}\; \end{array}\\ \text{INSTRUCCION} & :\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{n}\\ \text{INTERPRETACION} & :\begin{array}[t]{l} \text{Copiar en }\mathrm{N}\bar{k}\text{ el contenido de }\mathrm{N}\bar{n}\text{ (sin modificar el}\\ \text{contenido de }\mathrm{N}\bar{n}\text{)} \end{array}\\ \text{INSTRUCCION} & :\mathrm{P}\bar{k}\leftarrow^{\curvearrowright}\mathrm{P}\bar{k}\\ \text{INTERPRETACION} & :\begin{array}[t]{l} \text{Si el contenido de }\mathrm{P}\bar{k}\text{ es }\varepsilon\text{ dejarlo sin modificar;}\\ \text{en caso contrario remueva el 1er simbolo del}\\ \text{contenido de }\mathrm{P}\bar{k} \end{array} \end{aligned}\] \[\begin{aligned} \text{INSTRUCCION} & :\mathrm{P}\bar{k}\leftarrow\mathrm{P}\bar{k}.a\\ \text{INTERPRETACION} & :\begin{array}[t]{l} \text{Modificar el contenido de }\mathrm{P}\bar{k}\text{ agregandole}\\ \text{el simbolo }a\text{ a la derecha} \end{array}\\ \text{INSTRUCCION} & :\mathrm{IF}\;\mathrm{P}\bar{k}\;\mathrm{BEGINS}\;a\;\mathrm{GOTO}\;\mathrm{L}\bar{m}\\ \text{INTERPRETACION} & :\begin{array}[t]{l} \text{Si el contenido de }\mathrm{P}\bar{k}\text{ comiensa con }a,\text{ejecute}\\ \text{la primer instruccion con label }\mathrm{L}\bar{m}\text{; en caso}\\ \text{contrario ejecute la siguiente instruccion} \end{array} \end{aligned}\]

Un programa de \(\mathcal{S}^{\Sigma}\) es una palabra de la forma \[I_{1}I_{2}...I_{n}\] donde \(n\geq1\), \(I_{1},...,I_{n}\in\mathrm{Ins}^{\Sigma}\) y además se cumple la siguiente propiedad, llamada la ley de los GOTO,

Usaremos \(\mathrm{Pro}^{\Sigma}\) para denotar el conjunto de todos los programas de \(\mathcal{S}^{\Sigma}\). Como es usual cuando escribamos un programa lo haremos linea por linea, con la finalidad de que sea mas legible. Por ejemplo, escribiremos \[\begin{array}{ll} \mathrm{L}2 & \mathrm{N}12\leftarrow\mathrm{N}12\dot{-}1\\ & \mathrm{P}1\leftarrow\text{ }^{\curvearrowright}\mathrm{P}1\\ & \mathrm{IF\;N}12\neq0\;\mathrm{GOTO}\;\mathrm{L}2 \end{array}\] en lugar de \[\mathrm{L}2\mathrm{N}12\mathrm{\leftarrow}\text{N}12\mathrm{\dot{-}}1\mathrm{P}1\mathrm{\leftarrow}^{\curvearrowright}\mathrm{P}1\mathrm{IFN}12\mathrm{\neq}0\mathrm{GOTOL}2\] Un importante resultado es el siguiente lema que garantiza que los programas pueden ser parseados en forma única como concatenación de instrucciones.

4.43. Se tiene que:

adhocprefix(a)adhocsufix Si \(I_{1}...I_{n}=J_{1}...J_{m}\), con \(I_{1},...,I_{n},J_{1},...,J_{m}\in\mathrm{Ins}^{\Sigma}\), entonces \(n=m\) y \(I_{j}=J_{j}\) para cada \(j\geq1\).
adhocprefix(b)adhocsufix Si \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\), entonces existe una única sucesión de instrucciones \(I_{1},...,I_{n}\) tal que \(\mathcal{P}=I_{1}...I_{n}\)

Proof. (a) Supongamos \(I_{n}\neq J_{m}\). Ya que \(I_{1}...I_{n}=J_{1}...J_{m}\) tenemos que \(I_{n}\) es un tramo final propio de \(J_{m}\) o \(J_{m}\) es un tramo final propio de \(I_{n}.\) Supongamos \(I_{n}\) es un tramo final propio de \(J_{m}.\) Notar que entonces \(n>1\). Es fácil ver que entonces ya sea \(J_{m}=\mathrm{L}\bar{u}I_{n}\) para algún \(u\in\mathbf{N}\), o \(I_{n}\) es de la forma \(\mathrm{GOTO}\;\mathrm{L}\bar{n}\) y \(J_{m}\) es de la forma \(\alpha\mathrm{IF}\;\mathrm{P}\bar{k}\;\mathrm{BEGINS}\;a\;\mathrm{GOTO}\;\mathrm{L}\bar{n}\) con \(\alpha\in\{\mathrm{L}\bar{n}:n\in\mathbf{N}\}\cup\{\varepsilon\}\). El segundo caso no puede darse porque entonces el anteúltimo símbolo de \(I_{n-1}\) debería ser \(\mathrm{S}\) lo cual no sucede para ninguna instrucción. O sea que \(J_{m}=\mathrm{L}\bar{u}I_{n}\) para algún \(u\in\mathbf{N}\), por lo cual tenemos que \[I_{1}...I_{n}=J_{1}...J_{m-1}\mathrm{L}\bar{u}I_{n}\] Pero esto nos dice que

Es fácil deducir entonces que \(\mathrm{L}\bar{u}\) es tramo final de \(I_{n-1}\) y por lo tanto \(\mathrm{GOTO}\;\mathrm{L}\bar{u}\) es tramo final de \(I_{n-1}\). Pero entonces por (*), tenemos que \(\mathrm{GOTO}\) es tramo final de \(J_{1}...J_{m-1}\), lo cual es imposible. Hemos llegado a una contradicción lo cual nos dice que \(I_{n}\) no es un tramo final propio de \(J_{m}.\) Por simetría tenemos también que \(J_{m}\) no es un tramo final propio de \(I_{n}\), arribando a un absurdo. O sea que \(I_{n}=J_{m}\). Usando un razonamiento inductivo obtenemos que \(n=m\) y \(I_{j}=J_{j}\) para cada \(j\geq1\).

(b) del lema anterior nos dice que dado un programa \(\mathcal{P}\), tenemos unívocamente determinados \(n(\mathcal{P})\in\mathbf{N}\) y \(I_{1}^{\mathcal{P}},...,I_{n(\mathcal{P})}^{\mathcal{P}}\in\mathrm{Ins}^{\Sigma}\) tales que \(\mathcal{P}=I_{1}^{\mathcal{P}}...I_{n(\mathcal{P})}^{\mathcal{P}}\). Definamos también \[I_{i}^{\mathcal{P}}=\varepsilon\] cuando \(i=0\) o \(i>n(\mathcal{P})\). Nótese que las expresiones \(n(\alpha)\) y \(I_{i}^{\alpha}\) están definidas solo cuando \(\alpha\) es un programa (y \(i\) es un elemento de \(\omega\)), es decir, cierta palabra del alfabeto \(\Sigma\cup\Sigma_{p}\). O sea que cuando usemos notación lambda que involucre dichas expresiones, el alfabeto respecto del cual usaremos dicha notación será \(\Sigma\cup\Sigma_{p}\). Esto nos dice entonces que \(\lambda\alpha[n(\alpha)]\) tiene dominio igual a \(\mathrm{Pro}^{\Sigma}\subseteq(\Sigma\cup\Sigma_{p})^{\ast}\) y \(\lambda i\alpha[I_{i}^{\alpha}]\) tiene dominio igual a \(\omega\times\mathrm{Pro}^{\Sigma}\). Para hacer mas sugestiva la notación a veces escribiremos \(\lambda\mathcal{P}[n(\mathcal{P})]\) y \(\lambda i\mathcal{P}[I_{i}^{\mathcal{P}}]\) en lugar de \(\lambda\alpha[n(\alpha)]\) y \(\lambda i\alpha[I_{i}^{\alpha}]\).

Será necesaria la función \(Bas:\mathrm{Ins}^{\Sigma}\rightarrow(\Sigma\cup\Sigma_{p})^{\ast}\), dada por \[Bas(I)=\left\{ \begin{array}{ccl} J & & \text{si }I\text{ es de la forma }\mathrm{L}\bar{k}J\text{, con }k\in\mathbf{N}\text{ y }J\in\mathrm{Ins}^{\Sigma}\\ I & & \text{caso contrario} \end{array}\right.\]

4.3.2 Semántica de \(\mathcal{S}^{\Sigma}\)

Definamos \[\begin{aligned} \omega^{\left[\mathbf{N}\right]} & =\left\{ (s_{1},s_{2},...)\in\omega^{\mathbf{N}}:\text{ hay }n\in\mathbf{N}\text{ tal que }s_{i}=0,\text{para }i\geq n\right\} \\ \Sigma^{\ast\left[\mathbf{N}\right]} & =\left\{ (\sigma_{1},\sigma_{2},...)\in\Sigma^{\ast\mathbf{N}}:\text{ hay }n\in\mathbf{N}\text{ tal que }\sigma_{i}=\varepsilon,\text{para }i\geq n\right\} . \end{aligned}\] Asumiremos siempre que en una computación vía un programa de \(\mathcal{S}^{\Sigma}\), todas excepto una cantidad finita de las variables numéricas tienen el valor \(0\) y todas excepto una cantidad finita de las variables alfabéticas tienen el valor \(\varepsilon\). Esto no quita generalidad a nuestra modelización del funcionamiento de los programas ya que todo programa envuelve una cantidad finita de variables.

Un estado es un par \[(\vec{s},\vec{\sigma})=((s_{1},s_{2},...),(\sigma_{1},\sigma_{2},...))\in\omega^{\left[\mathbf{N}\right]}\times\Sigma^{\ast\left[\mathbf{N}\right]}.\] Si \(i\geq1\), entonces diremos que \(s_{i}\) es el contenido o valor de la variable \(\mathrm{N}\bar{\imath}\) en el estado \((\vec{s},\vec{\sigma})\) y \(\sigma_{i}\) es el contenido o valor de la variable \(\mathrm{P}\bar{\imath}\) en el estado \((\vec{s},\vec{\sigma})\). Intuitivamente hablando, un estado es un par de infinituplas que contiene la información de que valores tienen alojados las distintas variables.

Imaginemos que corremos un programa \(\mathcal{P}\) partiendo de un estado inicial \((\vec{s},\vec{\sigma})\). Por supuesto la primera instrucción a realizar será \(I_{1}^{\mathcal{P}}\) pero, dado que \(I_{1}^{\mathcal{P}}\) puede ser de tipo GOTO, la segunda instrucción que realizaremos puede no ser \(I_{2}^{\mathcal{P}}\). Es decir en cada paso iremos decidiendo en función de la instrucción ejecutada cual es la siguiente instrucción a realizar. O sea que mientras corremos \(\mathcal{P}\), en cada paso la información importante a tener en cuenta es, por una parte, cuales son los valores que tienen cada una de las variables y, por otra parte, cual es la instrucción que nos tocara realizar a continuación. Esto da lugar al concepto de descripción instantánea, a saber, un objeto matemático que describe en un instante dado de la computación cuales son los valores de las variables y cual es la instrucción que se debe realizar en el instante siguiente. Mas formalmente una descripción instantánea es una terna \((i,\vec{s},\vec{\sigma})\) tal que \((\vec{s},\vec{\sigma})\) es un estado e \(i\in\omega\). Es decir que \(\omega\times\omega^{\left[\mathbf{N}\right]}\times\Sigma^{\ast\left[\mathbf{N}\right]}\) es el conjunto formado por todas las descripciones instantáneas. Intuitivamente hablando, cuando \(i\in\{1,...,n(\mathcal{P})\}\), la descripción instantánea \((i,\vec{s},\vec{\sigma})\) nos dice que las variables están en el estado \((\vec{s},\vec{\sigma})\) y que la instrucción que debemos realizar es \(I_{i}^{\mathcal{P}}\). Dado que será conveniente para simplificar el tratamiento formal, nos abstraeremos un poco y cuando \(i=0\) o \(i>n(\mathcal{P})\) pensaremos también que la descripción instantánea \((i,\vec{s},\vec{\sigma})\) nos dice que las variables están en el estado \((\vec{s},\vec{\sigma})\) y que debemos realizar \(I_{i}^{\mathcal{P}}=\varepsilon\) (aunque por supuesto no podremos realizarla ya que no es una instrucción).

Dado un programa \(\mathcal{P}\) definiremos a continuación una función \[S_{\mathcal{P}}:\omega\times\omega^{\left[\mathbf{N}\right]}\times\Sigma^{\ast\left[\mathbf{N}\right]}\rightarrow\omega\times\omega^{\left[\mathbf{N}\right]}\times\Sigma^{\ast\left[\mathbf{N}\right]}\] la cual le asignara a una descripción instantánea \((i,\vec{s},\vec{\sigma})\) la descripción instantánea sucesora de \((i,\vec{s},\vec{\sigma})\) con respecto a \(\mathcal{P}\). Cuando \(i\in\{1,...,n(\mathcal{P})\}\), intuitivamente hablando, \(S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})\) será la descripción instantánea que resulta luego de realizar \(I_{i}^{\mathcal{P}}\) estando en el estado \((\vec{s},\vec{\sigma})\). Cuando \(i=0\) o \(i>n(\mathcal{P})\) definiremos \(S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i,\vec{s},\vec{\sigma})\), lo cual es bastante intuitivo ya que si estamos en estado \((\vec{s},\vec{\sigma})\) y debemos realizar \(I_{i}^{\mathcal{P}}=\varepsilon\), dado que \(\varepsilon\) no es una instrucción y por lo tanto no la podremos realizar, seguiremos en el mismo estado y teniendo que realizar \(I_{i}^{\mathcal{P}}\).

Para darle una semántica mas unificada al concepto de descripción instantánea sucesora debemos crear un nuevo verbo. El verbo "realizarp". Dada una actividad A, diremos que un individuo P realizap la actividad A, si P realiza A, en caso de que pueda hacerlo. O sea realizarp una actividad es realizarla si se puede.

Para dar otro ejemplo de este tipo de verbos, consideremos el verbo "comprarp", es decir "comprar si se puede". Un hijo le pide a su padre que le compre un determinado juguete y el padre le dice "si, hijo mio, te lo voy a comprarp". Luego el padre es despedido de su empleo y su situación económica hace que no le sea posible comprar dicho juguete. Sin embargo el padre no mintió ya que si bien no compro dicho juguete, él si lo comprop.

Con este verbo podemos describir intuitivamente \(S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})\): \[\begin{aligned} S_{\mathcal{P}}(i,\vec{s},\vec{\sigma}) & =\mathrm{desc\ inst\ que\ resulta\ luego\ de}\\ & \mathrm{rea}\text{l}\mathrm{izarp\ }I_{i}^{\mathcal{P}}\text{, estando en estado }(\vec{s},\vec{\sigma}) \end{aligned}\] Ahora sí, daremos la definición matemática de \(S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})\), según se den distintos casos posibles.

Caso \(i\notin\{1,...,n(\mathcal{P})\}\). Entonces \(S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i,\vec{s},\vec{\sigma})\)

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{k}\dot{-}1.\) Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,(s_{1},...,s_{k-1},s_{k}\dot{-}1,s_{k+1},...),\vec{\sigma})\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{k}+1.\) Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,(s_{1},...,s_{k-1},s_{k}+1,s_{k+1},...),\vec{\sigma})\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{n}\). Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,(s_{1},...,s_{k-1},s_{n},s_{k+1},...),\vec{\sigma})\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{N}\bar{k}\leftarrow0.\) Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,(s_{1},...,s_{k-1},0,s_{k+1},...),\vec{\sigma})\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{IF}\) \(\mathrm{N}\bar{k}\) \(\neq0\) \(\mathrm{GOTO}\) \(\mathrm{L}\bar{m}.\) Entonces tenemos dos subcasos.

Subcaso a. El valor de \(\mathrm{N}\bar{k}\) en \((\vec{s},\vec{\sigma})\) es 0. Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,\vec{s},\vec{\sigma})\]

Subcaso b. El valor de \(\mathrm{N}\bar{k}\) en \((\vec{s},\vec{\sigma})\) es no nulo. Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(\min\{l:I_{l}^{\mathcal{P}}\ \mathrm{tiene\ label\ L}\bar{m}\},\vec{s},\vec{\sigma})\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{P}\bar{k}\leftarrow\) \(^{\curvearrowright}\mathrm{P}\bar{k}.\) Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,\vec{s},(\sigma_{1},...,\sigma_{k-1},^{\curvearrowright}\sigma_{k},\sigma_{k+1},...))\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{P}\bar{k}\leftarrow\mathrm{P}\bar{k}.a\). Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,\vec{s},(\sigma_{1},...,\sigma_{k-1},\sigma_{k}a,\sigma_{k+1},...))\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{P}\bar{k}\leftarrow\mathrm{P}\bar{n}\). Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,\vec{s},(\sigma_{1},...,\sigma_{k-1},\sigma_{n},\sigma_{k+1},...))\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{P}\bar{k}\leftarrow\varepsilon.\) Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,\vec{s},(\sigma_{1},...,\sigma_{k-1},\varepsilon,\sigma_{k+1},...))\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{IF}\;\mathrm{P}\bar{k}\;\mathrm{BEGINS}\;a\;\mathrm{GOTO}\;\mathrm{L}\bar{m}.\) Entonces tenemos dos subcasos.

Subcaso a. El valor de \(\mathrm{P}\bar{k}\) en \((\vec{s},\vec{\sigma})\) comienza con \(a\). Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(\min\{l:I_{l}^{\mathcal{P}}\ \mathrm{tiene\ label\ L}\bar{m}\},\vec{s},\vec{\sigma})\]

Subcaso b. El valor de \(\mathrm{P}\bar{k}\) en \((\vec{s},\vec{\sigma})\) no comienza con \(a\). Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,\vec{s},\vec{\sigma})\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{GOTO}\;\mathrm{L}\bar{m}\). Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(\min\{l:I_{l}^{\mathcal{P}}\ \mathrm{tiene\ label\ L}\bar{m}\},\vec{s},\vec{\sigma})\]

Caso \(Bas(I_{i}^{\mathcal{P}})=\mathrm{SKIP}\). Entonces \[S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})=(i+1,\vec{s},\vec{\sigma})\]

4.3.2.1 La computación partiendo de un estado

Dado un programa \(\mathcal{P}\) y un estado \((\vec{s},\vec{\sigma})\) a la infinitupla \[((1,\vec{s},\vec{\sigma}),S_{\mathcal{P}}(1,\vec{s},\vec{\sigma}),S_{\mathcal{P}}(S_{\mathcal{P}}(1,\vec{s},\vec{\sigma})),S_{\mathcal{P}}(S_{\mathcal{P}}(S_{\mathcal{P}}(1,\vec{s},\vec{\sigma}))),...)\] la llamaremos la computación de \(\mathcal{P}\) partiendo del estado \((\vec{s},\vec{\sigma})\). Diremos que \[\overset{t\text{ veces}}{\overbrace{S_{\mathcal{P}}(...S_{\mathcal{P}}(S_{\mathcal{P}}(}}1,\vec{s},\vec{\sigma}))...)\] es la descripción instantánea obtenida luego de \(t\) pasos, partiendo del estado \((\vec{s},\vec{\sigma})\). Si \[\overset{t\text{ veces}}{\overbrace{S_{\mathcal{P}}(...S_{\mathcal{P}}(S_{\mathcal{P}}(}}1,\vec{s},\vec{\sigma}))...)=(j,\vec{u},\vec{\eta})\] diremos que \((\vec{u},\vec{\eta})\) es el estado obtenido luego de \(t\) pasos, partiendo del estado \((\vec{s},\vec{\sigma})\).

Es claro que en la infinitupla de mas arriba esta toda la información de la "corrida" del programa \(\mathcal{P}\) cuando partimos del estado \((\vec{s},\vec{\sigma})\). Veamos un ejemplo. Sea \(\Sigma=\{\blacktriangle,\#\}\) y sea \(\mathcal{P}\) el siguiente programa \[\begin{array}{ll} \mathrm{L}3 & \mathrm{N}4\leftarrow\mathrm{N}4+1\\ & \mathrm{P}1\leftarrow\ ^{\curvearrowright}\mathrm{P}1\\ & \mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3\\ & \mathrm{P}3\leftarrow\mathrm{P}3.\# \end{array}\] Supongamos que tomamos \((\vec{s},\vec{\sigma})\) igual al estado \[\left((2,1,0,5,3,0,0,0,...),(\#\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...)\right)\] Tendremos entonces que la computación de \(\mathcal{P}\) partiendo del estado \((\vec{s},\vec{\sigma})\) es la infinitupla formada por la siguiente sucesión (de arriba hacia abajo) de descripciones instantáneas: \[\begin{gathered} (1,(2,1,0,5,3,0,0,0,...),(\#\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{1}^{\mathcal{P}}=\mathrm{N}4\leftarrow\mathrm{N}4+1\text{ obtenemos}\\ (2,(2,1,0,6,3,0,0,0,...),(\#\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{2}^{\mathcal{P}}=\mathrm{P}1\leftarrow\ ^{\curvearrowright}\mathrm{P}1\text{ obtenemos}\\ (3,(2,1,0,6,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{3}^{\mathcal{P}}=\mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3\text{ obtenemos}\\ (1,(2,1,0,6,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{1}^{\mathcal{P}}=\mathrm{N}4\leftarrow\mathrm{N}4+1\text{ obtenemos}\\ (2,(2,1,0,7,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{2}^{\mathcal{P}}=\mathrm{P}1\leftarrow\ ^{\curvearrowright}\mathrm{P}1\text{ obtenemos}\\ (3,(2,1,0,7,3,0,0,0,...),(\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{3}^{\mathcal{P}}=\mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3\text{ obtenemos}\\ (4,(2,1,0,7,3,0,0,0,...),(\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{4}^{\mathcal{P}}=\mathrm{P}3\leftarrow\mathrm{P}3.\#\text{ obtenemos}\\ (5,(2,1,0,7,3,0,0,0,...),(\#\#,\varepsilon,\blacktriangle\blacktriangle\#,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{intentando realizar }I_{5}^{\mathcal{P}}=\varepsilon\text{ obtenemos}\\ (5,(2,1,0,7,3,0,0,0,...),(\#\#,\varepsilon,\blacktriangle\blacktriangle\#,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{intentando realizar }I_{5}^{\mathcal{P}}=\varepsilon\text{ obtenemos}\\ (5,(2,1,0,7,3,0,0,0,...),(\#\#,\varepsilon,\blacktriangle\blacktriangle\#,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{intentando realizar }I_{5}^{\mathcal{P}}=\varepsilon\text{ obtenemos}\\ (5,(2,1,0,7,3,0,0,0,...),(\#\#,\varepsilon,\blacktriangle\blacktriangle\#,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \vdots \end{gathered}\] Nótese que en este caso es natural decir que el programa \(\mathcal{P}\) se detiene, partiendo del estado inicial dado ya que llega a un punto en el que queda intentando realizar \(I_{n(\mathcal{P})+1}^{\mathcal{P}}\) lo cual no es una instrucción. Veamos un ejemplo de no detención. Sea \(\mathcal{Q}\) el siguiente programa \[\begin{array}{ll} \mathrm{L}3 & \mathrm{N}4\leftarrow\mathrm{N}4+1\\ & \mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3 \end{array}\] Supongamos que tomamos \((\vec{s},\vec{\sigma})\) igual al estado \[\left((2,1,0,5,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...)\right)\] Tendremos entonces que la computación de \(\mathcal{Q}\) partiendo del estado \((\vec{s},\vec{\sigma})\) es la siguiente sucesión (de arriba hacia abajo) de descripciones instantáneas: \[\begin{gathered} (1,(2,1,0,5,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{1}^{\mathcal{P}}=\mathrm{N}4\leftarrow\mathrm{N}4+1\text{ obtenemos}\\ (2,(2,1,0,6,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{2}^{\mathcal{P}}=\mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3\text{ obtenemos}\\ (1,(2,1,0,6,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{1}^{\mathcal{P}}=\mathrm{N}4\leftarrow\mathrm{N}4+1\text{ obtenemos}\\ (2,(2,1,0,7,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{2}^{\mathcal{P}}=\mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3\text{ obtenemos}\\ (1,(2,1,0,7,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{1}^{\mathcal{P}}=\mathrm{N}4\leftarrow\mathrm{N}4+1\text{ obtenemos}\\ (2,(2,1,0,8,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{2}^{\mathcal{P}}=\mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3\text{ obtenemos}\\ (1,(2,1,0,8,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{1}^{\mathcal{P}}=\mathrm{N}4\leftarrow\mathrm{N}4+1\text{ obtenemos}\\ (2,(2,1,0,9,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \text{realizando }I_{2}^{\mathcal{P}}=\mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3\text{ obtenemos}\\ (1,(2,1,0,9,3,0,0,0,...),(\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#,\varepsilon,\varepsilon,\varepsilon,...))\\ \vdots \end{gathered}\] Nótese que en este caso, es claro que el programa \(\mathcal{Q}\) no se detiene partiendo del estado inicial dado ya que sigue indefinidamente realizando instrucciones.

Definición matemática de detención

Ahora definiremos matemáticamente el concepto de detención. Cuando la primer coordenada de \[\overset{t\text{ veces}}{\overbrace{S_{\mathcal{P}}(...S_{\mathcal{P}}(S_{\mathcal{P}}(}}1,\vec{s},\vec{\sigma}))...)\] sea igual a \(n(\mathcal{P})+1\), diremos que \(\mathcal{P}\) se detiene (luego de \(t\) pasos), partiendo desde el estado \((\vec{s},\vec{\sigma})\). Si ninguna de las primeras coordenadas en la computación \[((1,\vec{s},\vec{\sigma}),S_{\mathcal{P}}(1,\vec{s},\vec{\sigma}),S_{\mathcal{P}}(S_{\mathcal{P}}(1,\vec{s},\vec{\sigma})),S_{\mathcal{P}}(S_{\mathcal{P}}(S_{\mathcal{P}}(1,\vec{s},\vec{\sigma}))),...)\] es igual a \(n(\mathcal{P})+1\), diremos que \(\mathcal{P}\) no se detiene partiendo del estado \((\vec{s},\vec{\sigma})\). Como puede observarse los programas de \(\mathcal{S}^{\Sigma}\) tienen una sola manera de detenerse, i.e. siempre que se detienen lo hacen habiendo realizado la última de sus instrucciones e intentando realizar la instrucción siguiente a su última instrucción.

Nótese que en los conceptos antes definidos por "1 paso" entendemos “aplicar una ves la función \(S_{\mathcal{P}}\)” y esto no siempre involucra “realizar una instrucción” ya que podría pasar que aplicáramos \(S_{\mathcal{P}}\) a una descripción instantánea cuya primer coordenada es \(n(\mathcal{P})+1\). Podemos redondear esta idea diciendo que “1 paso” equivale a "realizarp una instrucción", donde tal como se lo explico antes "realizarp" significa "realizar si se puede".

4.3.3 Funciones \(\Sigma\)-computables

Ahora que hemos definido matemáticamente la semántica de \(\mathcal{S}^{\Sigma}\) estamos en condiciones de definir el concepto de función \(\Sigma\)-computable, el cual será una modelización matemática del concepto de función \(\Sigma\)-efectivamente computable. Intuitivamente hablando una función será \(\Sigma\)-computable cuando haya un programa que la compute. Para precisar este concepto nos será útil la siguiente notación. Dados \(x_{1},...,x_{n}\in\omega\) y \(\alpha_{1},...,\alpha_{m}\in\Sigma^{\ast}\), con \(n,m\in\omega\), usaremos \[\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert\] para denotar el estado \[\left((x_{1},...,x_{n},0,...),(\alpha_{1},...,\alpha_{m},\varepsilon,...)\right)\] Esta notación requiere aclarar un poco como debe interpretarse en los casos limite, es decir cuando alguno de los números \(n,m\) es igual a \(0\). Nótese que por ejemplo \[\left\Vert x\right\Vert =\left((x,0,...),(\varepsilon,...)\right)\] (es el caso \(n=1\) y \(m=0\)). También \[\left\Vert \alpha\right\Vert =\left((0,...),(\alpha,\varepsilon,...)\right)\] (es el caso \(n=0\) y \(m=1\)). En el caso \(n=m=0\) pensaremos que \(x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\) se transforma en \(\lozenge\) por lo que se obtiene \[\left\Vert \lozenge\right\Vert =\left((0,...),(\varepsilon,...)\right)\] Además es claro que \[\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert =\left\Vert x_{1},...,x_{n},\overset{i}{\overbrace{0,...,0}},\alpha_{1},...,\alpha_{m},\overset{j}{\overbrace{\varepsilon,...,\varepsilon}}\right\Vert\] cualesquiera sean \(i,j\in\omega\).

Dado \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\), definamos para cada par \(n,m\geq0\), la función \(\Psi_{\mathcal{P}}^{n,m,\#}\) de la siguiente manera: \[\begin{array}{l} D_{\Psi_{\mathcal{P}}^{n,m,\#}}=\{(\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}:\mathcal{P}\text{ termina, partiendo del}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{estado }\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert \} \end{array}\] \[\begin{array}{l} \Psi_{\mathcal{P}}^{n,m,\#}(\vec{x},\vec{\alpha})=\text{valor de }\mathrm{N}1\text{ en el estado obtenido cuando }\mathcal{P}\text{ termina,}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{partiendo de }\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert \end{array}\] Análogamente definamos la función \(\Psi_{\mathcal{P}}^{n,m,\ast}\) de la siguiente manera: \[\begin{array}{l} D_{\Psi_{\mathcal{P}}^{n,m,\ast}}=\{(\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}:\mathcal{P}\text{ termina, partiendo del}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{estado }\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert \} \end{array}\] \[\begin{array}{l} \Psi_{\mathcal{P}}^{n,m,\ast}(\vec{x},\vec{\alpha})=\text{valor de }\mathrm{P}1\text{ en el estado obtenido cuando }\mathcal{P}\text{ termina,}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{partiendo de }\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert \end{array}\] Ahora sí daremos la definición precisa de función \(\Sigma\)-computable. Una función \(\Sigma\)-mixta \(f:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) será llamada \(\Sigma\)-computable si hay un programa \(\mathcal{P}\) tal que \(f=\Psi_{\mathcal{P}}^{n,m,\#}\). En tal caso diremos que la función \(f\) es computada por \(\mathcal{P}\) o que \(\mathcal{P}\) computa a \(f\). Análogamente una función \(\Sigma\)-mixta \(f:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) será llamada \(\Sigma\)-computable si hay un programa \(\mathcal{P}\) tal que \(f=\Psi_{\mathcal{P}}^{n,m,\ast}\). En tal caso diremos que la función \(f\) es computada por \(\mathcal{P}\) o que \(\mathcal{P}\) computa a \(f\).

Por supuesto para que el concepto de función \(\Sigma\)-computable tenga chance de ser una modelización adecuada del concepto de función \(\Sigma\)-efectivamente computable, tiene que ser cierto el siguiente resultado.

4.7 (Leibniz vence a Neumann). Si \(f\) es \(\Sigma\)-computable, entonces \(f\) es \(\Sigma\)-efectivamente computable.

Proof. Supongamos por ejemplo que \(f:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) es computada por \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\). Un procedimiento efectivo que compute a \(f\) puede consistir de realizar las sucesivas instrucciones de \(\mathcal{P}\) (partiendo de \(\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert\)) y eventualmente terminar en caso de que nos toque realizar la instrucción \(n(\mathcal{P})+1\), y dar como salida el contenido de la variable \(\mathrm{N}1\). Daremos a continuación una descripción mas detallada de dicho procedimiento.

Fijemos primero un número natural \(k\) que sea mayor que \(\max\{n,m\}\) y tal que toda variable que ocurre en \(\mathcal{P}\) este en la lista \(\mathrm{N}1,...,\mathrm{N}\bar{k},\mathrm{P}1,...,\mathrm{P}\bar{k}\). Sea \(\mathbb{P}\) el siguiente procedimiento efectivo:

- Conjunto de datos de entrada de \(\mathbb{P}\) igual a \(\omega^{n}\times\Sigma^{\ast}{}^{m}\)

Asignar los siguientes valores a las variables \(I,X_{1},...,X_{k},A_{1},...,A_{k}\): \[\begin{array}{ccc} & I\leftarrow1\\ X_{1}\leftarrow x_{1} & & A_{1}\leftarrow\alpha_{1}\\ \vdots & & \vdots\\ X_{n}\leftarrow x_{n} & & A_{m}\leftarrow\alpha_{m}\\ X_{n+1}\leftarrow0 & & A_{m+1}\leftarrow\varepsilon\\ \vdots & & \vdots\\ X_{k}\leftarrow0 & & A_{k}\leftarrow\varepsilon \end{array}\]

\(I\leftarrow\) 1er coordenada de \(S_{\mathcal{P}}(I,(X_{1},...,X_{k},0,...),(A_{1},...,A_{k},\varepsilon,...))\)

\(X_{i}\leftarrow\) \(i\)-ésima coordenada de la segunda coordenada de \(S_{\mathcal{P}}(I,(X_{1},...,X_{k},0,...),(A_{1},...,A_{k},\varepsilon,...))\)

\(A_{i}\leftarrow\) \(i\)-ésima coordenada de la tercer coordenada de \(S_{\mathcal{P}}(I,(X_{1},...,X_{k},0,...),(A_{1},...,A_{k},\varepsilon,...))\)

Si \(I=n(\mathcal{P})+1\), entonces dar \(X_{1}\) como salida y detenerse. En caso contrario ir a Etapa 2.

Sin embargo nuestro modelo imperativo de función \(\Sigma\)-efectivamente computable todavía podría no ser correcto ya que podría pasar que haya una función \(\Sigma\)-mixta que sea computada por un procedimiento efectivo pero que no exista un programa de \(\mathcal{S}^{\Sigma}\) que la compute. En otras palabras el modelo imperativo o Neumanniano podría ser incompleto. Por supuesto este no es el caso y los desarrollos que veremos mas adelante nos convencerán de que el paradigma imperativo es completo, es decir Neumann también vence a Leibniz.

4.3.4 Macros

Supongamos que estamos escribiendo un programa \(\mathcal{P}\) de \(\mathcal{S}^{\Sigma}\) con el objeto de que realice cierta tarea. Supongamos además que nos vendría muy bien para nuestros propósitos poder usar una instrucción \[\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\] la cual por supuesto al correr el programa, debería producir el efecto de dejar en la variable \(\mathrm{N}5\) la suma de los contenidos de las variables \(\mathrm{N}16\) y \(\mathrm{N}3\), sin modificar el contenido de las variables distintas a \(\mathrm{N}5\). Lamentablemente no tenemos en \(\mathcal{S}^{\Sigma}\) este tipo de instrucción pero podríamos reemplazarla por el siguiente programa \[\begin{array}{ll} & \mathrm{N}1111\leftarrow\mathrm{N}16\\ & \mathrm{N}2222\leftarrow\mathrm{N}3\\ & \mathrm{N}5\leftarrow\mathrm{N}1111\\ \mathrm{L}1000 & \mathrm{IF}\;\mathrm{N}2222\neq0\;\mathrm{GOTO}\;\mathrm{L}2000\\ & \mathrm{GOTO}\;\mathrm{L}3000\\ \mathrm{L}2000 & \mathrm{N}2222\leftarrow\mathrm{N}2222\dot{-}1\\ & \mathrm{N}5\leftarrow\mathrm{N}5+1\\ & \mathrm{GOTO}\;\mathrm{L}1000\\ \mathrm{L}3000 & \mathrm{SKIP} \end{array}\] donde las variables \(\mathrm{N}1111\), \(\mathrm{N}2222\) y los labels \(\mathrm{L}1000\), \(\mathrm{L}2000\), \(\mathrm{L}3000\) solo serán usados aquí, es decir no aparecerán en el resto de nuestro programa \(\mathcal{P}\). Nótese que este programa cuando es corrido termina dejando en la variable \(\mathrm{N}5\) la suma de los contenidos de las variables \(\mathrm{N}16\) y \(\mathrm{N}3\) y modifica el contenido de las variables \(\mathrm{N}1111\) y \(\mathrm{N}2222\), lo cual no traerá problemas ya que \(\mathrm{N}1111\) y \(\mathrm{N}2222\) no se usan en el resto de \(\mathcal{P}\). La variables \(\mathrm{N}1111\) y \(\mathrm{N}2222\) son auxiliares y se usan justamente para preservar el valor de las variables \(\mathrm{N}16\) y \(\mathrm{N}3\) ya que ellas son variables protagonistas de nuestro programa \(\mathcal{P}\) y en esta instancia no queremos alterar su contenido sino solo realizar la asignación \(\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\). Dejamos al lector explicar por que es necesario para que la simulación sea correcta que los labels \(\mathrm{L}1000\), \(\mathrm{L}2000\) y \(\mathrm{L}3000\) no sean usados en el resto de \(\mathcal{P}\).

Es decir el programa anterior simula la instrucción \(\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\) que no podíamos usar por no ser una instrucción de \(\mathcal{S}^{\Sigma}\), con un costo bastante bajo, es decir el costo de convenir en no usar en el resto de \(\mathcal{P}\) las variables \(\mathrm{N}1111\) y \(\mathrm{N}2222\) ni los labels \(\mathrm{L}1000\), \(\mathrm{L}2000\) y \(\mathrm{L}3000\).

Ahora supongamos que seguimos escribiendo el programa \(\mathcal{P}\) y nos hace falta simular la instrucción \(\mathrm{N}20\leftarrow\mathrm{N}1+\mathrm{N}14\). Entonces es claro que podríamos modificar el programa que simulaba \(\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\) haciéndole reemplazos adecuados a sus variables y labels. Por ejemplo podríamos escribir \[\begin{array}{ll} & \mathrm{N}9999\leftarrow\mathrm{N}1\\ & \mathrm{N}8888\leftarrow\mathrm{N}14\\ & \mathrm{N}20\leftarrow\mathrm{N}9999\\ \mathrm{L}1001 & \mathrm{IF}\;\mathrm{N}8888\neq0\;\mathrm{GOTO}\;\mathrm{L}2002\\ & \mathrm{GOTO}\;\mathrm{L}3003\\ \mathrm{L}2002 & \mathrm{N}8888\leftarrow\mathrm{N}8888\dot{-}1\\ & \mathrm{N}20\leftarrow\mathrm{N}20+1\\ & \mathrm{GOTO}\;\mathrm{L}1001\\ \mathrm{L}3003 & \mathrm{SKIP} \end{array}\] donde \(\mathrm{N}9999\), \(\mathrm{N}8888\), \(\mathrm{L}1001\), \(\mathrm{L}2002\) y \(\mathrm{L}3003\) solo serán usados aquí, es decir no aparecerán en el resto de nuestro programa \(\mathcal{P}\).

Consideremos el siguiente "molde" que llamaremos \(M\) \[\begin{array}{ll} & \mathrm{V}4\leftarrow\mathrm{V}2\\ & \mathrm{V}5\leftarrow\mathrm{V}3\\ & \mathrm{V}1\leftarrow\mathrm{V}4\\ \mathrm{A}1 & \mathrm{IF}\;\mathrm{V}5\neq0\;\mathrm{GOTO}\;\mathrm{A}2\\ & \mathrm{GOTO}\;\mathrm{A}3\\ \mathrm{A}2 & \mathrm{V}5\leftarrow\mathrm{V}5\dot{-}1\\ & \mathrm{V}1\leftarrow\mathrm{V}1+1\\ & \mathrm{GOTO}\;\mathrm{A}1\\ \mathrm{A}3 & \mathrm{SKIP} \end{array}\] Como puede notarse, cuando reemplazamos en \(M\)

obtenemos el programa que simulaba la instrucción \(\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\) dentro de \(\mathcal{P}\). Similarmente, cuando reemplazamos en \(M\)

obtenemos el programa que simulaba la instrucción \(\mathrm{N}20\leftarrow\mathrm{N}1+\mathrm{N}14\) dentro de \(\mathcal{P}\). La practicidad de tener el molde \(M\) cae de maduro. Ahora en caso de necesitar una instrucción del tipo \(\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{n}+\mathrm{N}\bar{m}\) solo tenemos que reemplazar en \(M\)

y reemplazar las "variables" \(\mathrm{V}4\) y \(\mathrm{V}5\) y los "labels" \(\mathrm{A}1\), \(\mathrm{A}2\) y \(\mathrm{A}3\), por dos variables concretas y tres labels concretos que no se usen en el programa que estamos realizando. El programa así obtenido simulara a la instrucción \(\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{n}+\mathrm{N}\bar{m}\).

En la jerga computacional el molde \(M\) suele llamarse macro y los programas obtenidos luego de realizar los reemplazos son llamados expansiones de \(M\). Nótese que \(Ti(M)=\mathrm{PALABRA}\) ya que, como en el caso de los programas, escribimos a \(M\) linea por linea para facilitar su manejo pero en realidad es una sola palabra, a saber: \[\mathrm{V}1\mathrm{\leftarrow}\text{V}2\mathrm{V}4\mathrm{\leftarrow}\text{V}3\mathrm{A}1\mathrm{IFV}4\mathrm{\neq}0\mathrm{GOTOA}2\mathrm{GOTOA}3\mathrm{A}2\mathrm{V}4\mathrm{\leftarrow}\text{V}4\mathrm{\dot{-}}1\mathrm{V}1\mathrm{\leftarrow}\text{V}1\mathrm{+}1\mathrm{GOTOA}1\mathrm{A}3\mathrm{SKIP}\] Es decir, como objeto matemático, \(M\) es simplemente una palabra. A las palabras de la forma \(\mathrm{V}\bar{n}\), con \(n\in\mathbf{N}\), las llamaremos variables numéricas de macro. A las palabras de la forma \(\mathrm{W}\bar{n}\), con \(n\in\mathbf{N}\), las llamaremos variables alfabéticas de macro y a las palabras de la forma \(\mathrm{A}\bar{n}\), con \(n\in\mathbf{N}\), las llamaremos labels de macro. Nuestro macro \(M\) no tiene variables alfabéticas de macro pero otros macros por supuesto pueden tener este tipo de variables.

Las variables \(\mathrm{V}1\), \(\mathrm{V}2\) y \(\mathrm{V}3\) son llamadas variables oficiales de \(M\) ya que son las variables que serán reemplazadas por variables que son protagonistas dentro del programa \(\mathcal{P}\) que usara la expansión de \(M\). Las palabras \(\mathrm{V}4\) y \(\mathrm{V}5\) son llamadas variables auxiliares de \(M\) ya que serán reemplazadas por variables que se usaran solo dentro de la expansión y no intervienen en la "trama" del programa \(\mathcal{P}\). También \(\mathrm{A}1\), \(\mathrm{A}2\) y \(\mathrm{A}3\) son llamados labels auxiliares de \(M\) ya que son usados solo para su funcionamiento interno y no tienen vinculación con los labels del programa \(\mathcal{P}\).

En el siguiente ejemplo veremos un macro que tiene un label que no es auxiliar sino oficial. Supongamos que estamos escribiendo un programa \(\mathcal{P}^{\prime}\) y nos hace falta simular instrucciones de la forma \[\mathrm{IF}\;\left\vert \mathrm{P}\bar{n}\right\vert \leq\mathrm{N}\bar{m}\ \mathrm{GOTO}\;\mathrm{L}\bar{k}\] (por supuesto estas instrucciones no pertenecen al lenguaje \(\mathcal{S}^{\Sigma}\) pero debería quedar claro como funcionan). Construiremos un macro que nos permita simular dicho tipo de instrucciones. Aquí la construcción del macro dependerá de quien es \(\Sigma\), es decir el macro nos servirá para simular instrucciones de \(\mathcal{S}^{\Sigma}\) haciendo programas de \(\mathcal{S}^{\Sigma}\) y si lo usamos haciendo un programa de \(\mathcal{S}^{\Gamma}\), donde \(\Gamma\) es otro alfabeto que contenga a \(\Sigma\), el macro no funcionara bien. Haremos entonces el macro para el caso de \(\Sigma=\{@,!\}\). Sea \(M^{\prime}\) el siguiente macro: \[\begin{array}{ll} & \mathrm{W}2\leftarrow\mathrm{W}1\\ & \mathrm{V}2\leftarrow\mathrm{V}1\\ \mathrm{A}4 & \mathrm{IF}\;\mathrm{W}2\;\mathrm{BEGINS}\;@\;\mathrm{GOTO}\;\mathrm{A}2\\ & \mathrm{IF}\;\mathrm{W}2\;\mathrm{BEGINS}\;!\;\mathrm{GOTO}\;\mathrm{A}2\\ & \mathrm{GOTO}\;\mathrm{A}1\\ \mathrm{A}2 & \mathrm{IF}\;\mathrm{V}2\neq0\;\mathrm{GOTO}\;\mathrm{A}3\\ & \mathrm{GOTO}\;\mathrm{A}5\\ \mathrm{A}3 & \mathrm{W}2\leftarrow^{\curvearrowright}\mathrm{W}2\\ & \mathrm{V}2\leftarrow\mathrm{V}2\dot{-}1\\ & \mathrm{GOTO}\;\mathrm{A}4\\ \mathrm{A}5 & \mathrm{SKIP} \end{array}\] el cual tiene

Una descripción intuitiva del macro \(M^{\prime}\) seria \[\mathrm{IF}\;\left\vert \mathrm{W}1\right\vert \leq\mathrm{V}1\ \mathrm{GOTO}\;\mathrm{A}1\] Nótese que en las primeras dos lineas el macro \(M^{\prime}\) guarda los valores de las variables oficiales \(\mathrm{W}1\) y \(\mathrm{V}1\) en las variables auxiliares \(\mathrm{W}2\) y \(\mathrm{V}2\), y sigue trabajando con las auxiliares. Esto es para preservar el valor de las variables oficiales. Dado que \(\Sigma=\{@,!\}\), las dos siguientes lineas sirven para decidir si el contenido de \(\mathrm{W}2\) es \(\varepsilon\) o no ya que si una palabra de \(\Sigma^{*}\) no comienza con \(@\) ni con \(!,\)deberá ser \(\varepsilon\) (aquí es donde notamos que nuestro macro \(M^{\prime}\) funcionara bien solo para hacer programas de \(\mathcal{S}^{\{@,!\}}\)). Dejamos al lector entender el resto del funcionamiento de \(M^{\prime}\).

Para dar un ejemplo de como usaríamos a \(M^{\prime}\), supongamos que para seguir escribiendo nuestro programa \(\mathcal{P}^{\prime}\) nos hace falta simular la instrucción \[\mathrm{IF}\;\left\vert \mathrm{P}5\right\vert \leq\mathrm{N}14\ \mathrm{GOTO}\;\mathrm{L}1\] y supongamos que las variables \(\mathrm{P}1000\) y \(\mathrm{N}1000\) y los labels \(\mathrm{L}6666\), \(\mathrm{L}7777\), \(\mathrm{L}8888\) y \(\mathrm{L}9999\) no se usaron hasta el momento en \(\mathcal{P}^{\prime}\). Entonces podemos reemplazar en \(M^{\prime}\)

y la expansión de \(M^{\prime}\) así obtenida simulara la instrucción \(\mathrm{IF}\;\left\vert \mathrm{P}5\right\vert \leq\mathrm{N}14\ \mathrm{GOTO}\;\mathrm{L}1\). Cabe destacar que para asegurarnos que la simulación funcione, también deberemos no usar en el resto de \(\mathcal{P}^{\prime}\) las variables \(\mathrm{P}1000\) y \(\mathrm{N}1000\) y los labels \(\mathrm{L}6666\), \(\mathrm{L}7777\), \(\mathrm{L}8888\) y \(\mathrm{L}9999\).

Es decir \(M^{\prime}\) funciona como un molde con el cual haciendo reemplazos adecuados podemos simular en \(\mathcal{S}^{\Sigma}\) cualquier instrucción del tipo \(\mathrm{IF}\;\left\vert \mathrm{P}\bar{n}\right\vert \leq\mathrm{N}\bar{m}\ \mathrm{GOTO}\;\mathrm{L}\bar{k}\), con \(n,m,k\in\mathbf{N}\).

Debería quedar claro el carácter oficial del label \(\mathrm{A}1\) en \(M^{\prime}\) ya que el label por el que se lo reemplaza para hacer la expansión es uno de los labels protagonistas del programa que se esta escribiendo.

Cabe destacar que las expansiones de \(M^{\prime}\) no son programas ya que si bien son concatenaciones de instrucciones, no cumplen la ley de los GOTO (llamada (G) en la definición de programa) respecto del label que reemplazo a \(\mathrm{A}1\).

Como se vio en este último ejemplo es importante tener en cuenta que cuando construimos un macro lo hacemos relativo a un alfabeto \(\Sigma\) previamente fijado, es decir estamos pensando que dicho macro será usado para hacer programas de \(\mathcal{S}^{\Sigma}\) y podría pasar que si lo usáramos para hacer un programa de \(\mathcal{S}^{\Gamma}\), donde \(\Gamma\) es otro alfabeto, el macro no cumpla las propiedades esperadas. Para visualizar esto mejor, nótese que la palabra \[\begin{array}{ll} & \mathrm{IF}\;\mathrm{W}1\;\mathrm{BEGINS}\;@\;\mathrm{GOTO}\;\mathrm{A}2\\ & \mathrm{IF}\;\mathrm{W}1\;\mathrm{BEGINS}\;\%\;\mathrm{GOTO}\;\mathrm{A}2\\ & \mathrm{IF}\;\mathrm{W}1\;\mathrm{BEGINS}\;!\;\mathrm{GOTO}\;\mathrm{A}2\\ & \mathrm{IF}\;\mathrm{W}1\;\mathrm{BEGINS}\;\uparrow\;\mathrm{GOTO}\;\mathrm{A}2\\ & \mathrm{GOTO}\;\mathrm{A}1\\ \mathrm{A}2 & \mathrm{SKIP} \end{array}\] es un macro de \(\mathcal{S}^{\{@,\%,!,\uparrow\}}\) que simula instrucciones de la forma \[\mathrm{IF}\;\mathrm{P}\bar{n}=\varepsilon\;\mathrm{GOTO}\;\mathrm{L}\bar{m}\] (el cual obviamente podríamos denotar con \(\mathrm{IF}\;\mathrm{W}1=\varepsilon\;\mathrm{GOTO}\;\mathrm{A}1\)), pero es claro que esta palabra no nos servirá para simular este tipo de instrucciones en el lenguaje \(\mathcal{S}^{\{@,\%,!,\uparrow,\vartriangle\}}\).

Nota: Siempre supondremos que la primera instrucción de los macros no es labelada. Esto es porque muchas veces cuando expandamos un macro nos interesara labelar la primera instrucción de dicha expansión. Por supuesto, esto es fácil de conseguir ya que si \(M\) es un macro, entonces \(\mathrm{SKIP}M\) es también un macro que posee las mismas propiedades.

4.3.4.1 Ejemplo concreto de uso de macros

Ya vimos recién que la palabra \[\begin{array}{ll} & \mathrm{V}4\leftarrow\mathrm{V}2\\ & \mathrm{V}5\leftarrow\mathrm{V}3\\ & \mathrm{V}1\leftarrow\mathrm{V}4\\ \mathrm{A}1 & \mathrm{IF}\;\mathrm{V}5\neq0\;\mathrm{GOTO}\;\mathrm{A}2\\ & \mathrm{GOTO}\;\mathrm{A}3\\ \mathrm{A}2 & \mathrm{V}5\leftarrow\mathrm{V}5\dot{-}1\\ & \mathrm{V}1\leftarrow\mathrm{V}1+1\\ & \mathrm{GOTO}\;\mathrm{A}1\\ \mathrm{A}3 & \mathrm{SKIP} \end{array}\] es un macro que sirve para simular instrucciones de la forma \(\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{n}+\mathrm{N}\bar{m}\) en \(\mathcal{S}^{\Sigma}\) (este macro sirve cualquiera sea \(\Sigma\)). Notemos que este macro es de asignación ya que cuando es expandido nos da un programa que simula la asignación a una variable dada del resultado de aplicar una función a los contenidos de ciertas otras variables. En este caso la función es \(SUMA=\lambda xy[x+y]\) por lo cual usaremos \(\left[\mathrm{V}1\leftarrow SUMA(\mathrm{V}2,\mathrm{V}3)\right]\) para denotar a dicho macro. Usaremos este macro para dar un programa \(\mathcal{P}\) que compute a la función \(\lambda xy[x.y]\). Nótese que podemos tomar \(\mathcal{P}\) igual al siguiente programa \[\begin{array}{ll} \mathrm{L}1 & \mathrm{IF}\;\mathrm{N}2\neq0\;\mathrm{GOTO}\;\mathrm{L}2\\ & \mathrm{GOTO}\;\mathrm{L}3\\ \mathrm{L}2 & \left[\mathrm{N}3\leftarrow SUMA(\mathrm{N}3,\mathrm{N}1)\right]\\ & \mathrm{N}2\leftarrow\mathrm{N}2\dot{-}1\\ & \mathrm{GOTO}\;\mathrm{L}1\\ \mathrm{L}3 & \mathrm{N}1\leftarrow\mathrm{N}3 \end{array}\] donde \(\left[\mathrm{N}3\leftarrow SUMA(\mathrm{N}3,\mathrm{N}1)\right]\) es una expansión del macro \(\left[\mathrm{V}1\leftarrow SUMA(\mathrm{V}2,\mathrm{V}3)\right]\) hecha haciendo el reemplazo de las variables oficiales \(\mathrm{V}1,\mathrm{V}2\) y \(\mathrm{V}3\) por \(\mathrm{N}3,\mathrm{N}3\) y \(\mathrm{N}1\), respectivamente, y haciendo reemplazos adecuados de sus variables y labels auxiliares. Hay muchas formas de hacer los reemplazos de variables y labels auxiliares pero en general no lo especificaremos explícitamente cuando expandamos un macro ya que es fácil imaginar como hacerlo en función del programa que estemos realizando. Por ejemplo en el caso de \(\mathcal{P}\) podríamos hacer los siguientes reemplazos:

y claramente esto no afectara la "lógica" o "idea" de nuestro programa \(\mathcal{P}\). De esta forma la expansión \(\left[\mathrm{N}3\leftarrow SUMA(\mathrm{N}3,\mathrm{N}1)\right]\) es el siguiente programa: \[\begin{array}{ll} & \mathrm{N}1111\leftarrow\mathrm{N}3\\ & \mathrm{N}2222\leftarrow\mathrm{N}1\\ & \mathrm{N}3\leftarrow\mathrm{N}1111\\ \mathrm{L}1000 & \mathrm{IF}\;\mathrm{N}2222\neq0\;\mathrm{GOTO}\;\mathrm{L}2000\\ & \mathrm{GOTO}\;\mathrm{L}3000\\ \mathrm{L}2000 & \mathrm{N}2222\leftarrow\mathrm{N}2222\dot{-}1\\ & \mathrm{N}3\leftarrow\mathrm{N}3+1\\ & \mathrm{GOTO}\;\mathrm{L}1000\\ \mathrm{L}3000 & \mathrm{SKIP} \end{array}\] el cual por supuesto esta escrito con espacios y en forma vertical pero es una mera palabra. Tenemos entonces que \(\mathcal{P}\) es el programa: \[\begin{array}{ll} \mathrm{L}1 & \mathrm{IF}\;\mathrm{N}2\neq0\;\mathrm{GOTO}\;\mathrm{L}2\\ & \mathrm{GOTO}\;\mathrm{L}3\\ \mathrm{L}2 & \mathrm{N}1111\leftarrow\mathrm{N}1\\ & \mathrm{N}2222\leftarrow\mathrm{N}3\\ & \mathrm{N}3\leftarrow\mathrm{N}1111\\ \mathrm{L}1000 & \mathrm{IF}\;\mathrm{N}2222\neq0\;\mathrm{GOTO}\;\mathrm{L}2000\\ & \mathrm{GOTO}\;\mathrm{L}3000\\ \mathrm{L}2000 & \mathrm{N}2222\leftarrow\mathrm{N}2222\dot{-}1\\ & \mathrm{N}3\leftarrow\mathrm{N}3+1\\ & \mathrm{GOTO}\;\mathrm{L}1000\\ \mathrm{L}3000 & \mathrm{SKIP}\\ & \mathrm{N}2\leftarrow\mathrm{N}2\dot{-}1\\ & \mathrm{GOTO}\;\mathrm{L}1\\ \mathrm{L}3 & \mathrm{N}1\leftarrow\mathrm{N}3 \end{array}\] el cual por supuesto esta escrito con espacios y en forma vertical pero es una mera palabra.

4.3.4.2 Macros asociados a funciones \(\Sigma\)-computables

Dada una función \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), usaremos \[\left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] para denotar un macro de \(\mathcal{S}^{\Sigma}\) \(M\) el cual cumpla las siguientes propiedades (no siempre existirá dicho macro, es decir solo para ciertas funciones \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) habrá un tal macro).

El programa \(\mathcal{E}=\left[\mathrm{N}\overline{k_{n+1}}\leftarrow f(\mathrm{N}\overline{k_{1}},...,\mathrm{N}\overline{k_{n}},\mathrm{P}\overline{j_{1}},...,\mathrm{P}\overline{j_{m}})\right]\) es comúnmente llamado la expansión del macro \(M=\left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\) con respecto a la elección de variables y labels realizada.

También, dada una función \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\), con \[\left[\mathrm{W}\overline{m+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] denotaremos un macro de \(\mathcal{S}^{\Sigma}\) el cual cumpla condiciones análogas a las descriptas recién. Dejamos al lector escribirlas en detalle para este caso.

Es importante notar que nuestra notación \[\left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] tiene cierta ambigüedad ya que no hace mención al alfabeto \(\Sigma\) el cual esta previamente fijado. Podría pasar que la función \(f\) sea \(\Gamma\)-mixta para otro alfabeto \(\Gamma\) y que el macro \[\left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] sea distinto según lo consideremos para \(\mathcal{S}^{\Sigma}\) o para \(\mathcal{S}^{\Gamma}\). Es decir, como ya lo remarcamos anteriormente, cuando hablamos de la existencia de un macro, es siempre relativo a un \(\mathcal{S}^{\Sigma}\). Lo mismo pasa con la notación \[\left[\mathrm{W}\overline{m+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] Dejamos al lector que piense este fenómeno para el caso de la función \(f:\{@,\%\}^{*}\times\{@,\%\}^{*}\rightarrow\{@,\%\}^{*}\), dada por \(f(\alpha,\beta)=\alpha\beta\). Si tomamos \(\Sigma=\{@,\%\}\) y \(\Gamma=\{@,\%,!\}\), entonces \(f\) resulta una función \(\Sigma\)-mixta y también \(\Gamma\)-mixta y debería quedar claro que no es lo mismo hacer el macro \[\left[\mathrm{W}3\leftarrow f(\mathrm{W}1,\mathrm{W}2)\right]\] para \(\mathcal{S}^{\Sigma}\) que hacerlo para \(\mathcal{S}^{\Gamma}\).

Otra ambigüedad de esta notación de macros de asignación es que en el nombre de los macros \[\left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] \[\left[\mathrm{W}\overline{m+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] no se especifica quienes son las variables y labels auxiliares de tipo macro. Ambas ambigüedades no nos traerán problemas si manejamos las cosas con cierta madurez.

4.8.

adhocprefix(a)adhocsufix Sea \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) una función \(\Sigma\)-computable. Entonces en \(\mathcal{S}^{\Sigma}\) hay un macro \[\left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\]
adhocprefix(b)adhocsufix Sea \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) una función \(\Sigma\)-computable. Entonces en \(\mathcal{S}^{\Sigma}\) hay un macro \[\left[\mathrm{W}\overline{m+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\]

Proof. Probaremos (b) La prueba de (a) es similar. Sea \(\mathcal{P}\) un programa que compute a \(f\). Tomemos un \(k\) tal que \(k\geq n,m\) y tal que todas las variables y labels de \(\mathcal{P}\) están en el conjunto \[\{\mathrm{N}1,...,\mathrm{N}\bar{k},\mathrm{P}1,...,\mathrm{P}\bar{k},\mathrm{L}1,...,\mathrm{L}\bar{k}\}\text{.}\] Sea \(\mathcal{P}^{\prime}\) la palabra que resulta de reemplazar en \(\mathcal{P}\):

Nótese que \[\begin{array}{l} \mathrm{V}\overline{n+1}\leftarrow\mathrm{V}1\\ \ \ \ \ \ \ \ \ \ \vdots\\ \mathrm{V}\overline{n+n}\leftarrow\mathrm{V}\overline{n}\\ \mathrm{V}\overline{n+n+1}\leftarrow0\\ \ \ \ \ \ \ \ \ \ \vdots\\ \mathrm{V}\overline{n+k}\leftarrow0\\ \mathrm{W}\overline{m+1}\leftarrow\mathrm{W}1\\ \ \ \ \ \ \ \ \ \ \vdots\\ \mathrm{W}\overline{m+m}\leftarrow\mathrm{W}\overline{m}\\ \mathrm{W}\overline{m+m+1}\leftarrow\varepsilon\\ \ \ \ \ \ \ \ \ \ \vdots\\ \mathrm{W}\overline{m+k}\leftarrow\varepsilon\\ \mathcal{P}^{\prime} \end{array}\] es el macro buscado, el cual tendrá sus variables auxiliares y labels en la lista \[\mathrm{V}\overline{n+1},...,\mathrm{V}\overline{n+k},\mathrm{W}\overline{m+2},...,\mathrm{W}\overline{m+k},\mathrm{A}1,...,\mathrm{A}\overline{k}.\]

Dejamos al lector probar la reciproca de la proposición anterior, es decir que si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) es tal que en \(\mathcal{S}^{\Sigma}\) hay un macro \[\left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] entonces \(f\) es \(\Sigma\)-computable

4.3.4.3 Macros asociados a predicados \(\Sigma\)-computables

Dado un predicado \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), usaremos \[\left[\mathrm{IF}\;P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] para denotar un macro \(M\) de \(\mathcal{S}^{\Sigma}\) el cual cumpla las siguientes propiedades (no siempre existirá dicho macro, es decir solo para ciertos predicados \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) habrá un tal macro).

La palabra \(\mathcal{E}=\left[\mathrm{IF\ }P(\mathrm{N}\overline{k_{1}},...,\mathrm{N}\overline{k_{n}},\mathrm{P}\overline{j_{1}},...,\mathrm{P}\overline{j_{m}})\ \mathrm{GOTO\ L}\bar{k}\right]\) es llamada la expansión del macro con respecto a la elección de variables y labels realizada. Al igual que en el caso de los macros de asignación, la notación \[\left[\mathrm{IF}\;P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] tiene cierta ambigüedad ya que no explicita el alfabeto ni los labels y variables auxiliares de tipo macro.

4.9. Sea \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) un predicado \(\Sigma\)-computable. Entonces en \(\mathcal{S}^{\Sigma}\) hay un macro \[\left[\mathrm{IF}\;P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right]\]

Proof. Por (a) de la proposición anterior tenemos en \(\mathcal{S}^{\Sigma}\) un macro \[\left[\mathrm{V}\overline{n+1}\leftarrow P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] Nótese que la palabra \[\left[\mathrm{V}\overline{n+1}\leftarrow P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\mathrm{IFV}\overline{n+1}\mathrm{\neq}0\mathrm{GOTOA}1\] es el macro buscado.

Dejamos al lector probar la reciproca de la proposición anterior, es decir si \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) es tal que en \(\mathcal{S}^{\Sigma}\) hay un macro \[\left[\mathrm{IF}\;P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] entonces \(P\) es \(\Sigma\)-computable.

Manantiales de macros

Dejamos en forma de una sola proposición los tres casos recién vistos de existencia de macros.

4.10 (Primer Manantial de Macros). Sea \(\Sigma\) un alfabeto finito.

adhocprefix(a)adhocsufix Si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) es \(\Sigma\)-computable, entonces en \(\mathcal{S}^{\Sigma}\) hay un macro \[\left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\]
adhocprefix(b)adhocsufix Si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) es \(\Sigma\)-computable, entonces en \(\mathcal{S}^{\Sigma}\) hay un macro \[\left[\mathrm{W}\overline{m+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\]
adhocprefix(c)adhocsufix Si \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) es un predicado \(\Sigma\)-computable, entonces en \(\mathcal{S}^{\Sigma}\) hay un macro \[\left[\mathrm{IF}\;P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right]\]

Básicamente habrá dos manantiales de macros de donde obtendremos todos los macros que potenciarán nuestro lenguaje \(\mathcal{S}^{\Sigma}\). El Segundo Manantial de Macros es consecuencia del primero y de la batalla Neumann vence a Godel.

4.3.5 Conjuntos \(\Sigma\)-enumerables

Ya que la noción de función \(\Sigma\)-computable es el modelo matemático Neumanniano o imperativo del concepto de función \(\Sigma\)-efectivamente computable, nos podríamos preguntar entonces cual es el modelo matemático Neumanniano del concepto de conjunto \(\Sigma\)-efectivamente enumerable. Si prestamos atención a la definición de este concepto, notaremos que depende de la existencia de ciertas funciones \(\Sigma\)-efectivamente computables por lo cual la siguiente definición cae de maduro:

Un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) será llamado \(\Sigma\)-enumerable cuando sea vacío o haya una función \(F:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tal que \(I_{F}=S\) y \(F_{(i)}\) sea \(\Sigma\)-computable, para cada \(i\in\{1,...,n+m\}\).

Debería entonces quedar claro que si el concepto de función \(\Sigma\)-computable modeliza correctamente al concepto de función \(\Sigma\)-efectivamente computable, entonces el concepto de conjunto \(\Sigma\)-enumerable recién definido modeliza correctamente al concepto de conjunto \(\Sigma\)-efectivamente enumerable. Nótese que según la definición que acabamos de escribir, un conjunto no vacío \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es \(\Sigma\)-enumerable si y solo si hay programas \(\mathcal{P}_{1},...,\mathcal{P}_{n+m}\) tales que

Como puede notarse los programas \(\mathcal{P}_{1},...,\mathcal{P}_{n+m}\) puestos secuencialmente a funcionar desde el estado \(\left\Vert x\right\Vert\) producen en forma natural un procedimiento efectivo (con dato de entrada \(x\in\omega\)) que enumera a \(S\). Por supuesto podemos decir que en tal caso los programas \(\mathcal{P}_{1},...,\mathcal{P}_{n+m}\) enumeran a \(S\). La siguiente proposición muestra que también las cosas se pueden hacer con un solo programa

4.11 (Caracterización de \(\Sigma\)-enumerabilidad). Sea \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) un conjunto no vacío. Entonces son equivalentes:

Proof. (1)\(\Rightarrow\)(2). Ya que \(S\) es no vacío, por definición tenemos que hay una \(F:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tal que \(I_{F}=S\) y \(F_{(i)}\) es \(\Sigma\)-computable, para cada \(i\in\{1,...,n+m\}\). Por el Primer Manantial de Macros tenemos que existen macros: \[\begin{aligned} & \left[\mathrm{V}2\leftarrow F_{(1)}(\mathrm{V}1)\right]\\ & \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ & \left[\mathrm{V}2\leftarrow F_{(n)}(\mathrm{V}1)\right]\\ & \left[\mathrm{W}1\leftarrow F_{(n+1)}(\mathrm{V}1)\right]\\ & \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ & \left[\mathrm{W}1\leftarrow F_{(n+m)}(\mathrm{V}1)\right] \end{aligned}\] Sea \(\mathcal{Q}\) el siguiente programa: \[\begin{aligned} & \left[\mathrm{P}\overline{m}\leftarrow F_{(n+m)}(\mathrm{N}1)\right]\\ & \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ & \left[\mathrm{P}1\leftarrow F_{(n+1)}(\mathrm{N}1)\right]\\ & \left[\mathrm{N}\overline{n}\leftarrow F_{(n)}(\mathrm{N}1)\right]\\ & \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ & \left[\mathrm{N}1\leftarrow F_{(1)}(\mathrm{N}1)\right] \end{aligned}\] donde se supone que las expansiones de los macros usados son hechas usando variables auxiliares no pertenecientes a la lista \(\mathrm{N}1,...,\mathrm{N}\overline{n},\mathrm{P}1,...,\mathrm{P}\overline{m}\) (por supuesto, dada la fortaleza de nuestros macros se puede usar una misma variable auxiliar para dos distintas expansiones), y también se supone que los labels auxiliares usados en dichas expansiones son todos distintos, es decir no usamos el mismo label auxiliar en dos expansiones distintas (por que?).

Sea \(k\) tal que las variables de \(\mathcal{Q}\) están todas en la lista \(\mathrm{N}1,...,\mathrm{N}\bar{k},\mathrm{P}1,...,\mathrm{P}\bar{k}\). Sea \(\mathcal{P}\) el siguiente programa: \[\mathcal{Q}\mathrm{N}\overline{n+1}\leftarrow0\mathrm{N}\overline{n+2}\leftarrow0...\mathrm{N}\overline{k}\leftarrow0\mathrm{P}\overline{m+1}\leftarrow\varepsilon\mathrm{P}\overline{m+2}\leftarrow\varepsilon...\mathrm{P}\overline{k}\leftarrow\varepsilon\] Dejamos al lector corroborar que el programa \(\mathcal{P}\) cumple las propiedades a y b

(3)\(\Rightarrow\)(1). Supongamos \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) cumple (a) y (b) de (3). Sean \[\begin{aligned} \mathcal{P}_{1} & =\mathcal{P}\mathrm{N}1\leftarrow\mathrm{N}1\\ \mathcal{P}_{2} & =\mathcal{P}\mathrm{N}1\leftarrow\mathrm{N}2\\ & \vdots\\ \mathcal{P}_{n} & =\mathcal{P}\mathrm{N}1\leftarrow\mathrm{N}\overline{n}\\ \mathcal{P}_{n+1} & =\mathcal{P}\mathrm{P}1\leftarrow\mathrm{P}1\\ \mathcal{P}_{n+2} & =\mathcal{P}\mathrm{P}1\leftarrow\mathrm{P}2\\ & \vdots\\ \mathcal{P}_{n+m} & =\mathcal{P}\mathrm{P}1\leftarrow\mathrm{P}\overline{m} \end{aligned}\] Definamos \[\begin{aligned} F_{1} & =\Psi_{\mathcal{P}_{1}}^{1,0,\#}\\ F_{2} & =\Psi_{\mathcal{P}_{2}}^{1,0,\#}\\ & \vdots\\ F_{n} & =\Psi_{\mathcal{P}_{n}}^{1,0,\#}\\ F_{n+1} & =\Psi_{\mathcal{P}_{n+1}}^{1,0,\ast}\\ F_{n+2} & =\Psi_{\mathcal{P}_{n+2}}^{1,0,\ast}\\ & \vdots\\ F_{n+m} & =\Psi_{\mathcal{P}_{n+m}}^{1,0,\ast} \end{aligned}\] Nótese que cada \(F_{i}\) es \(\Sigma\)-computable y tiene dominio igual a \(\omega\). Sea \(F=[F_{1},...,F_{n+m}]\). Tenemos por definición que \(D_{F}=\omega\) y ya que \(F_{(i)}=F_{i}\), para cada \(i=1,...,n+m\) tenemos que cada \(F_{(i)}\) es \(\Sigma\)-computable. Dejamos al lector verificar que \(I_{F}=S\)

Cuando un programa \(\mathcal{P}\) cumpla las propiedades dadas en (3) de la proposición anterior respecto de un conjunto \(S\), diremos que \(\mathcal{P}\) enumera a \(S\). Nótese que:

Cabe destacar que (3)\(\Rightarrow\)(1) de la proposición anterior es muy útil a la hora de probar que un conjunto dado es \(\Sigma\)-enumerable ya que nos permite trabajar dentro de un solo programa.

4.3.6 Conjuntos \(\Sigma\)-computables

La versión imperativa del concepto de conjunto \(\Sigma\)-efectivamente computable es fácil de dar: un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) será llamado \(\Sigma\)-computable cuando la función \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) sea \(\Sigma\)-computable. O sea que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es \(\Sigma\)-computable sii hay un programa \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) el cual computa a \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\), es decir:

Si \(\mathcal{P}\) es un programa el cual computa a \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\), diremos que \(\mathcal{P}\) decide la pertenencia a \(S\), con respecto al conjunto \(\omega^{n}\times\Sigma^{\ast m}\).

Macros asociados a conjuntos \(\Sigma\)-computables

El Primer Manantial de Macros nos dice que si \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es un conjunto \(\Sigma\)-computable, entonces, ya que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-computable, hay en \(\mathcal{S}^{\Sigma}\) un macro \[\left[\mathrm{IF}\;\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Escribiremos el nombre de este macro de la siguiente manera mas intuitiva: \[\left[\mathrm{IF}\;(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\in S\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Nótese que las expansiones de este macro, dado que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-total, ya sea terminan por la última instrucción de la expansión o direccionan a la primera instrucción que tenga label igual al label que reemplazo a \(\mathrm{A}1\) en la expansión. Es importante notar que para asegurar la existencia de este macro utilizamos que \(S\) es \(\Sigma\)-computable lo cual no siempre sucederá para un conjunto \(S\). Por ejemplo, puede pasar que \(S\) sea el dominio de una función \(\Sigma\)-computable pero que \(S\) no sea \(\Sigma\)-computable (esto se vera mas adelante) y en tal caso no existirá en \(\mathcal{S}^{\Sigma}\) un macro \[\left[\mathrm{IF}\;(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\in S\;\mathrm{GOTO}\;\mathrm{A}1\right]\] ya que si tal macro existiera seria fácil hacer un programa que compute a \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) y \(S\) seria \(\Sigma\)-computable. Es muy común el error de suponer que existe en \(\mathcal{S}^{\Sigma}\) un macro \(\left[\mathrm{IF}\;(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\in S\;\mathrm{GOTO}\;\mathrm{A}1\right]\) cuando \(S\) es el dominio de una función \(\Sigma\)-computable.

4.3 El paradigma imperativo de Neumann: El lenguaje \(\mathcal{S}^{\Sigma}\)