Teorema de Post

---

En la teoría de la computabilidad, el teorema de Post , que lleva el nombre de Emil Post , describe la conexión entre la jerarquía aritmética y los grados de Turing .

El enunciado del teorema de Post utiliza varios conceptos relacionados con la definibilidad y la teoría de la recursividad . Esta sección 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 se pueden definir 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 frente) con alternancias entre cuantificadores existenciales y universales aplicados a una fórmula con cuantificadores limitados únicamente. 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}}$

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 se puede definir mediante una fórmula, es decir, si hay una fórmula tal que cada número está en si y solo si se cumple. Se sabe que si un conjunto es entonces es para cualquiera , pero para cada m hay un conjunto que no lo es . Por 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}}$

---