Teorema de Post

Teorema de la teoría de la computabilidad

En la teoría de la computabilidad, el teorema de Post , llamado así en honor a Emil Post , describe la conexión entre la jerarquía aritmética y los grados de Turing .

Fondo

El enunciado del teorema de Post utiliza varios conceptos relacionados con la definibilidad y la teoría de la recursión . En esta sección se ofrece una breve descripción de estos conceptos, que se tratan en profundidad en sus respectivos artículos.

La jerarquía aritmética clasifica ciertos conjuntos de números naturales que son definibles en el lenguaje de la aritmética de Peano. Se dice que una fórmula es si es un enunciado existencial en forma normal prenex (todos los cuantificadores al principio) con alternancias entre cuantificadores existenciales y universales aplicados a una fórmula con cuantificadores acotados solamente. Formalmente, una fórmula en el lenguaje de la aritmética de Peano es una fórmula si tiene la forma ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle m}$ ${\displaystyle \phi (s)}$ ${\displaystyle \Sigma _{m}^{0}}$

${\displaystyle \left(\exists n_{1}^{1}\exists n_{2}^{1}\cdots \exists n_{j_{1}}^{1}\right)\left(\forall n_{1}^{2}\cdots \forall n_{j_{2}}^{2}\right)\left(\exists n_{1}^{3}\cdots \right)\cdots \left(Qn_{1}^{m}\cdots \right)\rho (n_{1}^{1},\ldots n_{j_{m}}^{m},x_{1},\ldots ,x_{k})}$

donde contiene solo cuantificadores acotados y Q es si m es par y si m es impar. ${\displaystyle \rho }$ ${\displaystyle \forall }$ ${\displaystyle \exists }$

Se dice que un conjunto de números naturales es si es definible mediante una fórmula, es decir, si existe una fórmula tal que cada número es si y solo si se cumple. Se sabe que si un conjunto es entonces es para cualquier , pero para cada m hay un conjunto que no es . Por lo tanto, el número de alternancias de cuantificadores necesarias para definir un conjunto da una medida de la complejidad del conjunto. ${\displaystyle A}$ ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle \phi (s)}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle \phi (n)}$ ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle n>m}$ ${\displaystyle \Sigma _{m+1}^{0}}$ ${\displaystyle \Sigma _{m}^{0}}$

El teorema de Post utiliza la jerarquía aritmética relativizada así como la jerarquía no relativizada que acabamos de definir. Se dice que un conjunto de números naturales es relativo a un conjunto , escrito , si es definible mediante una fórmula en un lenguaje extendido que incluye un predicado para la pertenencia a . ${\displaystyle A}$ ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle B}$ ${\displaystyle \Sigma _{m}^{0,B}}$ ${\displaystyle A}$ ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle B}$

Mientras que la jerarquía aritmética mide la definibilidad de conjuntos de números naturales, los grados de Turing miden el nivel de incomputabilidad de conjuntos de números naturales. Se dice que un conjunto es reducible por Turing a un conjunto , escrito , si hay una máquina de Turing oráculo que, dado un oráculo para , calcula la función característica de . El salto de Turing de un conjunto es una forma del problema de detención relativo a . Dado un conjunto , el salto de Turing es el conjunto de índices de las máquinas de Turing oráculo que se detienen en la entrada cuando se ejecutan con el oráculo . Se sabe que cada conjunto es reducible por Turing a su salto de Turing, pero el salto de Turing de un conjunto nunca es reducible por Turing al conjunto original. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\leq _{T}B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A'}$ ${\displaystyle 0}$ ${\displaystyle A}$ ${\displaystyle A}$

El teorema de Post utiliza saltos de Turing iterados finitamente. Para cualquier conjunto de números naturales, la notación indica el salto de Turing iterado de . Por lo tanto , es simplemente , y es el salto de Turing de . ${\displaystyle A}$ ${\displaystyle A^{(n)}}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle A^{(0)}}$ ${\displaystyle A}$ ${\displaystyle A^{(n+1)}}$ ${\displaystyle A^{(n)}}$

Teorema de Post y corolarios

El teorema de Post establece una estrecha conexión entre la jerarquía aritmética y los grados de Turing de la forma , es decir, saltos de Turing finitamente iterados del conjunto vacío. (El conjunto vacío podría reemplazarse por cualquier otro conjunto computable sin cambiar la verdad del teorema). ${\displaystyle \emptyset ^{(n)}}$

El teorema de Post establece:

1. Un conjunto es si y solo si es enumerable recursivamente por una máquina de Turing de oráculo con un oráculo para , es decir, si y solo si es . ${\displaystyle B}$ ${\displaystyle \Sigma _{n+1}^{0}}$ ${\displaystyle B}$ ${\displaystyle \emptyset ^{(n)}}$ ${\displaystyle B}$ ${\displaystyle \Sigma _{1}^{0,\emptyset ^{(n)}}}$
2. El conjunto es -completo para cada . Esto significa que cada conjunto es reducible muchos-uno a . ${\displaystyle \emptyset ^{(n)}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle n>0}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \emptyset ^{(n)}}$

El teorema de Post tiene muchos corolarios que exponen relaciones adicionales entre la jerarquía aritmética y los grados de Turing. Entre ellos se incluyen:

1. Fijar un conjunto . Un conjunto es si y sólo si es . Esta es la relativización de la primera parte del teorema de Post al oráculo . ${\displaystyle C}$ ${\displaystyle B}$ ${\displaystyle \Sigma _{n+1}^{0,C}}$ ${\displaystyle B}$ ${\displaystyle \Sigma _{1}^{0,C^{(n)}}}$ ${\displaystyle C}$
2. Un conjunto es si y solo si . En términos más generales, es si y solo si . ${\displaystyle B}$ ${\displaystyle \Delta _{n+1}}$ ${\displaystyle B\leq _{T}\emptyset ^{(n)}}$ ${\displaystyle B}$ ${\displaystyle \Delta _{n+1}^{C}}$ ${\displaystyle B\leq _{T}C^{(n)}}$
3. Un conjunto se define como aritmético si lo es para algún . El teorema de Post muestra que, de manera equivalente, un conjunto es aritmético si y solo si es reducible por Turing a para algún m . ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle n}$ ${\displaystyle \emptyset ^{(m)}}$

Prueba del teorema de Post

Formalización de las máquinas de Turing en aritmética de primer orden

El funcionamiento de una máquina de Turing en la entrada se puede formalizar de manera lógica en aritmética de primer orden . Por ejemplo, podemos usar los símbolos , , y para la configuración de la cinta, el estado de la máquina y la ubicación a lo largo de la cinta después de los pasos, respectivamente. El sistema de transición de determina la relación entre y ; sus valores iniciales (para ) son la entrada, el estado inicial y cero, respectivamente. La máquina se detiene si y solo si hay un número tal que es el estado de detención. ${\displaystyle T}$ ${\displaystyle n}$ ${\displaystyle A_{k}}$ ${\displaystyle B_{k}}$ ${\displaystyle C_{k}}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle (A_{k},B_{k},C_{k})}$ ${\displaystyle (A_{k+1},B_{k+1},C_{k+1})}$ ${\displaystyle k=0}$ ${\displaystyle k}$ ${\displaystyle B_{k}}$

La relación exacta depende de la implementación específica del concepto de máquina de Turing (por ejemplo, su alfabeto, modo de movimiento permitido a lo largo de la cinta, etc.)

En caso de que se detenga en el tiempo , la relación entre y debe satisfacerse sólo para k acotado desde arriba por . ${\displaystyle T}$ ${\displaystyle n_{1}}$ ${\displaystyle (A_{k},B_{k},C_{k})}$ ${\displaystyle (A_{k+1},B_{k+1},C_{k+1})}$ ${\displaystyle n_{1}}$

Por lo tanto, existe una fórmula en aritmética de primer orden sin cuantificadores ilimitados , tal que se detiene en la entrada en el tiempo como máximo si y solo si se satisface. ${\displaystyle \varphi (n,n_{1})}$ ${\displaystyle T}$ ${\displaystyle n}$ ${\displaystyle n_{1}}$ ${\displaystyle \varphi (n,n_{1})}$

Ejemplo de implementación

Por ejemplo, para una máquina de Turing sin prefijo, con alfabeto binario y sin símbolo en blanco, podemos utilizar las siguientes notaciones:

• ${\displaystyle A_{k}}$es el símbolo 1- ario para la configuración de toda la cinta después de los pasos (que podemos escribir como un número con LSB primero, siendo el valor de la m-ésima ubicación en la cinta su m-ésimo bit menos significativo). En particular , es la configuración inicial de la cinta, que corresponde a la entrada a la máquina. ${\displaystyle k}$ ${\displaystyle A_{0}}$
• ${\displaystyle B_{k}}$es el símbolo 1- ario del estado de la máquina de Turing después de los pasos. En particular, , el estado inicial de la máquina de Turing. ${\displaystyle k}$ ${\displaystyle B_{0}=q_{I}}$
• ${\displaystyle C_{k}}$es el símbolo 1- ario de la ubicación de la máquina de Turing en la cinta después de los pasos. En particular . ${\displaystyle k}$ ${\displaystyle C_{0}=0}$
• ${\displaystyle M(q,b)}$es la función de transición de la máquina de Turing, escrita como una función de un doblete (estado de la máquina, bit leído por la máquina) a un triplete (nuevo estado de la máquina, bit escrito por la máquina, movimiento +1 o -1 de la máquina a lo largo de la cinta).
• ${\displaystyle bit(j,m)}$es el j-ésimo bit de un número . Esto se puede escribir como una fórmula aritmética de primer orden sin cuantificadores ilimitados. ${\displaystyle m}$

Para una máquina de Turing sin prefijo podemos utilizar, para la entrada n, la configuración de cinta inicial donde cat representa la concatenación; por lo tanto, es una cadena de longitud de seguida de y luego de . ${\displaystyle t(n)=cat(2^{ceil(log_{2}n)}-1,0,n)}$ ${\displaystyle t(n)}$ ${\displaystyle \log(n)-}$ ${\displaystyle 1-s}$ ${\displaystyle 0}$ ${\displaystyle n}$

El funcionamiento de la máquina de Turing en los primeros pasos puede escribirse así como la conjunción de las condiciones iniciales y las fórmulas siguientes, cuantificadas para todo : ${\displaystyle n_{1}}$ ${\displaystyle k}$ ${\displaystyle k<n_{1}}$

• ${\displaystyle (B_{k+1},bit(C_{k},A_{k+1}),D)=M(B_{k},bit(C_{k},A_{k}))}$Dado que M tiene un dominio finito, esto se puede reemplazar por una fórmula aritmética de primer orden sin cuantificadores . La fórmula exacta obviamente depende de M.
• ${\displaystyle C_{k+1}=C_{k}+D}$
• ${\displaystyle \forall j:j\neq C_{k}\rightarrow bit(j,A_{k+1})=bit(j,A_{k})}$. Nótese que en los primeros pasos, nunca se llega a una posición a lo largo de la cinta mayor que . Por lo tanto, el cuantificador universal sobre j puede limitarse con +1, ya que los bits más allá de esta posición no tienen relevancia para el funcionamiento de la máquina. ${\displaystyle n_{1}}$ ${\displaystyle T}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{1}}$

T se detiene en la entrada en el tiempo como máximo si y solo si se satisface, donde: ${\displaystyle n}$ ${\displaystyle n_{1}}$ ${\displaystyle \varphi (n,n_{1})}$

${\displaystyle {\begin{aligned}\varphi (n,n_{1})=&(A_{0}=t(n))\land (B_{0}=q_{I})\land (C_{0}=0)\land (B_{n_{1}}=q_{H})\\&\land \forall k<n_{1}:((B_{k+1},bit(C_{k},A_{k+1}),1)=M(B_{k},bit(C_{k},A_{k}))\land C_{k+1}=C_{k}+1)&\\&\lor ((B_{k+1},bit(C_{k},A_{k+1}),-1)=M(B_{k},bit(C_{k},A_{k}))\land C_{k+1}=C_{k}-1))&\\&\land \forall j<n_{1}+1:j\neq C_{k}\rightarrow (bit(j,A_{k+1})=bit(j,A_{k}))&\end{aligned}}}$

Esta es una fórmula aritmética de primer orden sin cuantificadores ilimitados, es decir, está en . ${\displaystyle \Sigma _{0}^{0}}$

Conjuntos enumerables recursivamente

Sea un conjunto que puede enumerarse recursivamente mediante una máquina de Turing . Entonces, existe una máquina de Turing que para cada en , se detiene cuando se le da como entrada. ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle n}$

Esto se puede formalizar mediante la fórmula aritmética de primer orden presentada anteriormente. Los miembros de son los números que satisfacen la siguiente fórmula: ${\displaystyle S}$ ${\displaystyle n}$

${\displaystyle \exists n_{1}:\varphi (n,n_{1})}$

Esta fórmula está en . Por lo tanto, está en . Por lo tanto, todo conjunto enumerable recursivamente está en . ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle S}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$

La inversa también es cierta: para cada fórmula en con k cuantificadores existenciales, podemos enumerar las –tuplas de números naturales y ejecutar una máquina de Turing que las recorra todas hasta que encuentre que se satisface la fórmula. Esta máquina de Turing se detiene precisamente en el conjunto de números naturales que satisfacen , y así enumera su conjunto correspondiente. ${\displaystyle \varphi (n)}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle k}$ ${\displaystyle \varphi (n)}$

Máquinas Oracle

De manera similar, el funcionamiento de una máquina oráculo con un oráculo O que se detiene después de como máximo pasos de entrada se puede describir mediante una fórmula de primer orden , excepto que la fórmula ahora incluye: ${\displaystyle T}$ ${\displaystyle n_{1}}$ ${\displaystyle n}$ ${\displaystyle \varphi _{O}(n,n_{1})}$ ${\displaystyle \varphi _{1}(n,n_{1})}$

• Un nuevo predicado, , que da la respuesta del oráculo. Este predicado debe satisfacer alguna fórmula que se analizará a continuación. ${\displaystyle O_{m}}$
• Una cinta adicional -la cinta del oráculo- en la que se debe escribir el número m para cada llamada O(m) al oráculo; la escritura en esta cinta se puede formalizar lógicamente de manera similar a la escritura en la cinta de la máquina. Nótese que una máquina oráculo que se detiene después de como máximo pasos tiene tiempo para escribir como máximo dígitos en la cinta del oráculo. Por lo tanto, el oráculo solo puede ser llamado con números m que satisfagan . ${\displaystyle T}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{1}}$ ${\displaystyle m<2^{n_{1}}}$

Si el oráculo es para un problema de decisión, siempre es "Sí" o "No", que podemos formalizar como 0 o 1. Supongamos que el problema de decisión en sí mismo puede formalizarse mediante una fórmula aritmética de primer orden . Entonces se detiene después de un máximo de pasos si y solo si se cumple la siguiente fórmula: ${\displaystyle O_{m}}$ ${\displaystyle \psi ^{O}(m)}$ ${\displaystyle T}$ ${\displaystyle n}$ ${\displaystyle n_{1}}$ ${\displaystyle \varphi _{O}(n,n_{1})=\forall m<2^{n_{1}}:((\psi ^{O}(m)\rightarrow (O_{m}=1))\land (\lnot \psi ^{O}(m)\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

donde es una fórmula de primer orden sin cuantificadores ilimitados. ${\displaystyle {\varphi _{O}}_{1}(n,n_{1})}$

Salto de Turing

Si O es un oráculo para el problema de detención de una máquina , entonces es lo mismo que "existe tal que comenzando con la entrada m está en el estado de detención después de los pasos". Por lo tanto: donde es una fórmula de primer orden que formaliza . Si es una máquina de Turing (sin oráculo), es en (es decir, no tiene cuantificadores ilimitados). ${\displaystyle T'}$ ${\displaystyle \psi ^{O}(m)}$ ${\displaystyle m_{1}}$ ${\displaystyle T'}$ ${\displaystyle m_{1}}$ ${\displaystyle \psi ^{O}(m)=\exists m_{1}:\psi _{H}(m,m_{1})}$ ${\displaystyle \psi _{H}(m,m_{1})}$ ${\displaystyle T'}$ ${\displaystyle T'}$ ${\displaystyle \psi _{H}(m,m_{1})}$ ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}}$

Puesto que hay un número finito de números m que satisfacen , podemos elegir el mismo número de pasos para todos ellos: hay un número , tal que se detiene después de pasos precisamente en aquellas entradas para las que se detiene. ${\displaystyle m<2^{n_{1}}}$ ${\displaystyle m_{1}}$ ${\displaystyle T'}$ ${\displaystyle m_{1}}$ ${\displaystyle m<2^{n_{1}}}$

Pasando a la forma normal prenex , obtenemos que la máquina oráculo se detiene en la entrada si y solo si se cumple la siguiente fórmula: ${\displaystyle n}$ ${\displaystyle \varphi (n)=\exists n_{1}\exists m_{1}\forall m_{2}:(\psi _{H}(m,m_{2})\rightarrow (O_{m}=1))\land (\lnot \psi _{H}(m,m_{1})\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

(informalmente, hay un "número máximo de pasos", de modo que cada oráculo que no se detiene dentro de los primeros pasos no se detiene en absoluto; sin embargo, para cada , cada oráculo que se detiene después de los pasos sí se detiene). ${\displaystyle m_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle m_{2}}$

Tenga en cuenta que podemos reemplazar tanto y por un solo número (su máximo) sin cambiar el valor de verdad de . Por lo tanto, podemos escribir: ${\displaystyle n_{1}}$ ${\displaystyle m_{1}}$ ${\displaystyle \varphi (n)}$ ${\displaystyle \varphi (n)=\exists n_{1}\forall m_{2}:(\psi _{H}(m,m_{2})\rightarrow (O_{m}=1))\land (\lnot \psi _{H}(m,n_{1})\rightarrow (O_{m}=0)))\land {\varphi _{O}}_{1}(n,n_{1})}$

Para el oráculo del problema de detención sobre las máquinas de Turing, está en y está en . Por lo tanto, todo conjunto que sea recursivamente enumerable por una máquina de oráculo con un oráculo para , está en . ${\displaystyle \psi _{H}(m,m_{1})}$ ${\displaystyle \Pi _{0}^{0}}$ ${\displaystyle \varphi (n)}$ ${\displaystyle \Sigma _{2}^{0}}$ ${\displaystyle \emptyset ^{(1)}}$ ${\displaystyle \Sigma _{2}^{0}}$

La inversa también es cierta: supongamos que es una fórmula en con cuantificadores existenciales seguida de cuantificadores universales. De manera equivalente, tiene > cuantificadores existenciales seguidos de una negación de una fórmula en ; la última fórmula puede ser enumerada por una máquina de Turing y, por lo tanto, puede ser verificada inmediatamente por un oráculo para . ${\displaystyle \varphi (n)}$ ${\displaystyle \Sigma _{2}^{0}}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$ ${\displaystyle \varphi (n)}$ ${\displaystyle k_{1}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \emptyset ^{(1)}}$

Podemos enumerar las –tuplas de números naturales y ejecutar una máquina oráculo con un oráculo para que las recorra todas hasta encontrar una satisfacción para la fórmula. Esta máquina oráculo se detiene precisamente en el conjunto de números naturales que satisfacen , y así enumera su conjunto correspondiente. ${\displaystyle k_{1}}$ ${\displaystyle \emptyset ^{(1)}}$ ${\displaystyle \varphi (n)}$

Saltos de Turing más altos

En términos más generales, supongamos que cada conjunto que es recursivamente enumerable por una máquina oráculo con un oráculo para está en . Entonces, para una máquina oráculo con un oráculo para , está en . ${\displaystyle \emptyset ^{(p)}}$ ${\displaystyle \Sigma _{p+1}^{0}}$ ${\displaystyle \emptyset ^{(p+1)}}$ ${\displaystyle \psi ^{O}(m)=\exists m_{1}:\psi _{H}(m,m_{1})}$ ${\displaystyle \Sigma _{p+1}^{0}}$

Dado que es lo mismo que para el salto de Turing anterior, se puede construir (como acabamos de hacer con arriba) de modo que en . Después de pasar a la forma formal prenex, el nuevo está en . ${\displaystyle \psi ^{O}(m)}$ ${\displaystyle \varphi (n)}$ ${\displaystyle \varphi (n)}$ ${\displaystyle \psi _{H}(m,m_{1})}$ ${\displaystyle \Pi _{p}^{0}}$ ${\displaystyle \varphi (n)}$ ${\displaystyle \Sigma _{p+2}^{0}}$

Por inducción, cada conjunto que es enumerable recursivamente por una máquina oráculo con un oráculo para , está en . ${\displaystyle \emptyset ^{(p)}}$ ${\displaystyle \Sigma _{p+1}^{0}}$

La otra dirección también se puede demostrar por inducción: supongamos que cada fórmula en puede ser enumerada por una máquina oráculo con un oráculo para . ${\displaystyle \Sigma _{p+1}^{0}}$ ${\displaystyle \emptyset ^{(p)}}$

Ahora supongamos que es una fórmula en con cuantificadores existenciales seguidos de cuantificadores universales, etc. Equivalentemente, tiene > cuantificadores existenciales seguidos de una negación de una fórmula en ; la última fórmula puede ser enumerada por una máquina de oráculo con un oráculo para y, por lo tanto, puede ser verificada inmediatamente por un oráculo para . ${\displaystyle \varphi (n)}$ ${\displaystyle \Sigma _{p+2}^{0}}$ ${\displaystyle k_{1}}$ ${\displaystyle k_{2}}$ ${\displaystyle \varphi (n)}$ ${\displaystyle k_{1}}$ ${\displaystyle \Sigma _{p+1}^{0}}$ ${\displaystyle \emptyset ^{(p)}}$ ${\displaystyle \emptyset ^{(p+1)}}$

Podemos enumerar las –tuplas de números naturales y ejecutar una máquina oráculo con un oráculo para que las recorra todas hasta encontrar una satisfacción para la fórmula. Esta máquina oráculo se detiene precisamente en el conjunto de números naturales que satisfacen , y así enumera su conjunto correspondiente. ${\displaystyle k_{1}}$ ${\displaystyle \emptyset ^{(p+1)}}$ ${\displaystyle \varphi (n)}$

Referencias

Rogers, H. La teoría de funciones recursivas y computabilidad efectiva , MIT Press. ISBN  0-262-68052-1 ; ISBN 0-07-053522-1 

Soare, R. Conjuntos y grados enumerables de forma recursiva. Perspectivas en lógica matemática. Springer-Verlag, Berlín, 1987. ISBN 3-540-15299-7