Numeración admisible

En la teoría de la computabilidad , las numeraciones admisibles son enumeraciones del conjunto de funciones parcialmente computables que pueden convertirse a y desde la numeración estándar de funciones parcialmente computables. Estas numeraciones también se denominan numeraciones aceptables y sistemas de programación aceptables .

El teorema de equivalencia de Rogers demuestra que todos los sistemas de programación aceptables son equivalentes entre sí en el sentido formal de la teoría de números.

La formalización de la teoría de la computabilidad por Kleene condujo a una función computable parcial universal particular Ψ( e , x ) definida mediante el predicado T . Esta función es universal en el sentido de que es computable parcial , y para cualquier función computable parcial f existe un e tal que, para todo x , f ( x ) = Ψ( e , x ), donde la igualdad significa que ambos lados son indefinidos 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. Dichas enumeraciones se denominan formalmente numeraciones computables de las funciones computables parciales.

Se define que una numeración arbitraria η de funciones parciales es 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í, el primer punto requiere que la numeración sea computable; el segundo requiere que cualquier índice para la numeración η se pueda convertir efectivamente en un índice para la numeración ψ; y el tercero requiere que cualquier índice para la numeración ψ se pueda convertir efectivamente en un índice para la numeración η .

La siguiente caracterización equivalente de admisibilidad tiene la ventaja de ser "interna a η ", ya que no hace referencia directa a una numeración estándar (solo 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 solo 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 un e tal que η _e = f (nótese que aquí no estamos asumiendo una función computable total que transforme los índices η en índices ψ).
• η tiene " currying computable " o satisface el teorema del parámetro o el teorema 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 demostración es la siguiente:

El hecho de que las numeraciones admisibles en el sentido anterior tengan todas estas propiedades se deduce 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 del parámetro 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 la suposición 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.

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

• Numeración de Friedberg

• YL Ershov (1999), "Teoría de la numeración", Manual de teoría de la computabilidad , ER Griffor (ed.), Elsevier, pp.  473-506 . ISBN 978-0-444-89882-1
• M. Machtey y P. Young (1978), Introducción a la teoría general de algoritmos , North-Holland, 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