Estudiaremos el concepto de máquina de Turing, el cual fue introducido por Alan Turing para formalizar o modelizar matemáticamente la idea de procedimiento efectivo. Una vez definidas las máquinas podremos dar una modelización matemática precisa del concepto de función \(\Sigma\)-efectivamente computable. Llamaremos a estas funciones \(\Sigma\)-Turing computables y serán aquellas que (en algún sentido que será bien precisado matemáticamente) pueden ser computadas por una máquina de Turing. Por supuesto, la fidedignidad de este concepto, es decir cuan buena es la modelización matemática dada por Turing, puede no ser clara al comienzo pero a medida que vayamos avanzando en nuestro estudio y conozcamos además los otros paradigmas y su relación, quedara claro que el modelo de Turing es acertado.
Vivimos en un mundo plagado de máquinas (ascensores, celulares, relojes, taladros, etc). Una característica común a todas las máquinas es que tienen distintos estados posibles. Un estado es el conjunto de características que determinan un momento concreto posible de la máquina cuando esta funcionando. Por ejemplo un estado posible de un ascensor seria:
adhocprefix-adhocsufix esta en el tercer piso, con la primer puerta abierta y la otra cerrada, esta apretado el botón 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) habrá mas datos que especificar para determinar un estado concreto.
Otra característica común de las máquinas es que interactúan de distintas formas con el usuario o mas generalmente su entorno. Dependiendo de que acción se ejecute sobre la máquina y en que estado este, la máquina realizará alguna tarea y además cambiará de estado. En general las máquinas son deterministicas en el sentido que siempre que estén en determinado estado y se les aplique determinada acción, realizarán la misma tarea y pasarán al mismo estado.
Son un modelo abstracto de máquina con una cantidad finita de estados la cual trabaja sobre una cinta de papel dividida en cuadros e interactuá o recibe acciones externas por medio de una cabeza lectora que lee de a un cuadro de la cinta a la ves y además puede borrar el contenido del cuadro leído y escribir en el un símbolo. También la cabeza lectora puede moverse un cuadro hacia la izquierda o hacia la derecha o quedarse en el mismo cuadro. La cinta tiene un primer cuadro hacia su izquierda pero hacia la derecha puede extenderse todo lo necesario. En un cuadro de la cinta podrá haber un símbolo o un cuadro puede simplemente estar en blanco. Es decir que habrá un alfabeto \(\Gamma\) el cual consiste de todos los símbolos que pueden figurar en la cinta. Esto será parte de los datos o características de cada máquina, es decir, \(\Gamma\) puede cambiar dependiendo de la máquina. La máquina, en función del estado en que se encuentre y de lo que vea su cabeza lectora en el cuadro escaneado, podrá moverse a lo sumo un cuadro (izquierda, derecha o quedarse quieta), modificar lo que encuentre en dicho cuadro (borrando y escribiendo algún nuevo símbolo) y cambiar de estado (posiblemente al mismo que tenia). Para simplificar supondremos que hay en \(\Gamma\) un símbolo el cual si aparece en un cuadro de la cinta, significara que dicho cuadro esta sin escribir o en blanco. Esto nos permitirá describir mas fácilmente el funcionamiento de la máquina. En gral llamaremos \(B\) a tal símbolo. También por lo general llamaremos \(Q\) al conjunto de estados de la máquina.
También cada máquina tendrá un estado especial el cual será llamado su estado inicial, generalmente denotado con \(q_{0}\), el cual será el estado en el que estará la máquina al comenzar a trabajar sobre la cinta. Hay otras características que tendrán las máquinas de Turing pero para dar un primer ejemplo ya nos basta. Describiremos una máquina de Turing \(M\) que tendrá \(\Gamma=\{@,a,b,B\}\) y tendrá dos estados, es decir \(Q=\{q_{0},q_{1}\}\). Obviamente \(q_{0}\) será su estado inicial y además el "comportamiento o personalidad" de \(M\) estará dado por las siguientes clausulas:
adhocprefix-adhocsufix 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
adhocprefix-adhocsufix Estando en estado \(q_{0}\) si ve \(a\) entonces reescribe \(@\), se mueve a la izquierda y cambia al estado \(q_{1}\)
adhocprefix-adhocsufix 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 símbolos de \(\alpha\) en los siguientes cuadros. Supongamos además que ponemos la máquina en estado \(q_{0}\) y con su cabeza lectora escaneando el primer cuadro de la cinta. Esto lo podemos representar gráficamente 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 símbolos de \(\alpha\). Supongamos además que \(a\) ocurre en \(\alpha\). Dejamos al lector ir aplicando las clausulas de \(M\) para convencerse que luego de un rato de funcionar \(M\), la situación será \[\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 máquina no tenga contemplada ninguna acción posible. Por ejemplo sea \(M\) la máquina de Turing dada por \(Q=\{q_{0}\}\), \(\Gamma=\{@,\$,B\}\) y por la siguiente clausula:
adhocprefix-adhocsufix 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 fácil ver que si partimos de una situación \[\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 ningún \(\alpha_{i}\) es igual a \(\$\), la máquina se moverá indefinidamente hacia la derecha y en caso contrario se moverá \(i\) pasos a la derecha y se detendrá, donde \(i\) es el menor \(l\) tal que \(\alpha_{l}=\$\).
Otro caso posible de detención de una máquina de Turing es cuando esta escaneando el primer cuadro de la cinta y su única acción posible implica moverse un cuadro a la izquierda. También en estos casos diremos que la máquina se detiene ya que la cinta no es extensible hacia la izquierda.
Otra característica de las máquinas de Turing es que poseen un alfabeto de entrada el cual esta contenido en el alfabeto \(\Gamma\) y en el cual están los símbolos que se usaran para formar la configuración inicial de la cinta (excepto \(B\)). En general lo denotaremos con \(\Sigma\) al alfabeto de entrada y los símbolos de \(\Gamma-\Sigma\) son considerados auxiliares. También habrá un conjunto \(F\) contenido en el conjunto \(Q\) de los estados de la máquina, cuyos elementos serán 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 algún momento de la computación \(M\) esta en un estado de \(F\). Llamaremos \(L(M)\) 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 detención si partiendo de \[\begin{array}{cccccccc} B & \alpha_{1} & ... & \alpha_{n} & B & B & B & ...\\ \uparrow\\ q_{0} \end{array}\] en algún momento \(M\) se detiene. Llamaremos \(H(M)\) al conjunto formado por todas las palabras que son aceptadas por detención
Seguiremos bastante fidedignamente el tratamiento dado en el libro de Hopcroft y Ullman. Una máquina de Turing es una 7-upla \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,F\right)\) donde
adhocprefix-adhocsufix \(Q\) es un conjunto finito cuyos elementos son llamados estados
adhocprefix-adhocsufix \(\Gamma\) es un alfabeto que contiene a \(\Sigma\)
adhocprefix-adhocsufix \(\Sigma\) es un alfabeto llamado el alfabeto de entrada
adhocprefix-adhocsufix \(B\in\Gamma-\Sigma\) es un símbolo de \(\Gamma\) llamado el blank symbol
adhocprefix-adhocsufix \(\delta:D_{\delta}\subseteq Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R,K\}\)
adhocprefix-adhocsufix \(q_{0}\) es un estado llamado el estado inicial de \(M\)
adhocprefix-adhocsufix \(F\subseteq Q\) es un conjunto de estados llamados finales
Nótese que la función \(\delta\) da la "personalidad" de la máquina. Describiremos esto informalmente y después cuando definamos la relación \(\vdash\) mas abajo esta idea quedara precisada en forma matemática.
adhocprefix-adhocsufix \(\delta(p,\sigma)=(q,\gamma,L)\) significara que: si \(M\) esta en estado \(p\) y su cabezal esta escaneando una casilla distinta de la primera, en la cual esta dibujado el símbolo \(\sigma\), entonces la máquina hará lo siguiente:
borrara \(\sigma\) y escribirá \(\gamma\) en su lugar, luego
se moverá un cuadro a la izquierda y luego
pasara al estado \(q\)
adhocprefix-adhocsufix \(\delta(p,\sigma)=(q,\gamma,K)\) significara que: si \(M\) esta en estado \(p\) y su cabezal esta escaneando una casilla en la cual esta dibujado el símbolo \(\sigma\), entonces la máquina hará lo siguiente:
borrara \(\sigma\) y escribirá \(\gamma\) en su lugar, luego
pasara al estado \(q\)
(es decir que el cabezal se queda kieto)
adhocprefix-adhocsufix \(\delta(p,\sigma)=(q,\gamma,R)\) significara que: si \(M\) esta en estado \(p\) y su cabezal esta escaneando una casilla en la cual esta dibujado el símbolo \(\sigma\), entonces la máquina hará lo siguiente:
borrara \(\sigma\) y escribirá \(\gamma\) en su lugar, luego
se moverá un cuadro a la derecha y luego
pasara al estado \(q\)
Los casos arriba descriptos son los únicos en los cuales la máquina \(M\) trabajara. O sea que si \((p,\sigma)\in(Q\times\Gamma)-D_{\delta}\) entonces \(M\) estando en estado \(p\) y con el cabezal leyendo el símbolo \(\sigma\) no puede hacer nada es decir solo permanecer quieta en el lugar de la cinta que este. También si \(\delta(p,\sigma)=(q,\gamma,L)\), entonces cuando \(M\) este en estado \(p\), con su cabezal escaneando la primer casilla y en la cual este dibujado el símbolo \(\sigma\), \(M\) no podrá hacer nada, lo cual es razonable ya que la cinta no es extensible hacia la izquierda.
Si bien en nuestra definición de máquina de Turing no hay ninguna restricción acerca de la naturaleza de los elementos de \(Q\), para continuar nuestro análisis asumiremos siempre que \(Q\) es un alfabeto disjunto con \(\Gamma\). Esto nos permitirá dar definiciones matemáticas precisas que formalizaran el funcionamiento de las máquinas de Turing en el contexto de las funciones mixtas. Debería quedar claro que el hecho que solo trabajemos con máquinas en las cuales \(Q\) es un alfabeto disjunto con \(\Gamma\), no afectara la profundidad y generalidad de nuestros resultados y definiciones.
Una descripción instantánea será una palabra de la forma \(\alpha q\beta\), donde \(\alpha,\beta\in\Gamma^{\ast}\), \(\left[\beta\right]_{\left\vert \beta\right\vert }\neq B\) y \(q\in Q\). Nótese que la condición \(\left[\beta\right]_{\left\vert \beta\right\vert }\neq B\) nos dice que \(\beta=\varepsilon\) o el último símbolo de \(\beta\) es distinto de \(B\). La descripción instantánea \(\alpha_{1}...\alpha_{n}q\beta_{1}...\beta_{m}\), con \(\alpha_{1},...,\alpha_{n}\), \(\beta_{1},...,\beta_{m}\in\Gamma\), \(n,m\geq0\) representara la siguiente situación \[\begin{array}{cccccccccccc} \alpha_{1} & \alpha_{2} & ... & \alpha_{n} & \beta_{1} & \beta_{2} & ... & \beta_{m} & B & B & B & ...\\ & & & & \uparrow\\ & & & & q \end{array}\] Nótese que aquí \(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 situación \[\begin{array}{cccccccccccc} \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 situación \[\begin{array}{cccccccccccc} \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 situación \[\begin{array}{cccccccccccc} B & B & B & ...\\ \uparrow\\ q \end{array}\] La condición de que en una descripción instantánea \(\alpha q\beta\) deba suceder que \(\left[\beta\right]_{\left\vert \beta\right\vert }\neq B\) es para que haya una correspondencia biunívoca entre descripciones instantáneas y situaciones de funcionamiento de la máquina. Dejamos al lector meditar sobre esto hasta convencerse de su veracidad. Pero siempre debe tener presente que las descripciones instantáneas son palabras que describen una situación real de algún instante en el funcionamiento de la máquina
Usaremos \(Des\) para denotar el conjunto de las descripciones instantáneas. Definamos la función \(St:Des\rightarrow Q\), de la siguiente manera \[St(d)=\text{unico simbolo de }Q\text{ que ocurre en }d\]
Dado \(\alpha\in(Q\cup\Gamma)^{\ast}\), definamos \(\left\lfloor \alpha\right\rfloor\) de la siguiente manera \[\begin{aligned} \left\lfloor \varepsilon\right\rfloor & =\varepsilon\\ \left\lfloor \alpha\sigma\right\rfloor & =\alpha\sigma\text{, si }\sigma\neq B\\ \left\lfloor \alpha B\right\rfloor & =\left\lfloor \alpha\right\rfloor \end{aligned}\] Es decir \(\left\lfloor \alpha\right\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=\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.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha^{\curvearrowleft}=\left\{ \begin{array}{lll} \left[\alpha\right]_{1}...\left[\alpha\right]_{\left\vert \alpha\right\vert -1} & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right.\]
Observación: Nótese que si \(\alpha p\beta\) es una descripción instantánea, entonces en la situación real que ella describe la cabeza lectora de la máquina esta leyendo el símbolo \(\left[\beta B\right]_{1}\) (o sea el 1er símbolo de \(\beta\) si \(\beta\neq\varepsilon\) y \(B\) en caso contrario). Esta forma cheta de describir que símbolo lee la cabeza lectora nos será útil para definir a continuación la relación \(\vdash\). Dadas \(d_{1},d_{2}\in Des\), escribiremos \(d_{1}\vdash 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{aligned} d_{1} & =\alpha p\beta\\ \delta\left(p,\left[\beta B\right]_{1}\right) & =(q,\sigma,R)\\ d_{2} & =\alpha\sigma q^{\curvearrowright}\beta \end{aligned}\]
Caso 2. \[\begin{aligned} d_{1} & =\alpha p\beta\\ \delta\left(p,\left[\beta B\right]_{1}\right) & =(q,\sigma,L)\text{ y }\alpha\neq\varepsilon\\ d_{2} & =\left\lfloor \alpha^{\curvearrowleft}q\left[\alpha\right]_{\left\vert \alpha\right\vert }\sigma^{\curvearrowright}\beta\right\rfloor \end{aligned}\]
Caso 3. \[\begin{aligned} d_{1} & =\alpha p\beta\\ \delta(p,\left[\beta B\right]_{1}) & =(q,\sigma,K)\\ d_{2} & =\left\lfloor \alpha q\sigma^{\curvearrowright}\beta\right\rfloor \end{aligned}\] Escribiremos \(d\nvdash d^{\prime}\) para expresar que no se da \(d\vdash d^{\prime}\). Para \(d,d^{\prime}\in Des\) y \(n\geq0\), escribiremos \(d\overset{n}{\vdash}d^{\prime}\) si existen \(d_{1},...,d_{n+1}\in Des\) tales que \[\begin{aligned} d & =d_{1}\\ d^{\prime} & =d_{n+1}\\ d_{i} & \vdash d_{i+1}\text{, para }i=1,...,n. \end{aligned}\] Nótese que \(d\overset{0}{\vdash}d^{\prime}\) sii \(d=d^{\prime}\). Finalmente definamos \[d\overset{\ast}{\vdash}d^{\prime}\text{ sii }(\exists n\in\omega)\;d\overset{n}{\vdash}d^{\prime}\text{.}\]
Dada \(d\in Des\), diremos que \(M\) se detiene partiendo de \(d\) si existe \(d^{\prime}\in Des\) tal que
adhocprefix-adhocsufix \(d\overset{\ast}{\vdash}d^{\prime}\)
adhocprefix-adhocsufix \(d^{\prime}\nvdash d^{\prime\prime}\), para cada \(d^{\prime\prime}\in Des\)
Debería quedar claro que es posible que \(\alpha p\beta\nvdash d\), para cada descripción instantánea \(d\), y que \(\delta(p,[\beta B]_{1})\) sea no vacío.
Diremos que una palabra \(\alpha\in\Sigma^{\ast}\) es aceptada por \(M\) por alcance de estado final cuando \[\left\lfloor q_{0}B\alpha\right\rfloor \overset{\ast}{\vdash}d\text{, con }d\text{ tal que }St(d)\in F.\] El lenguaje aceptado por \(M\) por alcance de estado final se define de la siguiente manera \[L(M)=\{\alpha\in\Sigma^{\ast}:\alpha\text{ es aceptada por }M\text{ por alcance de estado final}\}\text{.}\]
Diremos que una palabra \(\alpha\in\Sigma^{\ast}\) es aceptada por \(M\) por detención cuando \(M\) se detiene partiendo de \(\left\lfloor q_{0}B\alpha\right\rfloor\). El lenguaje aceptado por \(M\) por detención se define de la siguiente manera \[H(M)=\{\alpha\in\Sigma^{\ast}:\alpha\text{ es aceptada por }M\text{ por detencion}\}\]
Para poder computar funciones mixtas con una máquina de Turing necesitaremos un símbolo para representar números sobre la cinta. Llamaremos a este símbolo unit y lo denotaremos con \(\shortmid\). Mas formalmente una máquina de Turing con unit es una 8-upla \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,\shortmid,F\right)\) tal que \(\left(Q,\Sigma,\Gamma,\delta,q_{0},B,F\right)\) es una máquina de Turing y \(\shortmid\) es un símbolo distinguido perteneciente a \(\Gamma-(\{B\}\cup\Sigma)\).
Diremos que una función \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) es \(\Sigma\)-Turing computable si existe una máquina de Turing con unit, \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,\shortmid,F\right)\) tal que:
adhocprefix(1)adhocsufix Si \((\vec{x},\vec{\alpha})\in D_{f}\), entonces hay un \(p\in Q\) tal que \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor \overset{\ast}{\vdash}\left\lfloor pBf(\vec{x},\vec{\alpha})\right\rfloor\] y \(\left\lfloor pBf(\vec{x},\vec{\alpha})\right\rfloor \nvdash d\), para cada \(d\in Des\)
adhocprefix(2)adhocsufix Si \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}-D_{f}\), entonces \(M\) no se detiene partiendo de \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor .\]
En forma similar, una función \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast}{}^{m}\rightarrow\omega\), es llamada \(\Sigma\)-Turing computable si existe una máquina de Turing con unit, \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,\shortmid,F\right)\), tal que:
adhocprefix(1)adhocsufix Si \((\vec{x},\vec{\alpha})\in D_{f}\), entonces hay un \(p\in Q\) tal que \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor \overset{\ast}{\vdash}\left\lfloor pB\shortmid^{f(\vec{x},\vec{\alpha})}\right\rfloor\] y \(\left\lfloor pB\shortmid^{f(\vec{x},\vec{\alpha})}\right\rfloor \nvdash d\), para cada \(d\in Des\)
adhocprefix(2)adhocsufix Si \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}-D_{f}\), entonces \(M\) no se detiene partiendo de \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor\]
Cabe destacar que la condición \[\left\lfloor pBf(\vec{x},\vec{\alpha})\right\rfloor \nvdash d,\text{ para cada }d\in Des\] es equivalente a que \((p,B)\) no este en el dominio de \(\delta\) o que si lo este y que la tercer coordenada de \(\delta(p,B)\) sea \(L\).
Cuando una máquina de Turing con unit \(M\) cumpla los items (1) y (2) de la definición anterior, diremos que \(M\) computa a la función \(f\) o que \(f\) es computada por \(M\). Por supuesto esta definición no tendría sentido como modelo matemático del concepto de función \(\Sigma\)-efectivamente computable si no sucediera que toda función \(\Sigma\)-Turing computable fuera \(\Sigma\)-efectivamente computable. Este hecho es intuitivamente claro y lo presentamos a continuación en forma de proposición. En algún sentido esto nos dice que el paradigma filosófico es mas amplio (o igual) al paradigma de Turing. Para darle un toque de humor expresaremos esto diciendo que Leibniz vence a Turing.
4.1 (Leibniz vence a Turing). Sean \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast}{}^{m}\rightarrow O\) es computada por una máquina de Turing con unit \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,\shortmid,F\right)\), entonces \(f\) es \(\Sigma\)-efectivamente computable.
Proof. Haremos el caso \(O=\Sigma^{\ast}\). Sea \(\mathbb{P}\) el siguiente procedimiento efectivo.
- Conjunto de datos de entrada de \(\mathbb{P}\) igual a \(\omega^{n}\times\Sigma^{\ast}{}^{m}\)
- Conjunto de datos de salida de \(\mathbb{P}\) contenido en \(O\)
- Funcionamiento: Hacer funcionar paso a paso la máquina \(M\) partiendo de la descripción instantánea \(\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor\). Si en alguna instancia \(M\) termina, dar como salida el resultado de remover de la descripción instantánea final los dos primeros símbolos.
Nótese que este procedimiento termina solo en aquellos elementos \((\vec{x},\vec{\sigma})\in\omega^{n}\times\Sigma^{\ast}{}^{m}\) tales que la máquina \(M\) termina partiendo desde \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor\] por lo cual termina solo en los elementos de \(D_{f}\) ya que \(M\) computa a \(f\). Además es claro que en caso de terminación el procedimiento da como salida \(f(\vec{x},\vec{\sigma})\).
Sin embargo el modelo Turingniano podría a priori no ser del todo correcto ya que podría pasar que haya una función que sea computada por un procedimiento efectivo pero que no exista una máquina de Turing que la compute. En otras palabras el modelo podría ser incompleto. La completitud de este modelo puede no ser clara al comienzo pero a medida que vayamos avanzando en nuestro estudio y conozcamos además los otros paradigmas y su relación, quedara claro que el modelo de Turing es acertado, es decir que también pasa que Turing vence a Leibniz.
Ya que la noción de función \(\Sigma\)-Turing computable es el modelo matemático de Turing del concepto de función \(\Sigma\)-efectivamente computable, nos podríamos preguntar entonces cual es el modelo matemático de Turing del concepto de conjunto \(\Sigma\)-efectivamente enumerable. Si prestamos atención a la definición de conjunto \(\Sigma\)-efectivamente enumerable, notaremos que depende de la existencia de cierta función \(F\) por lo cual la siguiente definición cae de maduro:
Diremos que un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) será llamado \(\Sigma\)-Turing enumerable cuando sea vacío o haya una función \(F:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tal que \(I_{F}=S\) y \(F_{(i)}\) sea \(\Sigma\)-Turing computable, para cada \(i\in\{1,...,n+m\}\).
Debería quedar claro que si el concepto de función \(\Sigma\)-Turing computable modeliza correctamente al concepto de función \(\Sigma\)-efectivamente computable, entonces el concepto de conjunto \(\Sigma\)-Turing enumerable recién definido modeliza correctamente al concepto de conjunto \(\Sigma\)-efectivamente enumerable. Nótese que según la definición que acabamos de escribir, un conjunto no vacío \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es \(\Sigma\)-Turing enumerable si y solo si hay máquinas de Turing con unit \[\begin{aligned} M_{1} & =\left(Q_{1},\Sigma,\Gamma_{1},\delta_{1},q_{01},B,\shortmid,F_{1}\right)\\ M_{2} & =\left(Q_{2},\Sigma,\Gamma_{2},\delta_{2},q_{02},B,\shortmid,F_{2}\right)\\ & \vdots\\ M_{n+m} & =\left(Q_{n+m},\Sigma,\Gamma_{n+m},\delta_{n+m},q_{0n+m},B,\shortmid,F_{n+m}\right) \end{aligned}\] tales que
adhocprefix-adhocsufix cada \(M_{i}\), con \(i=1,...,n\), computa una función \(F_{i}:\omega\rightarrow\omega\)
adhocprefix-adhocsufix cada \(M_{i}\), con \(i=n+1,...,n+m\), computa una función \(F_{i}:\omega\rightarrow\Sigma^{\ast}\)
adhocprefix-adhocsufix \(S=\mathrm{Im}([F_{1},...,F_{n+m}])\)
Como puede notarse las máquinas \(M_{1},...,M_{n+m}\) puestas secuencialmente a funcionar desde la descripciones instantáneas \[\begin{aligned} & \left\lfloor q_{01}B\shortmid^{x}\right\rfloor \\ & \left\lfloor q_{02}B\shortmid^{x}\right\rfloor \\ & \ \ \ \ \ \ \ \ \ \vdots\\ & \left\lfloor q_{0n+m}B\shortmid^{x}\right\rfloor \end{aligned}\] 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 máquinas \(M_{1},...,M_{n+m}\) enumeran a \(S\). La siguiente proposición muestra que también las cosas se pueden hacer con una sola máquina de Turing.
4.2. Sea \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) un conjunto no vacío. Entonces \(S\) es \(\Sigma\)-Turing enumerable si y solo si hay una máquina de Turing con unit \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,\shortmid,F\right)\), tal que:
adhocprefix(1)adhocsufix Para cada \(x\in\omega\), tenemos que \(M\) se detiene partiendo de \(\left\lfloor q_{0}B\shortmid^{x}\right\rfloor\) y llega a una descripción instantánea de la forma \(\left\lfloor qB\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor\), con \((\vec{x},\vec{\alpha})\in S\).
adhocprefix(2)adhocsufix Para cada \((\vec{x},\vec{\alpha})\in S\) hay un \(x\in\omega\) tal que \(M\) se detiene partiendo de \(\left\lfloor q_{0}B\shortmid^{x}\right\rfloor\) y llega a una descripción instantánea de la forma \(\left\lfloor qB\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor\)
Proof. Queda como ejercicio ver como construir la máquina \(M\) utilizando las máquinas \(M_{1},...,M_{n+m}\) y recíprocamente ver como a partir de una máquina \(M\) con las propiedades (1) y (2) se pueden construir las máquinas \(M_{1},...,M_{n+m}\).
La versión Turingniana del concepto de conjunto \(\Sigma\)-efectivamente computable es fácil de dar: un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) será llamado \(\Sigma\)-Turing computable cuando la función \(\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 máquina de Turing con unit \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,\shortmid,F\right)\) la cual computa a \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\), es decir:
adhocprefix-adhocsufix Si \((\vec{x},\vec{\alpha})\in S\), entonces hay un \(p\in Q\) tal que \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor \overset{\ast}{\vdash}\left\lfloor pB\shortmid\right\rfloor\] y \(\left\lfloor pB\shortmid\right\rfloor \nvdash d\), para cada \(d\in Des\)
adhocprefix-adhocsufix Si \((\vec{x},\vec{\alpha})\in(\omega^{n}\times\Sigma^{\ast m})-S\), entonces hay un \(p\in Q\) tal que \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}\right\rfloor \overset{\ast}{\vdash}\left\lfloor pB\right\rfloor\] y \(\left\lfloor pB\right\rfloor \nvdash d\), para cada \(d\in Des\)
Si \(M\) es una máquina de Turing la cual computa a \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\), diremos que \(M\) decide la pertenencia a \(S\), con respecto al conjunto \(\omega^{n}\times\Sigma^{\ast m}\).