Numeración (teoría de la computabilidad)

En la teoría de la computabilidad, una numeración es la asignación de números naturales a un conjunto de objetos, como funciones , números racionales , gráficas o palabras en algún lenguaje formal . Una numeración puede utilizarse para transferir la idea de computabilidad y conceptos relacionados, que originalmente se definen en los números naturales mediante funciones computables , a estos diferentes tipos de objetos.

Algunos ejemplos comunes de numeración incluyen la numeración de Gödel en lógica de primer orden , los números de descripción que surgen de las máquinas de Turing universales y las numeraciones admisibles del conjunto de funciones computables parciales.

Una numeración de un conjunto${\displaystyle S}$es una función parcial sobreyectiva de${\displaystyle \mathbb {N} }$a S ( Ershov 1999:477). El valor de una numeración${\displaystyle \nu }$En un número i (si está definido) a menudo se escribe${\displaystyle \nu _{i}}$en lugar de lo habitual${\displaystyle \nu (i)}$.

Algunos ejemplos de numeración son:

• El conjunto de todos los subconjuntos finitos de${\displaystyle \mathbb {N} }$tiene una numeración${\displaystyle \gamma }$, definido de modo que${\displaystyle \gamma (0)=\emptyset }$y de modo que, para cada conjunto finito no vacío${\displaystyle A=\{a_{0},\ldots ,a_{k}\}}$,${\displaystyle \gamma (n_{A})=A}$dónde${\displaystyle n_{A}=\sum _{i\leq k}2^{a_{i}}}$(Ershov 1999:477). Esta numeración es una inyección.
• Una numeración Gödel fija${\displaystyle \varphi _{i}}$de las funciones parciales computables se puede utilizar para definir una numeración W de los conjuntos computablemente enumerables , haciendo que W ( i ) sea el dominio de${\displaystyle \varphi _{i}}$. Esta numeración será sobreyectiva (como todas las numeraciones) pero no inyectiva: habrá números distintos que se corresponden con el mismo conjunto computablemente enumerable bajo W .

Una numeración es total si es una función total. Si el dominio de una numeración parcial es computacionalmente enumerable, entonces siempre existe una numeración total equivalente (la equivalencia de numeraciones se define más adelante).

Una numeración η es decidible si el conjunto${\displaystyle \{(x,y):\eta (x)=\eta (y)\}}$es un conjunto decidible.

Una numeración η es unívoca si η ( x ) = η ( y ) si y solo si x = y ; en otras palabras, si η es una función inyectiva. Una numeración unívoca del conjunto de funciones computables parciales se denomina numeración de Friedberg .

Hay un pedido anticipado del conjunto de todas las numeraciones. Deje${\displaystyle \nu _{1}:\mathbb {N} \rightharpoonup S}$y${\displaystyle \nu _{2}:\mathbb {N} \rightharpoonup S}$sean dos numeraciones. Entonces${\displaystyle \nu _{1}}$es reducible a${\displaystyle \nu _{2}}$, escrito${\displaystyle \nu _{1}\leq \nu _{2}}$, si

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

Dónde${\displaystyle \mathbf {P} ^{(1)}}$es el conjunto de todas las funciones computables parciales${\displaystyle \mathbb {N} \to \mathbb {N} }$.

Si${\displaystyle \nu _{1}\leq \nu _{2}}$y${\displaystyle \nu _{1}\geq \nu _{2}}$entonces ${\displaystyle \nu _{1}}$es equivalente a${\displaystyle \nu _{2}}$; esto está escrito${\displaystyle \nu _{1}\equiv \nu _{2}}$.

Cuando los objetos del conjunto S que se están numerando son suficientemente "constructivos", es común buscar numeraciones que puedan decodificarse eficazmente (Ershov 1999:486). Por ejemplo, si S consta de conjuntos computablemente enumerables, la numeración η es computable si el conjunto de pares ( x , y ) donde y ∈ η ( x ) es computablemente enumerable. De manera similar, una numeración g de funciones parciales es computable si la relación R ( x , y , z ) = "[ g ( x )]( y ) = z " es computablemente enumerable (Ershov 1999:487).

Una numeración computable se llama principal si toda numeración computable del mismo conjunto es reducible a ella. Tanto el conjunto de todos los subconjuntos computablemente enumerables de${\displaystyle \mathbb {N} }$y el conjunto de todas las funciones parcialmente computables tiene numeraciones principales (Ershov 1999:487). Una numeración principal del conjunto de funciones parcialmente computables se conoce como numeración admisible en la literatura.

• Numeración completa
• Cilindrificación
• Numeración de Gödel
• Número de descripción

• YL Ershov (1999), "Teoría de las numeraciones", Manual de teoría de la computabilidad , Elsevier, págs.  473 – 506.
• VA Uspenskiĭ , AL Semenov (1993), Algoritmos: Ideas principales y aplicaciones , Springer.