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 \le \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 \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$.