Numeración admisible
En la teoría de la computabilidad , las numeraciones admisibles son enumeraciones ( numeraciones ) del conjunto de funciones computables parciales que se pueden convertir hacia y desde la numeración estándar. Estas numeraciones también se denominan numeraciones aceptables y sistemas de programación aceptables .
El teorema de equivalencia de Rogers muestra que todos los sistemas de programación aceptables son equivalentes entre sí en el sentido formal de la teoría de la numeración.
Definición
La formalización de la teoría de la computabilidad por Kleene condujo a una Ψ particular, universales parcial computable función ( e , x ) definida mediante el predicado T . Esta función es universal en el sentido de que es computable parcialmente, y para cualquier función computable parcial f hay una e tal que, para todo x , f ( x ) = Ψ ( e , x ), donde la igualdad significa que ambos los lados no están definidos o ambos están definidos y son iguales. Es común escribir ψ e ( x ) para Ψ ( e , x); por tanto, la secuencia ψ 0 , ψ 1 , ... es una enumeración de todas las funciones computables parciales. Estas enumeraciones se denominan formalmente numeraciones computables de las funciones computables parciales.
Una numeración arbitraria η de funciones parciales se define como una numeración admisible si:
- La función H ( e , x ) = η e ( x ) es una función calculable parcial.
- Existe una función calculable total f tal que, para todo e , η e = ψ f ( e ) .
- Hay una función computable total g tal que, para todo e , ψ e = η g ( e ) .
Aquí, la primera viñeta requiere que la numeración sea computable; el segundo requiere que cualquier índice para la numeración η se pueda convertir eficazmente en un índice para la numeración ψ; y el tercero requiere que cualquier índice para la numeración ψ pueda convertirse efectivamente en un índice para la numeración η.
Teorema de equivalencia de Rogers
Hartley Rogers, Jr. mostró que una numeración η de las funciones computables parciales es admisible si y solo si hay una biyección computable total p tal que, para todo e , η e = ψ p ( e ) (Soare 1987: 25).
Ver también
Referencias
- YL Ershov (1999), "Teoría de la numeración", Manual de teoría de la computabilidad , ER Griffor (ed.), Elsevier, págs. 473–506. ISBN 978-0-444-89882-1
- M. Machtey y P. Young (1978), Introducción a la teoría general de los algoritmos , Holanda Septentrional, 1978. ISBN 0-444-00226-X
- H. Rogers, Jr. (1967), The Theory of Recursive Functions and Effective Computability , segunda edición 1987, MIT Press. ISBN 0-262-68052-1 ( tapa blanda), ISBN 0-07-053522-1
- R. Soare (1987), Conjuntos y grados recursivamente enumerables , Perspectivas en lógica matemática, Springer-Verlag. ISBN 3-540-15299-7
