Siguiente: Codificación de programas-while Un nivel arriba: Conceptos básicos Anterior: Computabilidad de los esquemas

Numerabilidad de las funciones computables

Veremos en esta sección que la clase de los programs-while es numerable. Un numeral es la representación formal de un número natural en una teoría dada. Así, por ejemplo, la cadena de (n+1) 1's, 1ⁿ⁺¹, es el numeral del número n en la teoría 1^*. La representación en base 10 de un número natural n puede ser vista como el numeral de n en el lenguaje (0+1+2+3+4+5+6+7+8+9)^*. Se sabe bien que en este último lenguaje, el numeral de un número es único salvo 0's a la izquierda, ``pues ésos no cuentan''.

Observación 9.1   Los número naturales son expresables mediante numerales constructibles como programas-while .

En la tabla 1.5 presentamos una descripción inductiva de esos numerales.

  

Table 1.5: Numerales como programas- while .

Esta propiedad de los programas-while hace que los programas-while se puedan codificar mediante ellos mismos, simplemente componiendo las correspondencias siguientes:

$$\begin{array}{ccccc} \mbox{\fbox{Clase de programas-{\bf whi... ...hile }} } \\ P &\mapsto& n=\Phi(P) &\mapsto& p_n \end{array}$$

donde $\Phi$ es la función de enumeración de los programas-while , de cuya existencia nos ocuparemos inmediatamente, y $\Psi$ es la correspondencia entre números y numerales descrita en la tabla 1.5.

Siguiente: Codificación de programas-while Un nivel arriba: Conceptos básicos Anterior: Computabilidad de los esquemas