Numeración admisible

En 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 parte de Kleene condujo a una función computable parcial universal particular Ψ( e , x ) definida utilizando el predicado T. Esta función es universal en el sentido de que es parcialmente computable, y para cualquier función parcial computable f existe 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 ψ ₀ , ψ ₁ , ... es una enumeración de todas las funciones computables parciales. Estas enumeraciones se denominan formalmente numeraciones computables de 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 computable parcial.
Existe una función total computable 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í, el primer punto requiere que la numeración sea computable; el segundo requiere que cualquier índice de la numeración η pueda convertirse efectivamente en un índice de la numeración ψ; y el tercero 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 computable parcial.
η es universal de Turing: para todas las funciones computables parciales f hay una e tal que η _e = f (tenga en cuenta que aquí no estamos asumiendo una función computable total que transforma η-índices en ψ-índices)
η tiene "currying computable" o satisface el Teorema del Parámetro 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 como sigue:

El hecho de que las numeraciones admisibles en el sentido anterior tengan todas estas propiedades se deriva 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 de la caracterización equivalente.

Dado que la función de evaluación H(e,x)= η _e (x) es parcialmente computable, existe v tal que ψ _v =H . Por lo tanto, según 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, según 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 curry computable para η. Entonces η _c(u,e) =ψ _e para todo e , entonces 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 hay una biyección total computable p tal que, para todo e , η _e = ψ _{p ( e )} (Soare 1987:25).

Ver también

Numeración de Friedberg

Referencias

YL Ershov (1999), "Teoría de las numeraciones", Manual de teoría de la computabilidad , ER Griffor (ed.), Elsevier, págs. 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), La teoría de las funciones recursivas y la 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 recursivamente enumerables , Perspectivas en lógica matemática, Springer-Verlag. ISBN 3-540-15299-7