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

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.

Definição

editar

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.

Exemplos

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

Propriedades

editar

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

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.