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 triples de números naturales que se usa 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 la terminología estándar para el concepto. [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 eficaz 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 en esa entrada. El predicado se obtiene formalizando esta simulación.
La relación ternaria toma tres números naturales como argumentos. es verdadero 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,
Si las tres preguntas tienen una respuesta positiva, entonces es verdadera; de lo contrario, es falsa.
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.
Existe una función recursiva primitiva correspondiente tal que, si es verdadera, devuelve la salida de la función con índice en la entrada .
