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

Na teoria da computabilidade, numeração é 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 idéia 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

Uma numeração de um conjunto $S\!$ é uma função sobrejectiva parcial

$\nu :\subseteq \mathbb {N} \to S.$

O valor de $\nu \!$ em $i\!$ (se definida) é normalmente escrita como $\nu _{i}\!$ ao invés do usual $\nu (i)\!$. $\nu \!$ é chamada de numeração total se $\nu \!$ é uma função total.

Se $S\!$ é um conjunto de números naturais, então $\nu \!$ é necessário para ser uma função parcial recursiva. Se $S\!$ é um conjunto de subconjuntos dos números naturais, então o conjunto $\{\langle i,j\rangle :j\in \nu _{i}\}$ (usando a função de emparelhamento de Cantor) é necessário para ser recursivamente enumerável.

Exemplos

• Dado uma numeração de Gödel $\varphi _{i}$ podemos definir uma numeração dos conjuntos recursivamente enumeráveis por $W(i):=\mathrm {domain} (\varphi _{i})$

Propriedades

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

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

$\nu _{1}:\subseteq \mathbb {N} \to S_{1}$

e

$\nu _{2}:\subseteq \mathbb {N} \to S_{2}$

Dizemos que $\nu _{1}$ é redutível a $\nu _{2}$ e escrita

$\nu _{1}\leq \nu _{2}$

se

$\exists f\in \mathbf {P} ^{(1)}\,\forall i\in \mathrm {Domain} (\nu _{1}):\nu _{1}(i)=\nu _{2}\circ f(i).$

Se $\nu _{1}\leq \nu _{2}$ e $\nu _{1}\geq \nu _{2}$ então dizemos que $\nu _{1}$ é equivalente a $\nu _{2}$ e escrita $\nu _{1}\equiv \nu _{2}$.