Siguiente: Funciones de apareamiento Un nivel arriba: COMPUTABILIDAD Y COMPLEJIDAD Anterior: Segunda lista de ejercicios

Funciones de apareamiento y universalidad

Hemos visto ya que, utilizando la enumeración de Cantor, puede probarse que la colección de programas-while es numerable. En este capítulo realzaremos la propiedad de numerabilidad, haciendo abstracción de la enumeración particular que se tome en el conjunto de secuencias de números naturales. Presentaremos también, como un ejemplo particular de codificación de secuencias por números a la función $\beta$ de Gödel. Finalmente, adentrándonos en la propiedad de numerabilidad efectiva de los programas-while , veremos que existen programas-while universales, es decir, tales que dado el código de otro programa-while y el código de una secuencia de datos, entonces el programa universal aplica ese otro programa en el conjunto dado de datos.