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 usar una numeración para transferir la idea de computabilidad [1] y conceptos relacionados, que originalmente se definen en los números naturales usando funciones computables , a estos diferentes tipos de objetos.
Los ejemplos comunes de numeraciones incluyen numeraciones de Gödel en lógica de primer orden y numeraciones admisibles del conjunto de funciones computables parciales.
Definición y ejemplos
Una numeración de un conjuntoes una función parcial sobreyectiva dea 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 del habitual.
Ejemplos de numeraciones incluyen:
- El conjunto de todos los subconjuntos finitos de tiene una numeración , definido para que y de modo que, para cada conjunto finito no vacío , dónde (Ershov 1999: 477). Esta numeración es una biyección (parcial).
- Una numeración de Gödel fija de las funciones parciales computables se puede utilizar para definir una numeración W de los conjuntos enumerables recursivamente , 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 asignan al mismo conjunto recursivamente numerable bajo W .
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 , 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.
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. Dejar y ser dos numeraciones. Luegoes reducible a, escrito , Si
Si y luego es equivalente a; esto esta escrito.
Numeraciones computables
Cuando los objetos del conjunto S que se numeran son lo suficientemente "constructivos", es común observar numeraciones que se pueden decodificar de manera efectiva (Ershov 1999: 486). Por ejemplo, si S consta de conjuntos recursivamente enumerables, la numeración η es calculable si el conjunto de pares ( x , y ) donde y ∈ η ( x ) es recursivamente enumerable. De manera similar, una numeración g de funciones parciales es calculable 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 se puede reducir a ella. Tanto el conjunto de todos los subconjuntos recursivamente enumerables dey el conjunto de todas las funciones computables parciales tiene numeraciones principales (Ershov 1999: 487). Una numeración principal del conjunto de funciones recursivas parciales se conoce como numeración admisible en la literatura.
Ver también
Referencias
- ^ "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", Manual de teoría de la computabilidad , Elsevier, págs. 473–506.
- VA Uspenskiĭ , AL Semenov (1993), Algoritmos: Ideas y aplicaciones principales , Springer.