Numeración admisible

En teoría de la computabilidad , las numeraciones admisibles son enumeraciones ( numeraciones ) del conjunto de funciones computables parciales que pueden convertirse a 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 numeración.

Definición

La formalización de la teoría de la computabilidad por parte de Kleene condujo a una función computable parcial universal particular Ψ( e , x ) definida usando el predicado T . Esta función es universal en el sentido de que es parcialmente computable, 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 lados no están definidos o ambos están definidos y son iguales. Es común escribir ψ _e ( x ) para Ψ( e , x ); por lo tanto, la secuencia ψ ₀ , ψ ₁ , ... es una enumeración de todas las funciones computables parciales. Tales 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 parcialmente computable.
Existe una función computable total f tal que, para todo e , η _e = ψ _{f ( e )} .
Existe 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; la segunda requiere que cualquier índice para la numeración η pueda convertirse efectivamente en un índice para la numeración ψ; y la tercera requiere que cualquier índice para la numeración ψ pueda convertirse efectivamente en un índice para la numeración η.

Definición equivalente

La siguiente caracterización equivalente de admisibilidad tiene la ventaja de ser "interna a η", en el sentido de que no hace referencia directa a una numeración estándar (sólo indirectamente a través de la definición de universalidad de Turing). Una numeración η de funciones parciales es admisible en el sentido anterior si y sólo si :

La función de evaluación H ( e , x ) = η _e ( x ) es una función parcialmente computable.
η es universal de Turing: para todas las funciones computables parciales f existe una e tal que η _e = f (nótese que aquí no estamos asumiendo una función computable total que transforma los índices η en índices ψ)
η tiene "currificación computable" o satisface el Teorema de Parámetros o Teorema de Smn , es decir, existe una función computable total c tal que para todo e , x , y , η _{c ( e , x )} ( y )=η _e ( x , y )

La prueba es la siguiente:

El hecho de que las numeraciones admisibles en el sentido anterior tengan todas estas propiedades se desprende del hecho de que la numeración estándar las tiene y del Teorema de Equivalencia de Rogers.

En la otra dirección, supongamos que η tiene las propiedades en la caracterización equivalente.

Puesto que la función de evaluación H ( e , x )=η _e ( x ) es parcialmente computable, existe v tal que ψ _v = H . Por lo tanto, por el Teorema de Parámetros para la numeración estándar, existe una función total computable d tal que ψ _{d ( v , e )} ( x )= H ( e , x ) para todo x . La función total f ( e ) = d ( v , e ) satisface entonces la segunda parte de la definición anterior.

A continuación, dado que la función de evaluación E ( e , x )= ψ _e ( x ) para la numeración estándar es parcialmente computable, por el supuesto de universalidad de Turing existe u tal que η _u ( e , x )= ψ _e ( x ) para todo e , x .

Sea c ( x , e ) la función de currificación computable para η. Entonces η _{c ( u , e )} = ψ _e para todo e , por lo que g ( e ) = c ( u , e ) satisface la tercera parte de la primera definición anterior.

Teorema de equivalencia de Rogers

Hartley Rogers, Jr. demostró que una numeración η de las funciones computables parciales es admisible si y sólo si existe una biyección computable total p tal que, para todo e , η _e = ψ _{p ( e )} (Soare 1987:25).

Véase también

Numeración de Friedberg

Referencias

YL Ershov (1999), "Teoría de numeraciones", Handbook of Computability Theory , 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 algoritmos , Holanda Septentrional, 1978. ISBN 0-444-00226-X
H. Rogers, Jr. (1967), La teoría de funciones recursivas y computabilidad efectiva , segunda edición, 1987, MIT Press. ISBN 0-262-68052-1 (libro de bolsillo), ISBN 0-07-053522-1
R. Soare (1987), Conjuntos y grados enumerables recursivamente , Perspectivas en lógica matemática, Springer-Verlag. ISBN 3-540-15299-7