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

En esta seccion daremos una modelizacion matematica del concepto de funcion \(\Sigma\)-efectivamente computable utilizando un lenguaje de programacion teorico el cual depende del alfabeto \(\Sigma\). Lo llamaremos \(\mathcal{S}^{\Sigma}\) a dicho lenguaje. Dado que fue el matematico Von Neumann quien contribuyo al desarrollo de la primera computadora de proposito 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.

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

Necesitaremos algunas funciones basicas para poder describir la sintaxis de \(\mathcal{S}^{\Sigma}\) en forma precisa. Recordemos que llamamos numerales a los siguientes simbolos \[0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\] Usaremos \(Num\) para denotar el conjunto de numerales. Notese 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}\] Notese que para \(n\in\mathbf{N}\), la palabra \(Dec(n)\) es la notacion usual decimal de \(n\). Para hacer mas agil la notacion escribiremos \(\bar{n}\) en lugar de \(Dec(n)\). Notese que, en virtud de esta convencion notacional se tiene que \(Dec=\lambda n[\bar{n}]\). Recordemos que para \(\alpha\in\Sigma^{\ast}\), definiamos \[^{\curvearrowright}\alpha=\left\{ \begin{array}{lll} \left[\alpha\right]_{2}...\left[\alpha\right]_{\left\vert \alpha\right\vert } & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right.\] La sintaxis de \(\mathcal{S}^{\Sigma}\) sera dada utilizando solo simbolos 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. Tambien notese que en \(\Sigma_{p}\) hay simbolos que a veces representan operaciones como por ejemplo \(+\) y \(\dot{-}\), pero deberia quedar claro que en \(\Sigma_{p}\) estan los simbolos \(+\) 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 numericas de \(\mathcal{S}^{\Sigma}\). Las palabras de la forma \(\mathrm{P}\bar{k}\) con \(k\in\mathbf{N}\), son llamadas variables alfabeticas 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 instruccion basica 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 basicas sean mas lejibles usamos espacios entre ciertos simbolos. 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{\textrm{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 referiamos 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 instruccion de \(\mathcal{S}^{\Sigma}\) es ya sea una instruccion basica 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 instruccion basica de \(\mathcal{S}^{\Sigma}\). Usaremos \(\mathrm{Ins}^{\Sigma}\) para denotar el conjunto de todas las instrucciones de \(\mathcal{S}^{\Sigma}\). Cuando la instruccion \(I\) es de la forma \(\mathrm{L}\bar{n}J\) con \(J\) una instruccion basica, diremos que \(\mathrm{L}\bar{n}\) es el label de \(I\). Damos a continuacion, a modo de ejemplo, la interpretacion intuitiva asociada a ciertas instrucciones basicas 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 ademas 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 lejible. 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 unica como concatenacion de instrucciones.

4.40. 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 unica sucesion de instrucciones \(I_{1},...,I_{n}\) tal que \(\mathcal{P}=I_{1}...I_{n}\)

Proof. (a) Supongamos \(I_{n}\) es un tramo final propio de \(J_{m}.\) Notar que entonces \(n>1\). Es facil ver que entonces ya sea \(J_{m}=\mathrm{L}\bar{u}I_{n}\) para algun \(u\in\mathbf{N}\), o \(I_{n}\) es de la forma \(\mathrm{GOTO}\;\mathrm{L}\bar{n}\) y \(J_{m}\) es de la forma \(w\mathrm{IF}\;\mathrm{P}\bar{k}\;\mathrm{BEGINS}\;a\;\mathrm{GOTO}\;\mathrm{L}\bar{n}\) donde \(w\in\{\mathrm{L}\bar{n}:n\in\mathbf{N}\}\cup\{\varepsilon\}\). El segundo caso no puede darse porque entonces el anteultimo simbolo de \(I_{n-1}\) deberia ser \(\mathrm{S}\) lo cual no sucede para ninguna instruccion. O sea que \[I_{1}...I_{n}=J_{1}...J_{m-1}\mathrm{L}\bar{u}I_{n}\] lo cual dice que

Es decir 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}.\) Por (*), \(\mathrm{GOTO}\) es tramo final de \(J_{1}...J_{m-1}\), lo cual es impossible. Hemos llegado a una contradiccion lo cual nos dice que \(I_{n}\) no es un tramo final propio de \(J_{m}.\) Por simetria tenemos que \(I_{n}=J_{m}\), lo cual usando un razonamiento inductivo nos dice 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 univocamente 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 tambien \[I_{i}^{\mathcal{P}}=\varepsilon\] cuando \(i=0\) o \(i>n(\mathcal{P})\). Notese que las expresiones \(n(\alpha)\) y \(I_{i}^{\alpha}\) estan 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 notacion lambda que involucre dichas expresiones, el alfabeto respecto del cual usaremos dicha notacion sera \(\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 notacion 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}]\).

Sera necesaria la funcion \(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 Semantica 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 computacion via un programa de \(\mathcal{S}^{\Sigma}\), todas exepto una cantidad finita de las variables numericas tienen el valor \(0\) y todas exepto una cantiad finita de las variables alfabeticas tienen el valor \(\varepsilon\). Esto no quita generalidad a nuestra modelizacion 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 informacion 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 instruccion a realizar sera \(I_{1}^{\mathcal{P}}\) pero, dado que \(I_{1}^{\mathcal{P}}\) puede ser de tipo GOTO, la segunda instruccion que realizaremos puede no ser \(I_{2}^{\mathcal{P}}\). Es decir en cada paso iremos decidiendo en funcion de la instruccion ejecutada cual es la siguiente instruccion a realizar. O sea que mientras corremos \(\mathcal{P}\), en cada paso la informacion 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 instruccion que nos tocara realizar a continuacion. Esto da lugar al concepto de descripcion instantanea, a saber, un objeto matematico que describe en un instante dado de la computacion cuales son los valores de las variables y cual es la instruccion que se debe realizar en el instante siguiente. Mas formalmente una descripcion instantanea 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 instantaneas. Intuitivamente hablando, cuando \(i\in\{1,...,n(\mathcal{P})\}\), la descripcion instantanea \((i,\vec{s},\vec{\sigma})\) nos dice que las variables estan en el estado \((\vec{s},\vec{\sigma})\) y que la instruccion que debemos realizar es \(I_{i}^{\mathcal{P}}\). Dado que sera conveniente para simplificar el tratamiento formal, nos abstraeremos un poco y cuando \(i=0\) o \(i>n(\mathcal{P})\) pensaremos tambien que la descripcion instantanea \((i,\vec{s},\vec{\sigma})\) nos dice que las variables estan 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 instruccion).

Dado un programa \(\mathcal{P}\) definiremos a continuacion una funcion \[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 descripcion instantanea \((i,\vec{s},\vec{\sigma})\) la descripcion instantanea 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})\) sera la descripcion instantanea 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 instruccion y por lo tanto no la podremos realizar, seguiremos en el mismo estado y teniendo que realizar \(I_{i}^{\mathcal{P}}\).

Para darle una semantica mas unificada al concepto de descripcion instantanea 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 cituacion economica hace que no le sea posible comprar dicho juguete. Sin envargo el padre no mintio 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 si, daremos la definicion matematica de \(S_{\mathcal{P}}(i,\vec{s},\vec{\sigma})\), segun 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})\) comiensa 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 comiensa 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 computacion 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 computacion 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 descripcion instantanea 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 informacion 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 computacion de \(\mathcal{P}\) partiendo del estado \((\vec{s},\vec{\sigma})\) es la siguiente sucesion (de arriba hacia abajo) de descripciones instantaneas: \[\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}\] Notese 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 instruccion. Veamos un ejemplo de no detencion. 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 computacion de \(\mathcal{Q}\) partiendo del estado \((\vec{s},\vec{\sigma})\) es la siguiente sucesion (de arriba hacia abajo) de descripciones instantaneas: \[\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}\] Notese 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.

Definicion matematica de detencion

Ahora definiremos matematicamente el concepto de detencion. 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 computacion \[((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})\).

Cabe destacar que en los conceptos antes definidos por "1 paso" entendemos "realizarp una instrucion", donde tal como se lo explico antes "realizarp" significa "realizar si se puede". Otra observacion importante es que los programas de \(\mathcal{S}^{\Sigma}\) tienen una sola manera de detenerse, i.e. siempre que se detienen lo hacen habiendo realizado la ultima de sus instrucciones e intentando realizar la instruccion siguiente a su ultima instruccion.

4.3.3 Funciones \(\Sigma\)-computables

Ahora que hemos definido matematicamente la semantica de \(\mathcal{S}^{\Sigma}\) estamos en condiciones de definir el concepto de funcion \(\Sigma\)-computable, el cual sera una modelizacion matematica del concepto de funcion \(\Sigma\)-efectivamente computable. Intuitivamente hablando una funcion sera \(\Sigma\)-computable cuando haya un programa que la compute. Para precisar este concepto nos sera util la siguiente notacion. 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 notacion requiere aclarar un poco como debe interpretarse en los casos limite, es decir cuando alguno de los numeros \(n,m\) es igual a \(0\). Notese que por ejemplo \[\left\Vert x\right\Vert =\left((x,0,...),(\varepsilon,...)\right)\] (es el caso \(n=1\) y \(m=0\)). Tambien \[\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 \(\Diamond\) por lo que se obtiene \[\left\Vert \Diamond\right\Vert =\left((0,...),(\varepsilon,...)\right)\] Ademas 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 funcion \(\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}\] Analogamente definamos la funcion \(\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 si daremos la definicion precisa de funcion \(\Sigma\)-computable. Una funcion \(\Sigma\)-mixta \(f:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) sera llamada \(\Sigma\)-computable si hay un programa \(\mathcal{P}\) tal que \(f=\Psi_{\mathcal{P}}^{n,m,\#}\). En tal caso diremos que la funcion \(f\) es computada por \(\mathcal{P}\) o que \(\mathcal{P}\) computa a \(f\). Analogamente una funcion \(\Sigma\)-mixta \(f:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) sera llamada \(\Sigma\)-computable si hay un programa \(\mathcal{P}\) tal que \(f=\Psi_{\mathcal{P}}^{n,m,\ast}\). En tal caso diremos que la funcion \(f\) es computada por \(\mathcal{P}\) o que \(\mathcal{P}\) computa a \(f\).

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

4.7. 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 instruccion \(n(\mathcal{P})+1\), y dar como salida el contenido de la variable \(\mathrm{N}1\). Daremos a continuacion una descripcion mas detallada de dicho procedimiento.

Fijemos primero un numero 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\)-esima coordenada de la segunda coordenada de \(S_{\mathcal{P}}(I,(X_{1},...,X_{k},0,...),(A_{1},...,A_{k},\varepsilon,...))\)

\(A_{i}\leftarrow\) \(i\)-esima 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 envargo nuestro modelo imperativo de funcion \(\Sigma\)-efectivamente computable todavia podria no ser correcto ya que podria pasar que haya una funcion \(\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 podria ser incompleto. Por supuesto este no es el caso y los desarrollos que veremos mas adelante nos convenceran de que el paradigma imperativo es completo.

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 ademas que nos vendria muy bien para nuestros propositos poder usar una instruccion \[\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\] la cual por supuesto al correr el programa, deberia 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 instruccion pero podriamos 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 seran usados aqui, es decir no apareceran en el resto de nuestro programa \(\mathcal{P}\). Notese 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 traera 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 asignacion \(\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\). Dejamos al lector explicar por que es necesario para que la simulacion 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 instruccion \(\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\) que no podiamos usar por no ser una instruccion 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 instruccion \(\mathrm{N}20\leftarrow\mathrm{N}1+\mathrm{N}14\). Entonces es claro que podriamos modificar el programa que simulaba \(\mathrm{N}5\leftarrow\mathrm{N}16+\mathrm{N}3\) haciendole reemplazos adecuados a sus variables y labels. Por ejemplo podriamos 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 seran usados aqui, es decir no apareceran 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 instruccion \(\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 instruccion \(\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 instruccion 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 asi obtenido simulara a la instruccion \(\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{n}+\mathrm{N}\bar{m}\).

En la gerga computacional el molde \(M\) suele llamarse macro y los programas obtenidos luego de realizar los reemplazos son llamados expansiones de \(M\). Notese 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 matematico, \(M\) es simplemente una palabra. A las palabras de la forma \(\mathrm{V}\bar{n}\), con \(n\in\mathbf{N}\), las llamaremos variables numericas de macro. A las palabras de la forma \(\mathrm{W}\bar{n}\), con \(n\in\mathbf{N}\), las llamaremos variables alfabeticas 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 alfabeticas 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 seran reemplazadas por variables que son protagonistas dentro del programa \(\mathcal{P}\) que usara la expansion de \(M\). Las palabras \(\mathrm{V}4\) y \(\mathrm{V}5\) son llamadas variables auxiliares de \(M\) ya que seran reemplazadas por variables que se usaran solo dentro de la expansion y no intervienen en la "trama" del programa \(\mathcal{P}\). Tambien \(\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 vinculacion con los labels del programa \(\mathcal{P}\).

En el siguiente ejemplo veremos un macro que tiene un label que no es auxiliar sino oficial. Sea \(\Sigma=\{@,!\}\). 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 deberia quedar claro como funcionan). Entonces podemos tomar el macro \(M^{\prime}\): \[\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 descripcion intuitiva del macro \(M^{\prime}\) seria \[\mathrm{IF}\;\left\vert \mathrm{W}1\right\vert \leq\mathrm{V}1\ \mathrm{GOTO}\;\mathrm{A}1\] Notese 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. Dejamos al lector entender el resto del funcionamiento de \(M^{\prime}\).

Para dar un ejemplo de como usariamos a \(M^{\prime}\), supongamos que para seguir escribiendo nuestro programa \(\mathcal{P}^{\prime}\) nos hace falta simular la instruccion \[\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 expansion de \(M^{\prime}\) asi obtenida simulara la instruccion \(\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 simulacion funcione, tambien 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 cualquier instruccion 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}\).

Deberia quedar claro el caracter oficial del label \(\mathrm{A}1\) en \(M^{\prime}\) ya que el label por el que se lo reemplaza para hacer la expansion 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 definicion de programa) respecto del label que reemplazo a \(\mathrm{A}1\).

Nota: Siempre supondremos que la primera instruccion de los macros no es labelada. Esto es porque muchas veces cuando expandamos un macro nos interesara labelar la primera instruccion de dicha expansion. Por supuesto, esto es facil de conseguir ya que si \(M\) es un macro, entonces \(\mathrm{SKIP}M\) es tambien un macro que posee las mismas propiedades.

4.3.4.1 Ejemplo concreto de uso de macros

Ya vimos recien 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}\). Notemos que este macro es de asignacion ya que cuando es expandido nos da un programa que simula la asignacion a una variable dada del resultado de aplicar una funcion a los contenidos de ciertas otras variables. En este caso la funcion 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 funcion \(\lambda xy[x.y]\). Notese 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 expansion 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 explicitamente cuando expandamos un macro ya que es facil imaginar como hacerlo en funcion del programa que estemos realizando. Por ejemplo en el caso de \(\mathcal{P}\) podriamos hacer los siguientes reemplazos:

y claramente esto no afectara la "logica" o "idea" de nuestro programa \(\mathcal{P}\). De esta forma la expansion \(\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 funcion \(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 \(M\) el cual cumpla las siguientes propiedades. Cabe destacar que no siempre existira dicho macro, es decir solo para ciertas funciones \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) habra un tal macro.

El programa \(\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 comunmente llamado la expansion del macro \(\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 eleccion de variables y labels realizada.

Tambien, dada una funcion \(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 el cual cumpla condiciones analogas a las descriptas recien. Dejamos al lector escribirlas en detalle para este caso.

Proof. Sea \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) una funcion \(\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]\] 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}\) estan 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}\):

la variable \(\mathrm{N}\overline{j}\) por \(\mathrm{V}\overline{n+j}\), para cada \(j=1,...,k\)

la variable \(\mathrm{P}\overline{j}\) por \(\mathrm{W}\overline{m+j}\), para cada \(j=1,...,k\)

el label \(\mathrm{L}\overline{j}\) por \(\mathrm{A}\overline{j}\), para cada \(j=1,...,k\)

Notese 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 tendra 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 resiproca de la proposicion 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\) el cual cumpla las siguientes propiedades. Cabe destacar que no siempre existira dicho macro, es decir solo para ciertos predicados \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) habra un tal macro.

La palabra \(\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 expansion del macro con respecto a la eleccion de variables y labels realizada

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 proposicion anterior tenemos 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]\). Notese 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 resiproca de la proposicion 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.

4.3.5 Conjuntos \(\Sigma\)-enumerables

Ya que la nocion de funcion \(\Sigma\)-computable es el modelo matematico Neumanniano o imperativo del concepto de funcion \(\Sigma\)-efectivamente computable, nos podriamos preguntar entonces cual es el modelo matematico Neumanniano del concepto de conjunto \(\Sigma\)-efectivamente enumerable. Si prestamos atencion a la definicion de este concepto, notaremos que depende de la existencia de ciertas funciones \(\Sigma\)-efectivamente computables por lo cual la siguiente definicion cae de maduro:

Un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) sera llamado \(\Sigma\)-enumerable cuando sea vacio o haya una funcion \(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\}\).

Deberia entonces quedar claro que si el concepto de funcion \(\Sigma\)-computable modeliza correctamente al concepto de funcion \(\Sigma\)-efectivamente computable, entonces el concepto de conjunto \(\Sigma\)-enumerable recien definido modeliza correctamente al concepto de conjunto \(\Sigma\)-efectivamente enumerable. Notese que segun la definicion que acabamos de escribir, un conjunto no vacio \(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 proposicion muestra que tambien las cosas se pueden hacer con un solo programa

4.10. Sea \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) un conjunto no vacio. Entonces son equivalentes:

Proof. (1)\(\Rightarrow\)(2). Ya que \(S\) es no vacio, por definicion 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 la Proposicion 4.8 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 usa una misma variable auxiliar para dos distintas expansiones), y tambien 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}\) estan 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}\] Notese que cada \(F_{i}\) es \(\Sigma\)-computable y tiene dominio igual a \(\omega\). Sea \(F=[F_{1},...,F_{n+m}]\). Tenemos por definicion 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 proposicion anterior respecto de un conjunto \(S\), diremos que \(\mathcal{P}\) enumera a \(S\).

Cabe destacar que (3)\(\Rightarrow\)(1) de la proposicion anterior es muy util a la hora de probar que un conjunto dado es \(\Sigma\)-enumerable.

4.3.6 Conjuntos \(\Sigma\)-computables

La version imperativa del concepto de conjunto \(\Sigma\)-efectivamente computable es facil de dar: un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) sera llamado \(\Sigma\)-computable cuando la funcion \(\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 pertenecia a \(S\), con respecto al conjunto \(\omega^{n}\times\Sigma^{\ast m}\).

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

La proposicion anterior 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 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]\] Notese que las expanciones de este macro, dado que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-total, ya sea terminan por la ultima instruccion de la expansion o direccionan a la primera instruccion que tenga label igual al label que reemplazo a \(\mathrm{A}1\) en la expansion. Es importante notar que para asegurar la existencia de este macro utilizamos que \(S\) es \(\Sigma\)-computable lo cual no siempre sucedera para un conjunto \(S\). Por ejemplo, puede pasar que \(S\) sea el dominio de una funcion \(\Sigma\)-computable pero que \(S\) no sea \(\Sigma\)-computable (esto se vera mas adelante) y en tal caso no existira 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 facil hacer un programa que compute a \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) y \(S\) seria \(\Sigma\)-computable. Es muy comun el error de suponer que existe 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 funcion \(\Sigma\)-computable.

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