Predicado T de Kleene

En la teoría de la computabilidad , el predicado T , estudiado por primera vez por el matemático Stephen Cole Kleene , es un conjunto particular de ternas de números naturales que se utiliza para representar funciones computables dentro de las teorías formales de la aritmética . De manera informal, el predicado T indica si un programa informático determinado se detendrá al ejecutarse con una entrada específica, y la función U correspondiente se utiliza para obtener los resultados del cálculo si el programa se detiene. Al igual que con el teorema s _mn , la notación original utilizada por Kleene se ha convertido en la terminología estándar para este concepto. ^{[ 1 ]}

La definición depende de una numeración de Gödel adecuada que asigne números naturales a las funciones computables (dadas como máquinas de Turing ). Esta numeración debe ser suficientemente efectiva como para que, dado un índice de una función computable y una entrada a la función, sea posible simular eficazmente el cálculo de la función con esa entrada.${\displaystyle T}$El predicado se obtiene formalizando esta simulación.

La relación ternaria${\displaystyle T_{1}(e,i,x)}$toma tres números naturales como argumentos.${\displaystyle T_{1}(e,i,x)}$es cierto si${\displaystyle x}$codifica un historial de computación de la función computable con índice${\displaystyle e}$cuando se ejecuta con entrada${\displaystyle i}$y el programa se detiene como último paso de este historial de computación. Es decir,

• ${\displaystyle T_{1}}$primero pregunta si${\displaystyle x}$es el número de Gödel de una secuencia finita${\displaystyle \langle x_{j}\rangle }$de configuraciones completas de la máquina de Turing con índice${\displaystyle e}$, realizando un cálculo en la entrada${\displaystyle i}$.
• En ese caso,${\displaystyle T_{1}}$Luego pregunta si esta secuencia comienza con el estado inicial del cálculo y si cada elemento sucesivo de la secuencia corresponde a un solo paso de la máquina de Turing.
• Si lo hace,${\displaystyle T_{1}}$finalmente pregunta si la secuencia${\displaystyle \langle x_{j}\rangle }$finaliza con la máquina en estado de parada.

Si las tres preguntas tienen una respuesta afirmativa, entonces${\displaystyle T_{1}(e,i,x)}$es verdadero, de lo contrario, es falso.

El${\displaystyle T_{1}}$El predicado es recursivo primitivo en el sentido de que existe una función recursiva primitiva que, dados los datos de entrada para el predicado, determina correctamente el valor de verdad del predicado sobre esos datos de entrada.

Existe una función recursiva primitiva correspondiente.${\displaystyle U}$de tal manera que si${\displaystyle T_{1}(e,i,x)}$entonces es cierto${\displaystyle U(x)}$devuelve la salida de la función con índice${\displaystyle e}$en la entrada${\displaystyle i}$.

Debido a que el formalismo de Kleene adjunta una serie de entradas a cada función, el predicado${\displaystyle T_{1}}$Solo se puede utilizar para funciones que toman una entrada. Hay predicados adicionales para funciones con múltiples entradas; la relación

${\displaystyle T_{k}(e,i_{1},\ldots ,i_{k},x)}$

es cierto si${\displaystyle x}$codifica un cálculo de parada de la función con índice${\displaystyle e}$en las entradas${\displaystyle i_{1},\ldots ,i_{k}}$.

Como${\displaystyle T_{1}}$todas las funciones${\displaystyle T_{k}}$son recursivas primitivas. Debido a esto, cualquier teoría de la aritmética que sea capaz de representar cada función recursiva primitiva es capaz de representar${\displaystyle T}$y${\displaystyle U}$Algunos ejemplos de este tipo de teorías aritméticas son la aritmética de Robinson y teorías más sólidas como la aritmética de Peano .

El${\displaystyle T_{k}}$Los predicados pueden utilizarse para obtener el teorema de la forma normal de Kleene para funciones computables (Soare 1987, p.  15; Kleene 1943, pp.  52-53 ). Esto establece que existe una función recursiva primitiva fija .${\displaystyle U}$de tal manera que una función${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$es computable si y solo si hay un número${\displaystyle e}$de tal manera que para todos${\displaystyle n_{1},\ldots ,n_{k}}$uno tiene

${\displaystyle f(n_{1},\ldots ,n_{k})\simeq U(\mu x\,T_{k}(e,n_{1},\ldots ,n_{k},x))}$,

donde μ es el operador μ (${\displaystyle \mu x\,\phi (x)}$es el número natural más pequeño para el cual${\displaystyle \phi (x)}$es cierto) y${\displaystyle \simeq }$es cierto si ambos lados no están definidos o si ambos están definidos y son iguales. Según el teorema, la definición de toda función recursiva general f puede reescribirse en una forma normal tal que el operador μ se utilice solo una vez, es decir, inmediatamente debajo del operador más alto.${\displaystyle U}$, que es independiente de la función computable${\displaystyle f}$.

Además de codificar la computabilidad, el predicado T se puede utilizar para generar conjuntos completos en la jerarquía aritmética . En particular, el conjunto

${\displaystyle K=\{e{\mbox{ }}:{\mbox{ }}\exists xT_{1}(e,0,x)\}}$

que tiene el mismo grado de Turing que el problema de la parada , es un${\displaystyle \Sigma _{1}^{0}}$relación unaria completa (Soare 1987, pp.  28, 41). Más generalmente, el conjunto

${\displaystyle K_{n+1}=\{\langle e,a_{1},\ldots ,a_{n}\rangle$ :\exists xT_{n}(e,a_{1},\ldots ,a_{n},x)\}}

es un${\displaystyle \Sigma _{1}^{0}}$-predicado ( n +1)-ario completo. Por lo tanto, una vez que se obtiene una representación del predicado T _n en una teoría de la aritmética, una representación de un${\displaystyle \Sigma _{1}^{0}}$-A partir de él se puede obtener un predicado completo.

Esta construcción puede extenderse a niveles superiores de la jerarquía aritmética, como en el teorema de Post (compárese con Hinman 2005, p.  397). Por ejemplo, si un conjunto${\displaystyle A\subseteq \mathbb {N} ^{k+1}}$es${\displaystyle \Sigma _{n}^{0}}$entonces completa el conjunto

${\displaystyle \{\langle a_{1},\ldots ,a_{k}\rangle$ :\forall x(\langle a_{1},\ldots ,a_{k},x\rangle \in A)\}}

es${\displaystyle \Pi _ {n+1}^{0}}$completo.

• Peter Hinman, 2005, Fundamentos de lógica matemática , AK Peters. ISBN 978-1-56881-262-5
• Kleene, Stephen Cole (enero de 1943). "Predicados y cuantificadores recursivos" (PDF) . Transactions of the American Mathematical Society . 53 (1): 41– 73. doi : 10.1090/S0002-9947-1943-0007371-8 .Reimpreso en The Undecidible , Martin Davis, ed., 1965, pp.  255 – 287.
• — , 1952, Introducción a la metamatemática , North-Holland. Reimpreso por Ishi Press, 2009, ISBN 0-923891-57-9.
• — , 1967. Lógica matemática, John Wiley. Reimpreso por Dover, 2001, ISBN 0-486-42533-9.
• Robert I. Soare , 1987, Conjuntos y grados recursivamente enumerables, Perspectivas en lógica matemática, Springer. ISBN 0-387-15299-7