Predicado T de Kleene

Concepto en la teoría de la computabilidad

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 triples 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 en particular se detendrá cuando se ejecute con una entrada particular, 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 el concepto. ^[1]

Definición

Ejemplo de llamada de T ₁ . El primer argumento proporciona el código fuente (en C en lugar de como un número de Gödel e ) de una función computable, a saber, la función de Collatz f . El segundo argumento proporciona el número natural i al que se aplicará f . El tercer argumento proporciona una secuencia x de pasos de cálculo que simulan la evaluación de f en i (como una cadena de ecuaciones en lugar de un número de secuencia de Gödel). La llamada de predicado se evalúa como verdadera ya que x es en realidad la secuencia de cálculo correcta para la llamada f (5), y termina con una expresión que ya no involucra a f . La función U , aplicada a la secuencia x , devolverá su expresión final, a saber, 1.

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

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

• ${\displaystyle T_{1}}$Primero pregunta si es el número de Gödel de una secuencia finita de configuraciones completas de la máquina de Turing con índice , ejecutando un cálculo en la entrada . ${\displaystyle x}$ ${\displaystyle \langle x_{j}\rangle }$ ${\displaystyle e}$ ${\displaystyle i}$
• Si es así, entonces pregunta si esta secuencia comienza con el estado inicial del cálculo y cada elemento sucesivo de la secuencia corresponde a un solo paso de la máquina de Turing. ${\displaystyle T_{1}}$
• Si es así, finalmente pregunta si la secuencia termina con la máquina en un estado de detención. ${\displaystyle T_{1}}$ ${\displaystyle \langle x_{j}\rangle }$

Si las tres preguntas tienen una respuesta positiva, entonces es verdadero; en caso contrario, es falso. ${\displaystyle T_{1}(e,i,x)}$

El predicado es recursivo primitivo en el sentido de que existe una función recursiva primitiva que, dadas las entradas para el predicado, determina correctamente el valor de verdad del predicado en esas entradas. ${\displaystyle T_{1}}$

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

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

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

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

Al igual que , todas las funciones son recursivas primitivas. Por ello, cualquier teoría aritmética que sea capaz de representar cada función recursiva primitiva es capaz de representar y . Entre los ejemplos de tales teorías aritméticas se incluyen la aritmética de Robinson y teorías más sólidas como la aritmética de Peano . ${\displaystyle T_{1}}$ ${\displaystyle T_{k}}$ ${\displaystyle T}$ ${\displaystyle U}$

Teorema de la forma normal

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

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

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

Jerarquía aritmética

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 es del mismo grado de Turing que el problema de detención , es una relación unaria completa (Soare 1987, pp. 28, 41). De manera más general, el conjunto ${\displaystyle \Sigma _{1}^{0}}$

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

es un 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, se puede obtener una representación de un predicado -completo a partir de él. ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$

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 es completo, entonces el conjunto ${\displaystyle A\subseteq \mathbb {N} ^{k+1}}$ ${\displaystyle \Sigma _{n}^{0}}$

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

está completo ${\displaystyle \Pi _{n+1}^{0}}$

Notas

1. El predicado descrito aquí fue presentado en (Kleene 1943) y (Kleene 1952), y es lo que usualmente se denomina " predicado T de Kleene ". (Kleene 1967) utiliza la letra T para describir un predicado diferente relacionado con funciones computables, pero que no puede utilizarse para obtener el teorema de la forma normal de Kleene.

Referencias

• Peter Hinman, 2005, Fundamentos de lógica matemática , AK Peters. ISBN  978-1-56881-262-5
• Stephen Cole Kleene (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 Undecidable , Martin Davis, ed., 1965, págs. 255–287.
• —, 1952, Introducción a las metamatemáticas , Holanda Septentrional. 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 enumerables recursivamente, Perspectivas en lógica matemática, Springer. ISBN 0-387-15299-7