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 tales 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 se definen originalmente sobre 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.
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) a menudo se escribe ν i en lugar del habitual .
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 las 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 denomina numeración de Friedberg .