Dragón oscuro puro es muy fuerte

El Teorema de Universalidad

EL TEOREMA DE UNIVERSALIDAD
1. Introducción
Uno de los pilares sobre los que descansa la Teoría de la Computabilidad y que ha de
estar presente en todo sistema de computación aceptable es sin duda el Teorema de
Universalidad. Este resultado, considerado bajo el modelo de los Programas While,
garantiza la existencia de un programa Universal, capaz de simular elcomportamiento
de cualquier otro programa ante una entrada dada. Como se puede observar, dicho
programa Universal debe admitir como parte de su entrada a otro programa while. Así
pues, teniendo en cuenta el hecho de que las entradas de un programa while han de ser
vectores de números naturales, nos veremos en la necesidad de construir un proceso de
codificación de los programas while. Esteproceso traerá como consecuencia la
enumeración efectiva de los programas y por consiguiente de las funciones
computables.
Una vez puestas de manifiesto las enumeraciones efectivas tanto de programas
como de funciones computables, se procederá al enunciado y justificación mediante la
Tesis de Church, del Teorema de Universalidad. Aunque esta demostración puede
resultar convincente, queremosresaltar que no lo debe ser tanto, debido a cierta
dificultad que ha de ser salvada mediante un resultado teórico. La dificultad estriba en
cómo un programa fijo, y por tanto con un número concreto de variables, puede simular
el comportamiento de otro programa que eventualmente puede tener más variables. La
idea clave reside, como se verá, en tratar de almacenar la información de un conjunto devariables, en una única variable. Se procede por tanto a la construcción de biyecciones
entre el conjunto de los naturales y cualquier potencia del mismo, así como las
correspondientes proyecciones.

2. Enumeración de los Programas While
Teniendo en cuenta que el alfabeto asociado a los programas while es finito y que se
pueden construir una infinidad de estos programas (por ejemplo losprogramas que
computan las funciones constantes), podemos deducir que el conjunto de todos los
programas while es numerable. De hecho dicho conjunto podría ser ordenado, por
ejemplo alfabéticamente. Sin embargo esta ordenación no es útil para nuestros
propósitos, pues aunque dados dos programas podríamos decidir cuál de ellos va antes
en el orden, no sería posible saber qué lugar ocupa unprograma determinado, ni
construir el programa que ocupa un lugar concreto.
Considerando el conjunto de caracteres del lenguaje de los programas while y el
hecho de que hemos convenido que los nombres de las variables son de la forma Xn con
n perteneciente a los naturales, se puede representar dicho conjunto mediante códigos
binarios de seis dígitos de acuerdo a la siguiente tabla:

1

ElTeorema de Universalidad

Símbolo
begin
end
while
do
:=
;
succ
pred
≠
(
)
X
0
1
2
3
4
5
6
7
8
9

Código binario
100000
100001
100010
100011
100100
100101
100110
100111
101000
101001
101010
101011
101100
101101
101110
101111
110000
110001
110010
110011
110100
110101

Código decimal
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
4950
51
52
53

Teniendo en cuenta la tabla anterior, podemos definir una función codificadora,
que denominaremos Cod, que va del conjunto de los programas while (WP) al conjunto
de los naturales: Cod : WP → N; de manera que dado un programa P, Cod (P) será el
número natural representado por la expansión binaria obtenida mediante la
concatenación de los bloques de seis bits asociados a loscaracteres de P en el orden de
la secuencia. Así el programa P ≡ begin X1 : = 0 end, tendrá como imagen por la
función Cod al número cuya espansión binaria es:
100000 101011 101101 100100 101100 100001
Es claro que el tamaño de los números que surgen de este proceso de
codificación resulta enormemente grande, pero afortunadamente esto no afectará a
nuestros intereses; ya que lo que...