4.1 El paradigma de Turing

Estudiaremos el concepto de maquina de Turing, el cual fue introducido por Alam Turing para formalizar o modelizar matematicamente la idea de procedimiento efectivo. Una vez definidas las maquinas podremos dar una modelizacion matematica precisa del concepto de funcion $\Sigma$-efectivamente computable. Llamaremos a estas funciones $\Sigma$-Turing computables y seran aquellas que (en algun sentido que sera bien precisado matematicamente) pueden ser computadas por una maquina de Turing. Por supuesto, la fidedignidad de este concepto, es decir cuan buena es la modelizacion matematica dada por Turing, puede no ser clara al comienzo pero a medida que vayamos avanzando en nuestro estudio y conozcamos ademas los otros paradigmas y su relacion, quedara claro que el modelo de Turing es acertado.

Vivimos en un mundo plagado de maquinas (ascensores, celulares, relojes, taladros, etc). Una caracteristica comun a todas las maquinas es que tienen distintos estados posibles. Un estado es el conjunto de caracteristicas que determinan un momento concreto posible de la maquina cuando esta funcionando. Por ejemplo un estado posible de un ascensor seria:

1. - esta en el tercer piso, con la primer puerta abierta y la otra cerrada, esta apretado el boton de ir al sexto piso, etc

donde ponemos etc porque dependiendo del tipo de ascensor (si es con memoria, a que pisos puede ir, etc) habra mas datos que especificar para determinar un estado concreto.

Otra caracteristica comun de las maquinas es que interactuan de distintas formas con el usuario o mas generalmente su entorno. Dependiendo de que accion se ejecute sobre la maquina y en que estado este, la maquina realizara alguna tarea y ademas cambiara de estado. En general las maquinas son deterministicas en el sentido que siempre que esten en determinado estado y se les aplique determinada accion, realizaran la misma tarea y pasaran al mismo estado.

4.1.1 Descripcion informal de las maquinas de Turing

Son un modelo abstracto de maquina con una cantidad finita de estados la cual trabaja sobre una cinta de papel dividida en cuadros e interactua o recibe acciones externas por medio de una cabeza lectora que lee de a un cuadro de la cinta a la ves y ademas puede borrar el contenido del cuadro leido y escribir en el un simbolo. Tambien la cabeza lectora puede moverse un cuadro hacia la izquierda o hacia la derecha. La cinta tiene un primer cuadro hacia su izquierda pero hacia la derecha puede extenderse todo lo necesario. En un cuadro de la cinta podra haber un simbolo o un cuadro puede simplemente estar en blanco. Es decir que habra un alfabeto $\Gamma$ el cual consiste de todos los simbolos que pueden figurar en la cinta. Esto sera parte de los datos o caracteristicas de cada maquina, es decir, $\Gamma$ puede cambiar dependiendo de la maquina. La maquina, en funcion del estado en que se encuentre y de lo que vea su cabeza lectora en el cuadro escaneado, podra moverse a lo sumo un cuadro (izquierda, derecha o quedarse quieta), modificar lo que encuentre en dicho cuadro (borrando y escribiendo algun nuevo simbolo) y cambiar de estado (posiblemente al mismo que tenia). Para simplificar supondremos que hay en $\Gamma$ un simbolo el cual si aparece en un cuadro de la cinta, significara que dicho cuadro esta sin escribir o en blanco. Esto nos permitira describir mas facilmente el funcionamiento de la maquina. En gral llamaremos $B$ a tal simbolo. Tambien por lo general llamaremos $Q$ al conjunto de estados de la maquina.

Tambien cada maquina tendra un estado especial el cual sera llamado su estado inicial, generalmente denotado con $q_0$, el cual sera el estado en el que estara la maquina al comenzar a trabajar sobre la cinta. Hay otras caracteristicas que tendran las maquinas de Turing pero para dar un primer ejemplo ya nos basta. Describiremos una maquina de Turing $M$ que tendra $\Gamma =\{@,a,b,B\}$ y tendra dos estados, es decir $Q=\{q_0,q_1\}$. Obviamente $q_0$ sera su estado inicial y ademas el "comportamiento o personalidad" de $M$ estara dado por las siguientes clausulas:

1. - Estando en estado $q_0$ si ve ya sea $b$ o $B$ o $@$, entonces se queda en estado $q_0$ y se mueve a la derecha

2. - Estando en estado $q_0$ si ve $a$ entonces reescribe $@$, se mueve a la izquierda y cambia al estado $q_1$

3. - Estando en estado $q_1$ si ve $a$ o $b$ o $B$ o $@$ entonces lo deja como esta, se mueve a la izquierda y queda en estado $q_1$

Supongamos ahora que tomamos una palabra $\alpha \in {\Gamma }^{\ast }$ y la distribuimos en la cinta dejando el primer cuadro en blanco y luego poniendo los simbolos de $\alpha$ en los siguientes cuadros. Supongamos ademas que ponemos la maquina en estado $q_0$ y con su cabeza lectora escaneando el primer cuadro de la cinta. Esto lo podemos representar graficamente de la siguiente manera $$\begin{array}{cccccccc}B& {\alpha }_1& ...& {\alpha }_n& B& B& B& ...\\ \uparrow & & & & & & & \\ q_0& & & & & & & \end{array}$$ donde ${\alpha }_1,...,{\alpha }_n$ son los sucesivos simbolos de $\alpha$. Supongamos ademas que $a$ ocurre an $\alpha$. Dejamos al lector ir aplicando las clausulas de $M$ para convencerse que luego de un rato de funcionar $M$, la situacion sera $$\begin{array}{cccccccc}B& {\beta }_1& ...& {\beta }_n& B& B& B& ...\\ \uparrow & & & & & & & \\ q_1& & & & & & & \end{array}$$ donde ${\beta }_1...{\beta }_n$ es el resultado de reemplazar en $\alpha$ la primer ocurrencia de $a$ por $@$. Dejamos como ejercicio para el lector averiguar que sucede cuando $a$ no ocurre en $\alpha$

Una cosa que puede pasar es que para un determinado estado $p$ y un $\sigma \in \Gamma$, la maquina no tenga contemplada ninguna accion posible. Por ejemplo sea $M$ la maquina de Turing dada por $Q=\left\{q_0\right\}$, $\Gamma =\{@,\$,B\}$ y por la siguiente clausula:

1. - Estando en estado $q_0$ si ve ya sea $@$ o $B$, entonces se queda en estado $q_0$ y se mueve a la derecha

Es facil ver que si partimos de una situacion $$\begin{array}{cccccccc}B& {\alpha }_1& ...& {\alpha }_n& B& B& B& ...\\ \uparrow & & & & & & & \\ q_0& & & & & & & \end{array}$$ donde ${\alpha }_1,...,{\alpha }_n\in \Gamma$, entonces si ningun ${\alpha }_i$ es igual a $\$$, la maquina se movera indefinidamente hacia la derecha y en caso contrario se movera $i$ pasos a la derecha y se detendra, donde $i$ es el menor $l$ tal que ${\alpha }_l=\$$.

Otro caso posible de detencion de una maquina de Turing es cuando esta escaneando el primer cuadro de la cinta y su unica accion posible implica moverse un cuadro a la izquierda. Tambien en estos casos diremos que la maquina se detiene ya que la cinta no es extensible hacia la izquierda.

Otra caracteristica de las maquinas de Turing es que poseen un alfabeto de entrada el cual esta contenido en el alfabeto $\Gamma$ y en el cual estan los simbolos que se usaran para formar la configuracion inicial de la cinta (exepto $B$). En general lo denotaremos con $\Sigma$ al alfabeto de entrada y los simbolos de $\Gamma -\Sigma$ son considerados auxiliares. Tambien habra un conjunto $F$ contenido en el conjunto $Q$ de los estados de la maquina, cuyos elementos seran llamados estados finales.

Diremos que una palabra $\alpha ={\alpha }_1...{\alpha }_n\in {\Sigma }^{\ast }$ es aceptada por $M$ por alcance de estado final si partiendo de $$\begin{array}{cccccccc}B& {\alpha }_1& ...& {\alpha }_n& B& B& B& ...\\ \uparrow & & & & & & & \\ q_0& & & & & & & \end{array}$$ en algun momento de la computacion $M$ esta en un estado de $F$. Llamaremos $L\left(M\right)$ al conjunto formado por todas las palabras que son aceptadas por alcance de estado final

Diremos que una palabra $\alpha ={\alpha }_1...{\alpha }_n\in {\Sigma }^{\ast }$ es aceptada por $M$ por detencion si partiendo de $$\begin{array}{cccccccc}B& {\alpha }_1& ...& {\alpha }_n& B& B& B& ...\\ \uparrow & & & & & & & \\ q_0& & & & & & & \end{array}$$ en algun momento $M$ se detiene. Llamaremos $H\left(M\right)$ al conjunto formado por todas las palabras que son aceptadas por detencion

4.1.2 Definicion matematica de maquina de Turing

Una maquina de Turing es una 7-upla $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,F)$ donde

1. - $Q$ es un conjunto finito cuyos elementos son llamados estados

2. - $\Gamma$ es un alfabeto que contiene a $\Sigma$

3. - $\Sigma$ es un alfabeto llamado el alfabeto de entrada

4. - $B\in \Gamma -\Sigma$ es un simbolo de $\Gamma$ llamado el blank symbol

5. - $\delta :D_{\delta }\subseteq Q\times \Gamma \to Q\times \Gamma \times \{L,R,K\}$

6. - $q_0$ es un estado llamado el estado inicial de $M$

7. - $F\subseteq Q$ es un conjunto de estados llamados finales

Notese que la funcion $\delta$ da la "personalidad" de la maquina. Aqui los simbolos $L,R,K$ serviran para especificar que hace el cabezal. O sea:

1. - $\delta (p,\sigma )=(q,\gamma ,L)$ significara que la maquina estando en estado $p$ y leyendo el simbolo $\sigma$ borrara $\sigma$ y escribira $\gamma$ en su lugar y luego se movera un cuadro a la izquierda (esto en caso que el cabezal no este en el cuadro de mas a la izquierda, en cuyo caso no podra realizar dicha tarea y se detendra).

2. - $\delta (p,\sigma )=(q,\gamma ,K)$ significara que la maquina estando en estado $p$ y leyendo el simbolo $\sigma$ borrara $\sigma$ y escribira $\gamma$ en su lugar y luego el cabezal se quedara kieto

3. - $\delta (p,\sigma )=(q,\gamma ,R)$ significara que la maquina estando en estado $p$ y leyendo el simbolo $\sigma$ borrara $\sigma$ y escribira $\gamma$ en su lugar y luego el cabezal se movera un cuadro a la derecha

Si bien en nuestra definicion de maquina de Turing no hay ninguna restriccion acerca de la naturaleza de los elementos de $Q$, para continuar nuestro analisis asumiremos siempre que $Q$ es un alfabeto disjunto con $\Gamma$. Esto nos permitira dar definiciones matematicas precisas que formalizaran el funcionamiento de las maquinas de Turing en el contexto de las funciones mixtas. Deberia quedar claro que el hecho que solo analicemos maquinas en las cuales $Q$ es un alfabeto disjunto con $\Gamma$, no afectara la profundidad y generalidad de nuestros resultados.

4.1.2.1 Descripciones instantaneas

Una descripcion instantanea sera una palabra de la forma $\alpha q\beta$, donde $\alpha ,\beta \in {\Gamma }^{\ast }$, ${\left[\beta \right]}_{\left|\beta \right|}\ne B$ y $q\in Q$. Notese que la condicion ${\left[\beta \right]}_{\left|\beta \right|}\ne B$ nos dice que $\beta =\epsilon$ o el ultimo simbolo de $\beta$ es distinto de $B$. La descripcion instantanea ${\alpha }_1...{\alpha }_{n}q{\beta }_1...{\beta }_m$, con ${\alpha }_1,...,{\alpha }_n$, ${\beta }_1,...,{\beta }_m\in \Gamma$, $n,m\ge 0$ representara la siguiente situacion $$\begin{array}{cccccccccccc}{\alpha }_1& {\alpha }_2& ...& {\alpha }_n& {\beta }_1& {\beta }_2& ...& {\beta }_m& B& B& B& ...\\ & & & & \uparrow & & & & & & & \\ & & & & q& & & & & & & \end{array}$$ Notese que aqui $n$ y $m$ pueden ser $0$. Por ejemplo si $n=0$ tenemos que ${\alpha }_1...{\alpha }_{n}q{\beta }_1...{\beta }_m=q{\beta }_1...{\beta }_m$ y representa la siguiente situacion $$\begin{array}{cccccccc}{\beta }_1& {\beta }_2& ...& {\beta }_m& B& B& B& ...\\ \uparrow & & & & & & & \\ q& & & & & & & \end{array}$$ Si $m=0$ tenemos que ${\alpha }_1...{\alpha }_{n}q{\beta }_1...{\beta }_m={\alpha }_1...{\alpha }_{n}q$ y representa la siguiente situacion $$\begin{array}{ccccccccccc}{\alpha }_1& {\alpha }_2& ...& {\alpha }_n& B& B& ...& & & & ...\\ & & & & \uparrow & & & & & & \\ & & & & q& & & & & & \end{array}$$ Si ambos $n$ y $m$ son $0$ entonces tenemos que ${\alpha }_1...{\alpha }_{n}q{\beta }_1...{\beta }_m=q$ y representa la siguiente situacion $$\begin{array}{cccc}B& B& B& ...\\ \uparrow & & & \\ q& & & \end{array}$$ La condicion de que en una descripcion instantanea $\alpha q\beta$ deba suceder que ${\left[\beta \right]}_{\left|\beta \right|}\ne B$ es para que haya una correspondencia biuniboca entre descripciones instantaneas y situaciones de funcionamiento de la maquina. Dejamos al lector meditar sobre esto hasta convenserse de su veracidad.

Usaremos $Des$ para denotar el conjunto de las descripciones instantaneas. Definamos la funcion $St:Des\to Q$, de la siguiente manera $$St\left(d\right)=\text{unico simbolo de}Q\text{que ocurre en}d$$

4.1.2.2 La relacion $⊢$

Dado $\alpha \in (Q\cup \Gamma {)}^{\ast }$, definamos $\lfloor \alpha \rfloor$ de la siguiente manera $$\begin{array}{cc}\lfloor \epsilon \rfloor & =\epsilon \\ \lfloor \alpha \sigma \rfloor & =\alpha \sigma \text{, si}\sigma \ne B\\ \lfloor \alpha B\rfloor & =\lfloor \alpha \rfloor \end{array}$$ Es decir $\lfloor \alpha \rfloor$ es el resultado de remover de $\alpha$ el tramo final mas grande de la forma $B^n$. Dada cualquier palabra $\alpha$ definimos $${}^{\curvearrowright }\alpha =\{\begin{array}{ccc}{\left[\alpha \right]}_2...{\left[\alpha \right]}_{\left|\alpha \right|}& \text{si}& \left|\alpha \right|\ge 2\\ \epsilon & \text{si}& \left|\alpha \right|\le 1\end{array}{\alpha }^{\curvearrowleft }=\{\begin{array}{ccc}{\left[\alpha \right]}_1...{\left[\alpha \right]}_{\left|\alpha \right|-1}& \text{si}& \left|\alpha \right|\ge 2\\ \epsilon & \text{si}& \left|\alpha \right|\le 1\end{array}$$ Dadas $d_1,d_2\in Des$, escribiremos $d_1⊢d_2$ cuando existan $\sigma \in \Gamma$, $\alpha ,\beta \in {\Gamma }^{\ast }$ y $p,q\in Q$ tales que se cumple alguno de los siguientes casos

Caso 1. $$\begin{array}{cc}{d}_1& =\alpha p\beta \\ \delta (p,{\left[\beta B\right]}_1)& =(q,\sigma ,R)\\ d_2& =\alpha \sigma q^{\curvearrowright }\beta \end{array}$$

Caso 2. $$\begin{array}{cc}{d}_1& =\alpha p\beta \\ \delta (p,{\left[\beta B\right]}_1)& =(q,\sigma ,L)\text{y}\alpha \ne \epsilon \\ d_2& =\lfloor {\alpha }^{\curvearrowleft }q{\left[\alpha \right]}_{\left|\alpha \right|}{\sigma }^{\curvearrowright }\beta \rfloor \end{array}$$

Caso 3. $$\begin{array}{cc}{d}_1& =\alpha p\beta \\ \delta (p,{\left[\beta B\right]}_1)& =(q,\sigma ,K)\\ d_2& =\lfloor \alpha q{\sigma }^{\curvearrowright }\beta \rfloor \end{array}$$ Escribiremos $d⊬d^{\prime }$ para expresar que no se da $d⊢d^{\prime }$. Para $d,d^{\prime }\in Des$ y $n\ge 0$, escribiremos $d\stackrel{n}{⊢}{d}^{\prime }$ si existen $d_1,...,d_{n+1}\in Des$ tales que $$\begin{array}{cc}d& =d_1\\ d^{\prime }& =d_{n+1}\\ d_i& ⊢d_{i+1}\text{, para}i=1,...,n.\end{array}$$ Notese que $d\stackrel{0}{⊢}{d}^{\prime }$ sii $d=d^{\prime }$. Finalmente definamos $$d\stackrel{\ast }{⊢}{d}^{\prime }\text{sii}(\exists n\in \omega )d\stackrel{n}{⊢}{d}^{\prime }\text{.}$$

4.1.2.3 Detencion

Dada $d\in Des$, diremos que $M$ se detiene partiendo de $d$ si existe $d^{\prime }\in Des$ tal que

1. - $d\stackrel{\ast }{⊢}{d}^{\prime }$

2. - $d^{\prime }⊬d^{\prime \prime }$, para cada $d^{\prime \prime }\in Des$

Deberia quedar claro que es posible que $\alpha p\beta ⊬d$, para cada descripcion instantanea $d$, y que $\delta (p,[\beta B{]}_1)$ sea no vacio.

4.1.2.4 El lenguaje $L\left(M\right)$

Diremos que una palabra $\alpha \in {\Sigma }^{\ast }$ es aceptada por $M$ por alcance de estado final cuando $$\lfloor q_{0}B\alpha \rfloor \stackrel{\ast }{⊢}d\text{, con}d\text{tal que}St\left(d\right)\in F.$$ El lenguage aceptado por $M$ por alcance de estado final se define de la siguiente manera $$L\left(M\right)=\{\alpha \in {\Sigma }^{\ast }:\alpha \text{es aceptada por}M\text{por alcance de estado final}\}\text{.}$$

4.1.2.5 El lenguaje $H\left(M\right)$

Diremos que una palabra $\alpha \in {\Sigma }^{\ast }$ es aceptada por $M$ por detencion cuando $M$ se detiene partiendo de $\lfloor q_{0}B\alpha \rfloor$. El lenguage aceptado por $M$ por detencion se define de la siguiente manera $$H\left(M\right)=\{\alpha \in {\Sigma }^{\ast }:\alpha \text{es aceptada por}M\text{por detencion}\}$$

4.1.3 Funciones $\Sigma$-Turing computables

Para poder computar funciones mixtas con una maquina de Turing necesitaremos un simbolo para representar numeros sobre la cinta. Llamaremos a este simbolo unit y lo denotaremos con $\mid$. Mas formalmente una maquina de Turing con unit es una 8-upla $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,\mid ,F)$ tal que $(Q,\Sigma ,\Gamma ,\delta ,q_0,B,F)$ es una maquina de Turing y $\mid$ es un simbolo distingido perteneciente a $\Gamma -\left(\right\{B\}\cup \Sigma )$.

Diremos que una funcion $f:D_f\subseteq {\omega }^n\times {\Sigma }^{\ast m}\to {\Sigma }^{\ast }$ es $\Sigma$-Turing computable si existe una maquina de Turing con unit, $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,\mid ,F)$ tal que:

1. (1) Si $(\overrightarrow{x},\overrightarrow{\alpha })\in D_f$, entonces hay un $p\in Q$ tal que $$\lfloor q_{0}B{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor \stackrel{\ast }{⊢}\lfloor pBf(\overrightarrow{x},\overrightarrow{\alpha })\rfloor$$ y $\lfloor pBf(\overrightarrow{x},\overrightarrow{\alpha })\rfloor ⊬d$, para cada $d\in Des$

2. (2) Si $(\overrightarrow{x},\overrightarrow{\alpha })\in {\omega }^n\times {\Sigma }^{\ast m}-D_f$, entonces $M$ no se detiene partiendo de $$\lfloor q_{0}B{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor .$$

En forma similar, una funcion $f:D_f\subseteq {\omega }^n\times {\Sigma }^{\ast }{}^m\to \omega$, es llamada $\Sigma$-Turing computable si existe una maquina de Turing con unit, $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,\mid ,F)$, tal que:

1. (1) Si $(\overrightarrow{x},\overrightarrow{\alpha })\in D_f$, entonces hay un $p\in Q$ tal que $$\lfloor q_{0}B{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor \stackrel{\ast }{⊢}\lfloor pB{\mid }^{f(\overrightarrow{x},\overrightarrow{\alpha })}\rfloor$$ y $\lfloor pB{\mid }^{f(\overrightarrow{x},\overrightarrow{\alpha })}\rfloor ⊬d$, para cada $d\in Des$

2. (2) Si $(\overrightarrow{x},\overrightarrow{\alpha })\in {\omega }^n\times {\Sigma }^{\ast m}-D_f$, entonces $M$ no se detiene partiendo de $$\lfloor q_{0}B{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor$$

Cuando $M$ y $f$ cumplan los items (1) y (2) de la definicion anterior, diremos que la funcion $f$ es computada por $M$.

Por supuesto esta definicion no tendria sentido como modelo matematico del concepto de funcion $\Sigma$-efectivamente computable si no sucediera que toda funcion $\Sigma$-Turing computable fuera $\Sigma$-efectivamente computable. Este hecho es intuitivamente claro y lo presentamos a continuacion en forma de proposicion. En algun sentido esto nos dice que el paradigma filosofico es mas amplio (o igual) al paradigma de Turing. Para darle un toque de humor expresaremos esto diciendo que Leibniz vence a Turing.

Proof. Haremos el caso $O={\Sigma }^{\ast }$. Sea $P$ el siguiente procedimiento efectivo.

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

- Conjunto de datos de salida de $P$ contenido en $O$

- Funcionamiento: Hacer funcionar paso a paso la maquina $M$ partiendo de la descripcion instantanea $\lfloor q_{0}B{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor$. Si en alguna instancia $M$ termina, dar como salida el resultado de remover de la descripcion instantanea final los dos primeros simbolos.

Notese que este procedimiento termina solo en aquelos elementos $(\overrightarrow{x},\overrightarrow{\sigma })\in {\omega }^n\times {\Sigma }^{\ast }{}^m$ tales que la maquina $M$ termina partiendo desde $$\lfloor q_{0}B{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor$$ por lo cual termina solo en los elementos de $D_f$ ya que $M$ computa a $f$. Ademas es claro que en caso de terminacion el procedimiento da como salida $f(\overrightarrow{x},\overrightarrow{\sigma })$.  

Sin envargo el modelo Turingniano podria a priori no ser del todo correcto ya que podria pasar que haya una funcion que sea computada por un procedimiento efectivo pero que no exista una maquina de Turing que la compute. En otras palabras el modelo podria ser incompleto. La completitud de este modelo puede no ser clara al comienzo pero a medida que vayamos avanzando en nuestro estudio y conozcamos ademas los otros paradigmas y su relacion, quedara claro que el modelo de Turing es acertado, es decir que tambien pasa que Turing vence a Leibniz.

4.1.4 Conjuntos $\Sigma$-Turing enumerables

Ya que la nocion de funcion $\Sigma$-Turing computable es el modelo matematico de Turing del concepto de funcion $\Sigma$-efectivamente computable, nos podriamos preguntar entonces cual es el modelo matematico de Turing del concepto de conjunto $\Sigma$-efectivamente enumerable. Si prestamos atencion a la definicion de conjunto $\Sigma$-efectivamente enumerable, notaremos que depende de la existencia de cierta funcion $F$ por lo cual la siguiente definicion cae de maduro:

Diremos que un conjunto $S\subseteq {\omega }^n\times {\Sigma }^{\ast m}$ sera llamado $\Sigma$-Turing enumerable cuando sea vacio o haya una funcion $F:\omega \to {\omega }^n\times {\Sigma }^{\ast m}$ tal que $I_F=S$ y $F_{\left(i\right)}$ sea $\Sigma$-Turing computable, para cada $i\in \{1,...,n+m\}$.

Deberia quedar claro que si el concepto de funcion $\Sigma$-Turing computable modeliza correctamente al concepto de funcion $\Sigma$-efectivamente computable, entonces el concepto de conjunto $\Sigma$-Turing 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$-Turing enumerable si y solo si hay maquinas de Turing con unit $$\begin{array}{cc}{M}_1& =(Q_1,\Sigma ,{\Gamma }_1,{\delta }_1,q_{01},B,\mid ,F_1)\\ M_2& =(Q_2,\Sigma ,{\Gamma }_2,{\delta }_2,q_{02},B,\mid ,F_2)\\ & ⋮\\ M_{n+m}& =(Q_{n+m},\Sigma ,{\Gamma }_{n+m},{\delta }_{n+m},q_{0n+m},B,\mid ,F_{n+m})\end{array}$$ tales que

1. - cada $M_i$, con $i=1,...,n$, computa una funcion $F_i:\omega \to \omega$

2. - cada $M_i$, con $i=n+1,...,n+m$, computa una funcion $F_i:\omega \to {\Sigma }^{\ast }$

3. - $S=\mathrm{Im}[F_1,...,F_{n+m}]$

Como puede notarse las maquinas $M_1,...,M_{n+m}$ puestas secuencialmente a funcionar desde la descripciones instantaneas $$\begin{array}{cc}& \lfloor q_{01}B{\mid }^x\rfloor \\ & \lfloor q_{02}B{\mid }^x\rfloor \\ & ⋮\\ & \lfloor q_{0n+m}B{\mid }^x\rfloor \end{array}$$ 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 las maquinas $M_1,...,M_{n+m}$ enumeran a $S$. La siguiente proposicion muestra que tambien las cosas se pueden hacer con una sola maquina de Turing.

1. (1) Para cada $x\in \omega$, tenemos que $M$ se detiene partiendo de $\lfloor q_{0}B{\mid }^x\rfloor$ y llega a una descripcion instantanea de la forma $\lfloor qB{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor$, con $(\overrightarrow{x},\overrightarrow{\alpha })\in S$.

2. (2) Para cada $(\overrightarrow{x},\overrightarrow{\alpha })\in S$ hay un $x\in \omega$ tal que $M$ se detiene partiendo de $\lfloor q_{0}B{\mid }^x\rfloor$ y llega a una descripcion instantanea de la forma $\lfloor qB{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor$

Proof. Queda como ejercicio ver como construir la maquina $M$ utilizando las maquinas $M_1,...,M_{n+m}$ y reciprocamente ver como a partir de una maquina $M$ con las propiedades (1) y (2) se pueden construir las maquinas $M_1,...,M_{n+m}$.  

4.1.5 Conjuntos $\Sigma$-Turing computables

La version Turingniana del concepto de conjunto $\Sigma$-efectivamente computable es facil de dar: un conjunto $S\subseteq {\omega }^n\times {\Sigma }^{\ast m}$ sera llamado $\Sigma$-Turing computable cuando la funcion ${\chi }_S^{{\omega }^n\times {\Sigma }^{\ast m}}$ sea $\Sigma$-Turing computable. O sea que $S\subseteq {\omega }^n\times {\Sigma }^{\ast m}$ es $\Sigma$-Turing computable sii hay una maquina de Turing con unit $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,\mid ,F)$ la cual computa a ${\chi }_S^{{\omega }^n\times {\Sigma }^{\ast m}}$, es decir:

1. - Si $(\overrightarrow{x},\overrightarrow{\alpha })\in S$, entonces hay un $p\in Q$ tal que $$\lfloor q_{0}B{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor \stackrel{\ast }{⊢}\lfloor pB\mid \rfloor$$ y $\lfloor pB\mid \rfloor ⊬d$, para cada $d\in Des$

2. - Si $(\overrightarrow{x},\overrightarrow{\alpha })\in ({\omega }^n\times {\Sigma }^{\ast m})-S$, entonces hay un $p\in Q$ tal que $$\lfloor q_{0}B{\mid }^{x_1}B...B{\mid }^{x_n}B{\alpha }_{1}B...B{\alpha }_m\rfloor \stackrel{\ast }{⊢}\lfloor pB\rfloor$$ y $\lfloor pB\rfloor ⊬d$, para cada $d\in Des$

Si $M$ es una maquina de Turing la cual computa a ${\chi }_S^{{\omega }^n\times {\Sigma }^{\ast m}}$, diremos que $M$ decide la pertenecia a $S$, con respecto al conjunto ${\omega }^n\times {\Sigma }^{\ast m}$.