Sea \(\Sigma\) un alfabeto. Dados \(n,m\in\omega\), usaremos \(\omega^{n}\times\Sigma^{\ast m}\) para abreviar la expresión \[\overset{n\text{ veces}}{\overbrace{\omega\times...\times\omega}}\times\overset{m\text{ veces}}{\overbrace{\Sigma^{\ast}\times...\times\Sigma^{\ast}}}\] Por ejemplo, \(\omega^{3}\times\Sigma^{\ast4}\) será una forma abreviada de escribir \(\omega\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\). Debe quedar claro que estamos haciendo cierto abuso notacional ya que en principio si no hacemos esta convención notacional, \(\omega^{3}\times\Sigma^{\ast4}\) denota un conjunto de pares y \(\omega\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\) es un conjunto de \(7\)-uplas.
Nótese que:
adhocprefix-adhocsufix Cuando \(n=m=0\), tenemos que \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\{\lozenge\}\)
adhocprefix-adhocsufix Si \(m=0\), entonces \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\omega^{n}\)
adhocprefix-adhocsufix Si \(n=0\), entonces \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\Sigma^{\ast m}\)
adhocprefix-adhocsufix Cuando \(\Sigma=\emptyset\), tenemos que \(\Sigma^{\ast}=\{\varepsilon\}\). O sea que por ejemplo \[\omega^{n}\times\Sigma^{\ast5}=\{(x_{1},...,x_{n},\varepsilon,\varepsilon,\varepsilon,\varepsilon,\varepsilon):x_{1},...,x_{n}\in\omega\}\]
Es decir que tenemos que tener cuidado cuando leemos esta notación y no caer en la confusión de interpretarla mal.
Con esta convención notacional, un elemento genérico de \(\omega^{n}\times\Sigma^{\ast m}\) es una \((n+m)\)-upla de la forma \((x_{1},...,x_{n},\alpha_{1},...,\alpha_{m})\). Para abreviar, escribiremos \((\vec{x},\vec{\alpha})\) en lugar de \((x_{1},...,x_{n},\alpha_{1},...,\alpha_{m})\).
Sea \(\Sigma\) un alfabeto. Dada una función \(f\), diremos que \(f\) es \(\Sigma\)-mixta si cumple las siguientes propiedades
adhocprefix(M1)adhocsufix Existen \(n,m\geq0\), tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\)
adhocprefix(M2)adhocsufix Ya sea \(I_{f}\subseteq\omega\) o \(I_{f}\subseteq\Sigma^{\ast}\)
Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(\Sigma=\{\square,\%,\blacktriangle\}\). La función \[\begin{array}{rll} f:\{(1,\square\%\%),(100,\%\blacktriangle\blacktriangle)\} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & x+\left\vert \alpha\right\vert \end{array}\] es \(\Sigma\)-mixta ya que se cumple (M1) con \(n=m=1\) y también cumple (M2). Nótese que \(f\) no es \(\{\square,\%\}\)-mixta ya que no cumple (M1) respecto del alfabeto \(\{\square,\%\}\). Sin embargo note que \(f\) es \(\{\square,\%,\blacktriangle,@\}\)-mixta
adhocprefix(E2)adhocsufix La función \[\begin{array}{rll} \omega^{4} & \rightarrow & \omega\\ (x,y,z,w) & \rightarrow & x+y \end{array}\] es \(\Sigma\)-mixta cualesquiera sea el alfabeto \(\Sigma\)
adhocprefix(E3)adhocsufix Sea \(\Sigma=\{\square,@\}\). La función \[\begin{array}{rll} \{\square\square\square,@@\} & \rightarrow & \omega\\ \alpha & \rightarrow & \left\vert \alpha\right\vert \end{array}\]
es \(\Sigma\)-mixta ya que se cumple (M1) (con \(n=0\) y \(m=1\)) y (M2)
adhocprefix(E4)adhocsufix Supongamos \(\Sigma=\emptyset\). Tenemos entonces que \(\Sigma^{\ast}=\{\varepsilon\}\). Por ejemplo \[\begin{array}{rll} D & \rightarrow & \omega\\ (x,\varepsilon,\varepsilon,\varepsilon) & \rightarrow & x^{2} \end{array}\] donde \(D=\{(x,\varepsilon,\varepsilon,\varepsilon):x\) es impar\(\}\), es \(\Sigma\)-mixta (con \(n=1\) y \(m=3\) en (M1)). También nótese que \[\begin{array}{rll} \{(\varepsilon,\varepsilon)\} & \rightarrow & \{\varepsilon\}\\ (\varepsilon,\varepsilon) & \rightarrow & \varepsilon \end{array}\] es \(\Sigma\)-mixta (con \(n=0\) y \(m=2\) en (M1)).
adhocprefix(E5)adhocsufix La función \[\begin{array}{rll} \{\lozenge\} & \rightarrow & \omega\\ \lozenge & \rightarrow & 5 \end{array}\] es \(\Sigma\)-mixta cualesquiera sea el alfabeto \(\Sigma\) (con \(n=m=0\) en (M1)).
adhocprefix(E6)adhocsufix La función \(\emptyset\) es \(\Sigma\)-mixta cualesquiera sea el alfabeto \(\Sigma\) (con \(n,m\) cualesquiera elementos de \(\omega\) en (M1)).
Dejamos al lector la fácil prueba del siguiente resultado básico.
1.10. Supongamos \(\Sigma\subseteq\Gamma\) son alfabetos finitos. Entonces si \(f\) es una función \(\Sigma\)-mixta, \(f\) es \(\Gamma\)-mixta.
Una función \(\Sigma\)-mixta \(f\) es \(\Sigma\)-total cuando haya \(n,m\in\omega\) tales que \(D_{f}=\omega^{n}\times\Sigma^{\ast m}\). El lema anterior nos dice que si \(\Sigma\subseteq\Gamma\), entonces toda función \(\Sigma\)-mixta es \(\Gamma\)-mixta. Sin embargo una función puede ser \(\Sigma\)-total y no ser \(\Gamma\)-total, cuando \(\Sigma\subseteq\Gamma\). Por ejemplo tomemos \(\Sigma=\{\square,\%,\blacktriangle\}\) y \(\Gamma=\{\square,\%,\blacktriangle,!\}\), y consideremos la función \[\begin{array}{rll} f:\omega\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & x+\left\vert \alpha\right\vert \end{array}\] Es claro que \(f\) es \(\Sigma\)-mixta y \(\Sigma\)-total. También es \(\Gamma\)-mixta ya que \(D_{f}\subseteq\omega\times\Gamma^{\ast}\) y \(I_{f}\subseteq\omega\), por lo cual cumple (M1) y (M2). Sin embargo \(f\) no es \(\Gamma\)-total ya que \(D_{f}\) no es igual a \(\omega^{n}\times\Gamma^{\ast m}\), cualesquiera sean \(n\) y \(m\). Nótese que la función \(\emptyset\) no es \(\Sigma\)-total cualquiera sea el alfabeto \(\Sigma\).
Como hemos visto recién, una función \(f\) puede ser \(\Sigma\)-mixta y \(\Gamma\)-mixta para dos alfabetos distintos \(\Sigma\) y \(\Gamma\) e incluso es fácil construir un ejemplo en el cual \(\Sigma\) y \(\Gamma\) sean incomparables como conjuntos, es decir que ninguno incluya al otro. Nótese que si \(f\) es una función que es \(\Sigma\)-mixta para algún alfabeto \(\Sigma\), entonces hay un alfabeto \(\Sigma_{0}\) el cual es el menor de todos los alfabetos respecto de los cuales \(f\) es mixta, es decir \(\Sigma_{0}\) cumple que \(f\) es \(\Sigma_{0}\)-mixta y si \(\Gamma\) es tal que \(f\) es \(\Gamma\)-mixta, entonces \(\Sigma_{0}\subseteq\Gamma\). Simplemente podemos tomar \(\Sigma_{0}\) igual al conjunto formado por todos los símbolos \(\sigma\) tales que ya sea \(\sigma\) ocurre en alguna palabra que es coordenada de alguna upla del dominio de \(f\) o \(\sigma\) ocurre en alguna palabra perteneciente a la imagen de \(f\).
A continuación daremos algunas funciones \(\Sigma\)-mixtas básicas las cuales serán frecuentemente usadas.
La función sucesor es definida por \[\begin{array}{rll} Suc:\omega & \rightarrow & \omega\\ n & \rightarrow & n+1 \end{array}\] La función predecesor es definida por \[\begin{array}{rll} Pred:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n-1 \end{array}\]
Sea \(\Sigma\) un alfabeto no vacío. Para cada \(a\in\Sigma\), definamos \[\begin{array}{rll} d_{a}:\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ \alpha & \rightarrow & \alpha a \end{array}\] La función \(d_{a}\) es llamada la función derecha sub \(a\), respecto del alfabeto \(\Sigma\).
Sea \(\Sigma\) un alfabeto. Para \(n,m,i\in\omega\) tales que \(1\leq i\leq n\), definamos \[\begin{array}{rll} p_{i}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & x_{i} \end{array}\] Para \(n,m,i\in\omega\) tales que \(n+1\leq i\leq n+m\), definamos \[\begin{array}{rll} p_{i}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \Sigma^{\ast}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \alpha_{i-n} \end{array}\] Las funciones \(p_{i}^{n,m}\) son llamadas proyecciones. La función \(p_{i}^{n,m}\) es llamada la proyección \(n,m,i\), respecto del alfabeto \(\Sigma\). Nótese que esta definición requiere que \(n+m\geq1\) ya que \(i\) debe cumplir \(1\leq i\leq n+m\). Además nótese que siempre la función \(p_{i}^{n,m}\) aplicada a una \((n+m)\)-upla da la coordenada \(i\)-ésima de dicha \((n+m)\)-upla. Por ejemplo: \[\begin{array}{rll} p_{3}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & \alpha_{2} \end{array}\]
Sea \(\Sigma\) un alfabeto. Para \(n,m,k\in\omega\), y \(\alpha\in\Sigma^{\ast}\), definamos \[\begin{array}{rll} C_{k}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & k \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} C_{\alpha}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \Sigma^{\ast}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \alpha \end{array}\] Por ejemplo: \[\begin{array}{rll} C_{3}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & 3 \end{array}\ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} C_{\varepsilon}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & \varepsilon \end{array}\] Nótese que \(C_{k}^{0,0}:\{\lozenge\}\rightarrow\{k\}\) y que \(C_{\alpha}^{0,0}:\{\lozenge\}\rightarrow\{\alpha\}\).
Definamos \[\begin{array}{rll} pr:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n\text{-ésimo número primo} \end{array}\] Nótese que \(pr(1)=2\), \(pr(2)=3\), \(pr(3)=5\), etc.
Dada una función \(\Sigma\)-mixta \(f\), si \(n,m\in\omega\) son tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\) y además \(I_{f}\subseteq\omega\), entonces diremos que \(f\) es una función de tipo \((n,m,\#)\). Similarmente si \(n,m\in\omega\) son tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\) y además \(I_{f}\subseteq\Sigma^{\ast}\), entonces diremos que \(f\) es una función de tipo \((n,m,\ast)\). Nótese que si \(f\neq\emptyset\), entonces hay únicos \(n,m\in\omega\) y \(s\in\{\#,\ast\}\) tales que \(f\) es una función de tipo \((n,m,s)\). Sin embargo \(\emptyset\) es una función de tipo \((n,m,s)\) cualesquiera sean \(n,m\in\omega\) y \(s\in\{\#,\ast\}\). De esta forma, cuando \(f\neq\emptyset\) hablaremos de "el tipo de \(f\)" para referirnos a esta única terna \((n,m,s)\). Nótese que \(Suc\) es de tipo \((1,0,\#)\) y cada \(d_{a}\) es de tipo \((0,1,\ast)\).
También nótese que la relación "\(f\) es una función de tipo \((n,m,s)\)" no depende del alfabeto \(\Sigma\) (que significa esto?).
Supongamos que \(k,l,n,m\in\omega\) y que \(F:D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega^{n}\times\Sigma^{\ast m}\). Supongamos además que \(n+m\geq1\). Entonces denotaremos con \(F_{(i)}\) a la función \(p_{i}^{n,m}\circ F\). Notar que \[\begin{aligned} F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega\text{, para cada }i=1,...,n\\ F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\Sigma^{\ast}\text{, para cada }i=n+1,...,n+m \end{aligned}\] Por lo cual cada una de las funciones \(F_{(i)}\) son \(\Sigma\)-mixtas. Además nótese que \[F=[F_{(1)},...,F_{(n+m)}]\]
Un predicado \(\Sigma\)-mixto es una función \(f\) la cual es \(\Sigma\)-mixta y además cumple que \(I_{f}\subseteq\{0,1\}\). Ejemplos \[\begin{array}{rll} \omega\times\omega & \rightarrow & \omega\\ (x,y) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=y\\ 0\text{ si }x\neq y \end{array}\right. \end{array}\ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} \{1,2,3,4,5\}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=\left\vert \alpha\right\vert \\ 0\text{ si }x\neq\left\vert \alpha\right\vert \end{array}\right. \end{array}\]
Dados predicados \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}\), con el mismo dominio, definamos nuevos predicados \((P\vee Q)\), \((P\wedge Q)\) y \(\lnot P\) de la siguiente manera \[\begin{array}{rll} (P\vee Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ o }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\] \[\begin{array}{rll} (P\wedge Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ y }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\] \[\begin{array}{rll} \lnot P:S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=0\\ 0 & & \text{si }P(\vec{x},\vec{\alpha})=1 \end{array}\right. \end{array}\]
Dado un alfabeto \(\Sigma\), una familia \(\Sigma\)-indexada de funciones será una función \(\mathcal{G}\) tal que \(D_{\mathcal{G}}=\Sigma\) y para cada \(a\in D_{\mathcal{G}}\) se tiene que \(\mathcal{G}(a)\) es una función. Algunos ejemplos:
adhocprefix(E1)adhocsufix Sea \(\mathcal{G}\) dada por \[\begin{array}{rcl} \mathcal{G}:\{\square,\%,\blacktriangle\} & \rightarrow & \{Suc,Pred\}\\ \square & \rightarrow & Suc\\ \% & \rightarrow & Suc\\ \blacktriangle & \rightarrow & Pred \end{array}\] Claramente \(\mathcal{G}\) es una familia \(\{\square,\%,\blacktriangle\}\)-indexada de funciones. Notar que \[\mathcal{G}=\{(\square,Suc),(\%,Suc),(\blacktriangle,Pred)\}\] Se tiene también por ejemplo que \(\mathcal{G}(\%)=Suc\) por lo cual también es cierto que \(\mathcal{G}(\%)(22)=23\), etc.
adhocprefix(E2)adhocsufix Si \(\Sigma\) es un alfabeto no vacío, la función \[\begin{array}{rcl} \mathcal{G}:\Sigma & \rightarrow & \{f:f\text{ es una función de }\Sigma^{\ast}\text{ en }\Sigma^{\ast}\}\\ a & \rightarrow & d_{a} \end{array}\] es una familia \(\Sigma\)-indexada de funciones. Notar que \[\mathcal{G}=\{(a,d_{a}):a\in\Sigma\}\]
adhocprefix(E3)adhocsufix \(\emptyset\) es una flia \(\emptyset\)-indexada de funciones
Si \(\mathcal{G}\) es una familia \(\Sigma\)-indexada de funciones, entonces para \(a\in\Sigma\), escribiremos \(\mathcal{G}_{a}\) en lugar de \(\mathcal{G}(a)\).
Un conjunto \(S\) es llamado \(\Sigma\)-mixto si hay \(n,m\in\omega\) tales que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Por ejemplo, \[\{(x,\alpha)\in\omega\times\{\blacktriangle,!\}^{\ast}:\left\vert \alpha\right\vert =x\}\] \[\{(0,\blacktriangle\blacktriangle\blacktriangle,\varepsilon),(1,\%\blacktriangle\%,\blacktriangle\blacktriangle)\}\] son conjuntos \(\{\blacktriangle,\%,!\}\)-mixtos. También nótese que \(\emptyset\) y \(\{\lozenge\}\) son conjuntos \(\Sigma\)-mixtos, cualesquiera sea el alfabeto \(\Sigma\). Por último el conjunto \[\{(x,\varepsilon,\varepsilon,\varepsilon):x\in\omega\text{ y }x\text{ es impar}\}\] es \(\emptyset\)-mixto (con \(n=1\) y \(m=3\)).
Dado un conjunto \(\Sigma\)-mixto \(S\), si \(n,m\in\omega\) son tales que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\), entonces diremos que \(S\) es un conjunto de tipo \((n,m)\). Nótese que si \(S\neq\emptyset\), entonces hay únicos \(n,m\in\omega\) tales que \(S\) es un conjunto de tipo \((n,m)\). De esta forma, cuando \(S\neq\emptyset\) hablaremos de "el tipo de \(S\)" para referirnos a este único par \((n,m)\). También es importante notar que de la definición anterior sale inmediatamente que \(\emptyset\) es un conjunto de tipo \((n,m)\) cualesquiera sean \(n,m\in\omega\), por lo cual cuando hablemos de EL tipo de un conjunto deberemos estar seguros de que dicho conjunto es no vacío.
Nótese que \(\omega\) es de tipo \((1,0)\) y \(\Sigma^{\ast}\) es de tipo \((0,1)\).
Un conjunto es llamado rectangular si es de la forma \[S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\] con \(n,m\in\omega\), cada \(S_{i}\subseteq\omega\) y cada \(L_{i}\) es un conjunto de palabras. Notar que todo subconjunto de \(\omega\) es rectangular (es el caso \(n=1\) y \(m=0\)). También \(\{\lozenge\}\) es rectangular (es el caso \(n=m=0\)). Otros ejemplos:
adhocprefix-adhocsufix \(\mathbf{N}\times\{1,2\}\times\{@@,\varepsilon\}\) es rectangular (aquí \(n=2\) y \(m=1\))
adhocprefix-adhocsufix \(\{!!!,!!\}\times\{@@,\varepsilon\}\) es rectangular (aquí \(n=0\) y \(m=2\))
adhocprefix-adhocsufix \(\emptyset\) es rectangular (aquí \(n=1\) y \(m=0\))
Cabe destacar que no hemos fijado un alfabeto para definir conjunto rectangular. Notar que si \(\Sigma\) es un alfabeto tal que \(L_{i}\subseteq\Sigma^{\ast}\), para cada \(i=1,...,m\), entonces el conjunto rectangular \(S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-mixto.
El concepto de conjunto rectangular es muy importante en nuestro enfoque. Aunque en general no habrá restricciones acerca del dominio de las funciones y predicados, nuestra filosofía será tratar en lo posible que los dominios de las funciones que utilicemos para hacer nuestro análisis de recursividad de las maquinas de Turing y de la semántica del lenguaje \(\mathcal{S}^{\Sigma}\), sean rectangulares. Aunque en principio puede parecer que todos los conjuntos son rectangulares, el siguiente lema mostrara cuan ingenua es esta visión.
1.11. Sea \(S\subseteq\omega\times\Sigma^{\ast}\). Entonces \(S\) es rectangular si y solo si se cumple la siguiente propiedad:
adhocprefix(R)adhocsufix Si \((x,\alpha),(y,\beta)\in S\), entonces \((x,\beta)\in S\)
Proof. Ejercicio.
Nótese que podemos usar el lema anterior para probar por ejemplo que los siguientes conjuntos no son rectangulares
adhocprefix-adhocsufix \(\{(0,\#\#),(1,\%\%\%)\}\)
adhocprefix-adhocsufix \(\{(x,\alpha):\left\vert \alpha\right\vert =x\}\)
Dejamos como ejercicio para el lector enunciar un lema análogo al anterior pero que caracterice cuando \(S\subseteq\omega^{2}\times\Sigma^{\ast3}\) es rectangular.