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 dice si un programa de computadora en particular se detendrá cuando se ejecute con una entrada en particular, y la función U correspondiente se usa 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 terminología estándar para el concepto. ^[1]

La definición depende de una numeración de Gödel adecuada que asigna números naturales a funciones computables (dadas como máquinas de Turing ). Esta numeración debe ser lo suficientemente efectiva 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.${\ estilo de visualización T}$

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

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

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

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

Ejemplo de llamada de T ₁ . El primer argumento proporciona el código fuente (en C en lugar de un número de Gödel e ) de una función computable, a saber. la función de Collatz f . El segundo argumento da el número natural i al que se va a aplicar f . El tercer argumento da 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 xes 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.