Numeración completa

En la teoría de la computabilidad, las numeraciones completas son generalizaciones de la numeración de Gödel, introducida por primera vez por A.I. Mal'tsev en 1963. Se estudian porque varios resultados importantes, como el teorema de recursión de Kleene y el teorema de Rice , que se demostraron originalmente para el conjunto de funciones computables numeradas por Gödel , siguen siendo válidos para conjuntos arbitrarios con numeraciones completas.

Una numeración${\displaystyle \nu }$de un conjunto${\displaystyle A}$se denomina completo (con respecto a un elemento)${\displaystyle a\in A}$) si para cada función computable parcial${\displaystyle f}$existe una función computable total${\displaystyle h}$para que (Ershov  1999:482):

${\displaystyle \nu \circ h(i)={\begin{cases}\nu \circ f(i)&{\mbox{si}}~i\in \operatorname {dom} (f),\\a&{\mbox{en otro caso}}.\end{cases}}}$

Ershov se refiere al elemento a como un elemento "especial" para la numeración. Una numeración${\displaystyle \nu }$Se denomina precompleto si se cumple la propiedad más débil:

${\displaystyle \nu \circ f(i)=\nu \circ h(i)\qquad i\in \operatorname {dom} (f).}$

• Cualquier numeración de un conjunto de un solo elemento es completa.
• La función identidad en los números naturales no está completa.
• La numeración de Gödel está precompleta.

• 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
• AI Mal'tsev, Conjuntos con numeración completa . Algebra i Logika , 1963, vol. 2, n.º 2, 4-29 (en ruso).