Mostrar código-fonte de Numeração (teoria da computação)

Na [[teoria da computabilidade]], '''numeração'''<ref>V.A. Uspenskiĭ, A.L. Semenov ''Algorithms: Main Ideas and Applications'' (1993 Springer) pp.&nbsp;98ff.</ref> é 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 [[Número_de_Gödel|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 <math>S \!</math> é uma [[função sobrejectiva]] [[função parcial|parcial]]
:<math>\nu: \subseteq \mathbb{N} \to S.</math>

O valor de <math>\nu \!</math> em <math>i \!</math> (se definida) é normalmente escrita como <math>\nu_i \!</math> ao invés do usual <math>\nu(i) \!</math>. <math>\nu \!</math> é chamada de '''numeração total''' se <math>\nu \!</math> é uma [[função total]].

Se <math>S \!</math> é um conjunto de números naturais, então <math>\nu \!</math> é necessário para ser uma [[função parcial]] recursiva. Se <math>S \!</math> é um conjunto de subconjuntos dos números naturais, então o conjunto <math>\{\langle i,j \rangle : j \in \nu_i \}</math> (usando a função de emparelhamento de Cantor) é necessário para ser [[Conjuntos_recursivamente_enumeráveis|recursivamente enumerável.]]

== Exemplos ==
* Dado uma numeração de Gödel <math>\varphi_i</math> podemos definir uma numeração dos [[conjuntos recursivamente enumeráveis]] por <math>W(i):=\mathrm{domain}(\varphi_i)</math>

== 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
:<math>\nu_1: \subseteq \mathbb{N} \to S_1</math>
e
:<math>\nu_2: \subseteq \mathbb{N} \to S_2</math>
Dizemos que <math>\nu_1</math> é '''redutível''' a <math>\nu_2</math> e escrita
:<math>\nu_1 \le \nu_2</math>
se 
:<math>\exists f \in \mathbf{P}^{(1)} \, \forall i \in \mathrm{Domain}(\nu_1) : \nu_1(i) = \nu_2 \circ f(i).</math>

Se <math>\nu_1 \le \nu_2</math> e <math>\nu_1 \ge \nu_2</math> então dizemos que <math>\nu_1</math> é '''equivalente''' a <math>\nu_2</math> e escrita <math>\nu_1 \equiv \nu_2</math>.

{{referências}}


[[Categoria:Teoria da computação]]