13.5: Representando Máquinas Turing

Template:MathJaxZach

Para representar las máquinas Turing y su comportamiento mediante una frase de lógica de primer orden, tenemos que definir un lenguaje adecuado. El lenguaje consta de dos partes: símbolos predicados para describir configuraciones de la máquina, y expresiones para numerar pasos de ejecución (“momentos”) y posiciones en la cinta.

Introducimos dos tipos de símbolos predicados, ambos de 2 lugares: Para cada estado\(q\), un símbolo de predicado\(\Obj Q_q\), y para cada símbolo de cinta\(\sigma\), un símbolo de predicado\(\Obj S_\sigma\). El primero nos permite describir el estado\(M\) y la posición de su cabeza de cinta, este último nos permite describir el contenido de la cinta.

Para expresar las posiciones del cabezal de cinta y el número de pasos ejecutados, necesitamos una forma de expresar números. Esto se hace usando un símbolo constante\(\Obj 0\), y una función\(1\) -place\(\prime\), la función sucesora. Por convención se escribe después de su argumento (y dejamos fuera los paréntesis). Entonces\(\Obj 0\) nombra la posición más a la izquierda en la cinta así como el tiempo antes del primer paso de ejecución (la configuración inicial),\(\Obj 0'\) nombra el cuadrado a la derecha del cuadrado más a la izquierda, y el tiempo después del primer paso de ejecución, y así sucesivamente. También introducimos un símbolo predicado\(<\) para expresar tanto el orden de las posiciones de la cinta (cuando significa “a la izquierda de”) como los pasos de ejecución (entonces significa “antes”).

Una vez que tenemos el lenguaje en su lugar, enumeramos los “axiomas” de\(T(M, w)\), es decir, las oraciones que, tomadas en conjunto, describen el comportamiento de\(M\) cuando se ejecutan en entrada\(w\). Habrá oraciones que establezcan condiciones sobre\(\Obj 0\), y\(\prime\)\(<\), oraciones que describen la configuración de entrada, y oraciones que describen cuál\(M\) es la configuración después de ejecutar una instrucción particular.

Definición\(\PageIndex{1}\)

Dada una máquina Turing\(M = \tuple{Q, \Sigma, q_0, \delta}\), el lenguaje\(\Lang L_M\) consiste en:

1. Un símbolo de predicado de dos lugares\(\Obj Q_q(x, y)\) para cada estado\(q \in Q\). Intuitivamente,\(\Obj Q_q(\num{m}, \num{n})\) expresa “después de\(n\) pasos,\(M\) está en estado\(q\) escaneando el cuadrado\(m\) th”.

2. Un símbolo de predicado de dos\(\Obj S_\sigma(x, y)\) posiciones para cada símbolo\(\sigma\in \Sigma\). Intuitivamente,\(\Obj S_\sigma(\num{m}, \num{n})\) expresa “después de\(n\) los pasos, el cuadrado\(m\) th contiene símbolo”\(\sigma\).

3. Un símbolo constante\(\Obj 0\)

4. Un símbolo de función de un solo lugar\(\prime\)

5. Un símbolo de predicado de dos posiciones\(<\)

Para cada número\(n\) hay un término canónico\(\num{n}\), el numeral para\(n\), que lo representa en\(\Lang L_M\). \(\num{0}\)es\(\Obj 0\),\(\num{1}\) es\(\Obj 0'\),\(\num{2}\) es\(\Obj 0''\), y así sucesivamente. Más formalmente:\[\begin{aligned} \num{0} & = \Obj 0 \\ \num{n+1} &= \num{n}'\end{aligned}\]

Las frases que describen el funcionamiento de la máquina Turing\(M\) en la entrada\(w = \sigma_{i_1}\dots\sigma_{i_k}\) son las siguientes:

1. Axiomas que describen números:

   1. Una frase que dice que la función sucesora es inyectiva:\[\lforall{x}{\lforall{y}{ (\eq[x'][y'] \lif \eq[x][y])}}\nonumber\]

   2. Una frase que dice que cada número es menor que su sucesor:\[\lforall{x}{x < x'}\nonumber\]

   3. Una frase que asegura que\(<\) es transitiva:\[\lforall{x}{\lforall{y}{\lforall{z}{ ((x < y \land y < z) \lif x < z)}}}\nonumber\]

   4. Una frase que conecta\(<\) y\(=\):\[\lforall{x}{\lforall{y}{(x < y \lif \eqN[x][y])}}\nonumber\]

2. Axiomas que describen la configuración de entrada:

   1. Después\(0\) de los pasos, antes de que la máquina arranque,\(M\) está en el estado inicial\(q_0\), escaneando el cuadrado\(1\):\[\Obj Q_{q_0}(\num{1}, \num{0})\nonumber\]

   2. Los primeros\(k+1\) cuadrados contienen los símbolos\(\TMendtape\),\(\sigma_{i_1}\),...,\(\sigma_{i_k}\):\[\Obj S_\TMendtape(\num{0}, \num{0}) \land \Obj S_{\sigma_{i_1}}(\num{1}, \num{0}) \land \dots \land \Obj S_{\sigma_{i_k}}(\num{k}, \num{0})\nonumber\]

   3. De lo contrario, la cinta está vacía:\[\lforall{x}{(\num{k} < x \lif \Obj S_\TMblank(x, \num{0}))}\nonumber\]

3. Axiomas que describen la transición de una configuración a la siguiente:

   Para lo siguiente, deje\(A(x, y)\) ser la conjunción de todas las oraciones de la forma\[\lforall{z}{ (((z < x \lor x < z) \land \Obj S_\sigma(z, y)) \lif \Obj S_\sigma(z, y'))}\nonumber\] donde\(\sigma \in \Sigma\). Usamos\(A(\num{m},\num{n})\) para expresar “aparte de en cuadrado\(m\), la cinta después de los\(n+1\) pasos es la misma que después de\(n\) los pasos”.

   1. Por cada instrucción\(\delta(q_i, \sigma) = \tuple{q_j, \sigma', \TMright}\), la frase:\[\begin{aligned} & \lforall{x}{\lforall{y}{( (\Obj Q_{q_i}(x, y) \land \Obj S_{\sigma}(x, y)) \lif {}}} \\ &\qquad (\Obj Q_{q_j}(x', y') \land \Obj S_{\sigma'}(x, y') \land A(x, y)))\end{aligned}\] Esto dice que si, después de\(y\) los pasos, la máquina está en el estado de\(q_i\) escaneo cuadrado\(x\) que contiene símbolo\(\sigma\), entonces después \(y+1\)pasos está escaneando cuadrado\(x+1\), está en estado\(q_j\), cuadrado\(x\) ahora contiene\(\sigma'\), y cada cuadrado que no sea\(x\) contiene el mismo símbolo que lo hizo después\(y\) pasos.

   2. Por cada instrucción\(\delta(q_i, \sigma) = \tuple{q_j, \sigma', \TMleft}\), la frase:\[\begin{aligned} & \lforall{x}{\lforall{y}{ ((\Obj Q_{q_i}(x', y) \land \Obj S_{\sigma}(x', y)) \lif {}}}\\ & \qquad (\Obj Q_{q_j}(x, y') \land \Obj S_{\sigma'}(x', y') \land A(x, y))) \land {}\\ & \lforall{y}{((\Obj Q_{q_i}(\Obj 0, y) \land \Obj S_{\sigma}(\Obj 0, y)) \lif {}}\\ & \qquad (\Obj Q_{q_j}(\Obj 0, y') \land \Obj S_{\sigma'}(\Obj 0, y') \land A(\Obj 0, y)))\end{aligned}\] Tómese un momento para pensar en cómo funciona esto: ahora no empezamos con “si escanea cuadrado\(x\)...” sino: “si escanea cuadrado\(x+1\)...” Un movimiento hacia la izquierda significa que en el siguiente paso la máquina está escaneando cuadrados\(x\). Pero el cuadrado en el que está escrito es\(x+1\). Lo hacemos de esta manera ya que no tenemos resta ni una función predecesora.

      Tenga en cuenta que los números del formulario\(x+1\) son\(1\),\(2\),..., es decir, esto no cubre el caso en el que la máquina está escaneando cuadrados\(0\) y se supone que debe moverse hacia la izquierda (que por supuesto no puede—simplemente se queda en su lugar). Ese caso especial está cubierto por la segunda conjunción: dice que si, después de\(y\) los pasos, la máquina está escaneando cuadrado\(0\) en estado\(q_i\) y cuadrado\(0\) contiene símbolo\(\sigma\), entonces después \(y+1\)pasos sigue escaneando cuadrados\(0\), ahora está en estado\(q_j\), el símbolo en el cuadrado\(0\) es\(\sigma'\), y los cuadrados distintos al cuadrado\(0\) contienen los mismos símbolos que contenían a menudo \(y\)pasos.

   3. Por cada instrucción\(\delta(q_i, \sigma) = \tuple{q_j, \sigma', \TMstay}\), la frase:\[\begin{aligned} & \lforall{x}{\lforall{y}{( (\Obj Q_{q_i}(x, y) \land \Obj S_{\sigma}(x, y)) \lif {}}} \\ &\qquad (\Obj Q_{q_j}(x, y') \land \Obj S_{\sigma'}(x, y') \land A(x, y)))\end{aligned}\]

Dejar\(T(M, w)\) ser la conjunción de todas las frases anteriores para máquina de Turing\(M\) y entrada\(w\).

Para expresar que\(M\) eventualmente se detiene, tenemos que encontrar una frase que diga “después de algún número de pasos, la función de transición estará indefinida”. Dejar\(X\) ser el conjunto de todos los pares\(\tuple{q, \sigma}\) tal que\(\delta(q, \sigma)\) esté indefinido. Que\(E(M, w)\) entonces sea la sentencia\[\lexists{x}{\lexists{y}{(\bigvee_{\tuple{q, \sigma} \in X}(\Obj Q_q(x, y) \land \Obj S_\sigma(x, y)))}}\nonumber\]

Si usamos una máquina Turing con un estado de detención designado\(h\), es aún más fácil: entonces la oración\(E(M, w)\)\[\lexists{x}{\lexists{y}{\Obj Q_h(x, y)}}\nonumber\] expresa que la máquina finalmente se detiene.

Proposición\(\PageIndex{1}\)

Si\(m < k\), entonces\(T(M, w) \Entails \num{m} < \num{k}\)

Comprobante. Ejercicio. ◻

Problema\(\PageIndex{1}\)

Demostrar Proposición\(\PageIndex{1}\). (Pista: usar inducción\(k-m\)).