Numeración (teoría de la computabilidad)

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

En teoría de 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 . Una numeración se puede utilizar para transferir la idea de computabilidad ^[1] y conceptos relacionados, que se definieron originalmente en los números naturales utilizando 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

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

Algunos 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 , haciendo 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 mapeen 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 recursivamente 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 es un conjunto decidible. ${\displaystyle \{(x,y):\eta (x)=\eta (y)\}}$

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

Comparación de numeraciones

Hay un preorden en el conjunto de todas las numeraciones. Sean y 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 se escribe . ${\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 numeran son suficientemente "constructivos", es común buscar numeraciones que puedan decodificarse de manera efectiva (Ershov 1999:486). Por ejemplo, si S consiste en 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 parcialmente recursiva (Ershov 1999:487).

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

Véase también

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

Referencias

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

• YL Ershov (1999), "Teoría de numeraciones", Handbook of Computability Theory , Elsevier, págs. 473–506.
• VA Uspenskiĭ , AL Semenov (1993), Algoritmos: ideas principales y aplicaciones , Springer.