Predicado T de Kleene

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde julho de 2012)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde julho de 2012).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.

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 computaveis 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 smn, a notação original usada por Kleene se tornou padrão na terminologia do conceito. [1]

Definição[editar | editar código-fonte]

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 T1(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 T1(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, T1 primeiramente indaga se x é um Número de Gödel de uma sequência finita 〈xj〉 das configurações completas de uma Máquina de Turing de índice e, computando uma entrada i. Se isso for verdadeiro, T1 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, T1 por fim pergunta se a sequência 〈xj〉 termina com a máquina num estado de parada. Se a resposta para as três perguntas foi afirmativa, então T1(e,i,x) é verdadeira. Caso contrário, T1(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 T1 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 i1,...,ik.

Teorema da Forma Normal[editar | editar código-fonte]

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 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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^0_1 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 x T(e, a_1, \ldots, a_n, x)\}

é um \Sigma^0_1 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^0_1-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^0_{n} completo, então o conjunto :\{ \langle a_1, \ldots, a_k\rangle : \forall x ( \langle a_1, \ldots, a_k, x) \in A)\} é \Pi^0_{n+1} completo.

Referências

  1. O predicado descrito aqui foi representado em (Kleene 1943) e (Kleene 1952), e isso é o que é chamado de "Predicato T de Kleene". (Kleene 1967) usa a letra T para descrever um predicado diferente relacionado com funções computáveis, mas que não podem ser usadas na obtenção do teorema da Forma Normal de Kleene

Bibliografia[editar | editar código-fonte]

  • 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