Numeración (teoría de la computabilidad)

En teoría de la computabilidad, la asignación de números naturales a un conjunto de objetos.

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áficos o palabras en algún lenguaje formal . Se puede utilizar una numeración para transferir la idea de computabilidad ^[1] y conceptos relacionados, que originalmente se definen en los números naturales mediante funciones computables , a estos diferentes tipos de objetos.

Ejemplos comunes de numeraciones incluyen las numeraciones 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.

Definición y ejemplos

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

Ejemplos de numeraciones incluyen:

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

Tipos de numeraciones

Una numeración es total si es una función total. Si el dominio de una numeración parcial es enumerable de forma recursiva, entonces siempre existe una numeración total equivalente (la equivalencia de numeraciones se define a continuación).

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

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

Comparación de numeraciones

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

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

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

Numeraciones computables

Cuando los objetos del conjunto S que se están numerando son suficientemente "constructivos", es común buscar numeraciones que puedan decodificarse efectivamente (Ershov 1999:486). Por ejemplo, si S consta de conjuntos recursivamente enumerables, la numeración η es computable si el conjunto de pares ( x , y ) donde y ∈ η ( x ) es recursivamente 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 recursiva parcial (Ershov 1999:487).

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

Ver también

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

Referencias

1. "Teoría de la computabilidad: descripción general | Temas de ScienceDirect". www.sciencedirect.com . Consultado el 19 de enero de 2021 .

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