Saltar para o conteúdo

Numeração (teoria da computação)

Origem: Wikipédia, a enciclopédia livre.

Na teoria da computabilidade, numeração[1] é a atribuição de números naturais para um conjunto de objetos como números racionais, gráficos ou palavras em alguma linguagem. A numeração pode ser usada para transferir a ideia de computabilidade e conceitos relacionados, que estão estritamente definidos sobre os números naturais usando funções computáveis, para objetos diferentes.

Numerações importantes são a numeração de Gödel dos termos de lógica de primeira ordem (LPO) e numerações do conjunto de funções computáveis​​, que pode ser usado para aplicar os resultados da teoria da computabilidade sobre o conjunto de funções computáveis ​​em si.

Uma numeração de um conjunto é uma função sobrejectiva parcial

O valor de em (se definida) é normalmente escrita como ao invés do usual . é chamada de numeração total se é uma função total.

Se é um conjunto de números naturais, então é necessário para ser uma função parcial recursiva. Se é um conjunto de subconjuntos dos números naturais, então o conjunto (usando a função de emparelhamento de Cantor) é necessário para ser recursivamente enumerável.

  • Dado uma numeração de Gödel podemos definir uma numeração dos conjuntos recursivamente enumeráveis por

Muitas vezes é mais conveniente trabalhar com uma numeração total do que com uma parcial. Se o domínio de uma numeração parcial é recursivamente enumerável, então sempre existe uma numeração equivalente total.

Comparação de numerações

[editar | editar código-fonte]

Usando a função computável, podemos definir uma ordem parcial no conjunto de todas as numerações. Dadas duas numerações

e

Dizemos que é redutível a e escrita

se

Se e então dizemos que é equivalente a e escrita .

Referências

  1. V.A. Uspenskiĭ, A.L. Semenov Algorithms: Main Ideas and Applications (1993 Springer) pp. 98ff.