Siguiente: Teoría de la recursividad Un nivel arriba: Universalidad Anterior: Máquina Universal de Turing

Universalidad en programas-while

Así como en el funcionamiento de las máquinas de Turing puede ser formalizado en las máquinas de Turing para dar así lugar a la máquina universal de Turing, tenemos que la sintaxis y la semántica de los programas-while pueden, también, ser formalizados en el lenguaje de los programas-while . Al inicio de este capítulo presentamos una codificación de los programas-while . Esa codificación es programable, y dada una variable P siempre se puede decidir si su contenido es el código de un programa. El proceso de decisión conlleva un proceso de análisis sintáctico, que puede llevarse hasta el de una interpretación semántica del programa en cuestión.

Proposición 4.5 (Programa-tex2html_deferredwhile universal)   Existe un programa-while $\mbox{\it PU}$ tal que para cualquier $P\in\mbox{\rm\rm Programas-{\bf while }}$ y cualquier lista de datos $\mbox{\bf x}$ se tiene $\mbox{\it PU}(\lceil P\rceil,\lceil \mbox{\bf x}\rceil)=P(\mbox{\bf x})$.

También, como las proposiciones 3.4.3 y 3.4.4 en el caso de las máquinas de Turing, resulta válida la

Proposición 4.6   Existen sendos programas-while P₁ y P₂ que calculan las funciones

$$(\lceil p_1\rceil,\ldots,\lceil p_m\rceil,\mbox{\bf x})\mapst... ...rceil,\mbox{\bf x})\mapsto \bigwedge_{i=1}^m p_i(\mbox{\bf x}).$$