Predicado T de Kleene

Na teoria da computabilidade, o predicado T, que foi primeiramente estudado pelo matemático Stephen Kleene, é uma conjunto de triplas particular de números naturais que é usado para representar funções computáveis dentro das teorias formais da aritmética. Informalmente, o predicado T diz se um Programa de computador em particular vai parar quando rodado com uma entrada em particular, e a função U é usada para obter os resultados da computação se o programa para. E com o Teorema s_mn, a notação original usada por Kleene se tornou padrão na terminologia do conceito.

Definição

A definição depende Número de Gödel que se encaixe, ou seja, que atribua números naturais para funções computáveis. Essa numeração deve ser suficientemente efetive para que, dado um índice de uma função computável e uma entrada para essa função, seja possível simular efetivamente a computação da entrada.O Predicado T é obtido formalizando esta simulação.

A relação ternária T₁(e,i,x) recebe três números naturais como argumentos. As triplas de números (e,i,x) que pertencem a relação (os que tornam T₁(e,i,x) verdadeira) são definidas exatamente para serem triplas nas quais x representa um histórico de computação de uma função computável de índice e quando roda com uma entrada i, e o programa para no último passo desse histórico de computação. Ou seja, T₁ primeiramente indaga se x é um Número de Gödel de uma sequência finita ⟨x_j⟩ das configurações completas de uma Máquina de Turing de índice e, computando uma entrada i. Se isso for verdadeiro, T₁ pergunta se a sequência começa com o estado inicial da computação e se cada elemento seguinte corresponde a um único passo de uma máquina de Turing. Se sim, T₁ por fim pergunta se a sequência ⟨x_j⟩ termina com a máquina num estado de parada. Se a resposta para as três perguntas foi afirmativa, então T₁(e,i,x) é verdadeira. Caso contrário, T₁(e,i,x) é falsa.

Existe uma função correspondente U tal que, se T(e,i,x) é verdadeira, então U(x) retorna a saída da função com índice e e entrada i.

O formalismo de Kleene anexa um número de entradas a cada função, o que ocasiona que o predicado T₁ só pode ser usado para funções que só recebem uma entrada. Existem outros predicados para funções que recebem entradas múltiplas. A relação:

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

é verdadeira se x contem a computação de parada de uma função e com entrada i₁,...,i_k.

Teorema da forma normal

O Predicado T pode ser usado para obter o Teorema da Forma Normal de Kleene para funções computáveis (Soare 1987, p. 15). Desses estados existem uma função recursiva primitiva U tal que a função f que recebe um inteiro como argumento é computável se e apenas se existe um numero e tal que para todo n existe

$f(n)\simeq U(\mu x\,T(e,n,x))$,

que μ é um operador μ $\simeq$ é verdade se ambos os lados são indefinidos ou se os dois lados são definidos e iguais. Nesse caso U é uma operação universal (ou seja, independe da função computável f) o qual tem como propósito extrair, de um número x (contendo um histórico de computação completo) que é retornado pelo operador μ, apenas o valor de f(n) que foi encontrado no final da computação.

Formalização

O predicado T é uma primitiva recursiva no sentido de que existe uma função primitiva recursiva que, dadas entradas para o predicado, determina corretamente o valor verdade do predicado para tais entradas. Similarmente, a função U é primitiva recursiva.

Por causa disso qualquer teoria da aritmética que consegue representar qualquer função recursiva primitiva também consegue representar T e U. Por exemplo as teorias aritméticas de Robinson e teorias mais fortes com a aritmética de Peano.

Hierarquia aritmética

Em adição a codificação de computabilidade, o predicado T pode ser usado para gerar conjuntos completos dentro de hierarquia aritmética. Em particular, o conjunto

K = { e : ∃ x T(e,0,x)},

que tem o mesmo grau de Turing que o problema da parada, é a uma $\Sigma _{1}^{0}$ relação unaria completa (Soare 1987, pp. 28, 41). Mais geralmente, o conjunto

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

é um $\Sigma _{1}^{0}$ predicado completo (n+1)-ário. Assim, quando a representação do predicado T é obtido em uma teoria da aritmética, a representação de um predicado $\Sigma _{1}^{0}$-completo pode ser obtido dele.

Essa construção pode ser estendida na hierarquia aritmética, como no Teorema de Post (Hinman 2005, p. 397). Por exemplo, se um conjunto $A\subseteq \mathbb {N} ^{k+1}$ é $\Sigma _{n}^{0}$ completo, então o conjunto :$\{\langle a_{1},\ldots ,a_{k}\rangle :\forall x(\langle a_{1},\ldots ,a_{k},x)\in A)\}$ é $\Pi _{n+1}^{0}$ completo.

Bibliografia

• Peter Hinman, 2005, Fundamentals of Mathematical Logic, A K Peters. ISBN 978-1-56881-262-5
• Stephen Cole Kleene, 1943, "Recursive predicates and quantifiers", Transactions of the AMS v. 53 n. 1, pp. 41–73. Reprinted in The Undecidable, Martin Davis, ed., 1965, pp. 255–287.
• —, 1952, Introduction to Metamathematics, North-Holland. Reprinted by Ishi press, 2009, ISBN 0-923891-57-9.
• —, 1967. Mathematical Logic, John Wiley. Reprinted by Dover, 2001, ISBN 0-486-42533-9.
• Robert I. Soare, 1987, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer. ISBN 0-387-15299-7