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 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

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 $\{⟨i,j⟩: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 ${\phi }_i$ podemos definir uma numeração dos conjuntos recursivamente enumeráveis por $W(i):=\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}({\phi }_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\le {\nu }_2$

se

$\mathrm{\exists }f\in {𝐏}^{(1)}\mathrm{\forall }i\in \mathrm{D}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}({\nu }_1):{\nu }_1(i)={\nu }_2\circ f(i).$

Se ${\nu }_1\le {\nu }_2$ e ${\nu }_1\ge {\nu }_2$ então dizemos que ${\nu }_1$ é equivalente a ${\nu }_2$ e escrita ${\nu }_1\equiv {\nu }_2$.