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

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na teoria da computabilidade, numeração1 é 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[editar | editar código-fonte]

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[editar | editar código-fonte]

Propriedades[editar | editar código-fonte]

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

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

Referências

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