¿Puede un ordenador calcular cualquier cosa?
Al igual que Gödel en mátemáticas. Alan Turing estableció los límites de la computación, y hasta qué
punto un ordenador es capaz de calcular cualquier cosa.
El concepto de máquina de Turing
Una máquina de Turing es un concepto de ordenador idealizado, es decir un
ordenador de papel y lápiz, o según lo concibió el propio Turing un
ordenador con un lector y una cinta
infinita que puede moverse hacia adelante o atrás siguiendo unas reglas
sencillas escritas en la propia cinta. A
pesar de esta gran simplicidad, una máquina de Turing se puede adaptar para ejecutar
cualquier algoritmo o programa.
Una máquina de Turing que es capaz de
simular cualquier otra máquina de Turing es llamada una máquina
universal de Turing (UTM,
o simplemente una máquina universal). Las máquinas de Turing sirven para
estudiar hasta qué punto se puede automatizar
cualquier noción de lógica o de matemáticas.
Programas finalizables y no finalizables
Hoy en la práctica,
cualquier PC puede ser considerado una máquina de Turing o mejor dicho una
Máquina Universal de Turing pues en realidad lo que hace es simular cualquier
máquina de Turing y la coletilla de “Universal” expresa explícitamente que es
programable, pues en principio cada máquina de Turing puede ejecutar una sola tarea
o algoritmo. Mientras que la máquina Universal de Turing puede simular
cualquier máquina de Turing es decir cualquier algoritmo o tarea mediante la
programación adecuada.
De este modo por ejemplo, podemos
programar nuestra máquina de Turing para que calcule si cualquier número que se
le proporcione de entrada es primo. Para ello existe un algoritmo perfectamente
definido que obtiene como resultado una salida booleana (verdadero o falso) en función
de si el número introducido es primo o no.
Igual que la primidad
podemos programar nuestra máquina para cualquier otra tarea sencilla como
decirnos si el número introducido es par o, dados dos números que nos diga cual
es el mayor. Todos estos ejemplos tienen algo en común y es que aunque el
número introducido sea muy grande, el proceso finaliza. No obstante existe una
serie de programas perfectamente definidos algorítmicamente que alimentados con
ciertos números no finalizan nunca. Por ejemplo un algoritmo que calcule los
decimales del número pi o de cualquier otro número irracional, no acabará
nunca.
Pero existen otros
algoritmos aún más maliciosos, y digo maliciosos por que el algoritmo que
calcula los decimales de pi sabemos que no acaba nunca pero podemos “cortarlo”
cuando consideremos que tenemos los decimales suficientes, sin embargo hay
otros algoritmos en los que no podemos determinar de antemano si pararán o no, por
ejemplo la conjetura de Goldbach que
dice que cualquier número par mayor de dos se puede representar como la suma de
dos números primos, dado cualquier número de entrada es posible que el
algoritmo encuentre los dos números indicados y pare la ejecución, pero no
tenemos la certeza dado un número muy grande, de si parará alguna vez o no.
¿Se puede programar cualquier algoritmo?
Dicho lo anterior
cabe preguntarse si existe un algoritmo para
determinar si una máquina de Turing o programa determinado se detendrá alguna
vez o no. Vamos a suponer que tal algoritmo existe.
Suponiendo
que dicho algoritmo existe, podemos imaginar una lista de todos los programas o
máquinas de Turing y como estos son infinitos podemos asociar un número natural
n a cada máquina de Turing. Pondremos en la lista la salida proporcionada por
el programa de tal modo que podemos formar una matriz del siguiente modo. (La f significa que el programa no finaliza y por tanto no tiene una
salida válida)
m-> 0 1 2 3 4 5 6
…. m
Prog(0) f f f f f f f f
Prog(1) 0 0 0 0 0 0 0
0
Prog(2) 0 1 2 3 4 5 6
m
Prog(3) 2 4 6 8
10 12 14 (2+ 2Xm)
…
Prog(n)
Dada tal matriz suponemos que existe
un algoritmo H capaz de determinar si un programa Prog(n) terminará o no, de
tal forma que aplicando dicho algoritmo sobre el programa tendremos un 0 de
salida si el programa no finaliza y la salida del programa dado si este si
finaliza de tal modo que:
Prog(n) x H(n,m) = 0 si no finaliza
Prog(n) x H(n,m) = Salida si
finaliza.
La nueva matriz quedaría del
siguiente modo.
m-> 0
1 2 3 4 5 6
…. m
Prog(0) x H(0,m)
0
0 0 0
0 0 0 0
Prog(1) x H(1,m) 0 0 0
0 0 0 0 0
Prog(2) x H(2,m) 0 1
2 3 4 5 6 m
Prog(3) x H(3,m) 2 4 6 8 10 12
14 (2+ 2Xm)
…
Prog(n) x
H(n,m)
Ahora podemos sumar 1 a la diagonal aplicando un método muy similar al argumento diagonal de Cantor a la diagonal de la última matriz obteniendo:
m-> 0
1 2 3 4 5
6 ….
m
Prog(0) x H(0,m)
1 0 0
0 0 0
0 0
Prog(1) x H(1,m) 0 1 0 0 0
0 0 0
Prog(2) x H(2,m) 0 1 3 3 4 5 6 m
Prog(3) x H(3,m) 2 4
6
9 10 12 14
(2+ 2Xm)
…
Prog(n) x
H(n,m)
La diagonal ha generado una nueva
secuencia del tipo
1 + Prog(n) x H(n,m)
La nueva secuencia difiere de
cualquiera de la lista por tanto H no existe. Se podría sugerir que n es en realidad R, el conjunto
de los números reales, pues no hay ningún
impedimento para que la lista de programas sea de este modo:
Prog(1) =
n+1
Prog(2) =
n+2
Prog(3) =
n+3
Hasta n = N
Y luego continuar con
Prog(n+1) =
n x 1
Prog(n+2) =
n x 2
Prog(n+3) = n x 3
Hasta n = N
Y luego continuar con
Prog(n+n+1) = n 1
Prog(n+n+2)
= n 2
Prog(n+n+2)
= n 3
Hasta n = N
Y así sucesivamente.
Pero a pesar de eso n sigue siendo N pues como demuestra Cantor, R no tiene una relación biyectiva con N mientras que en este caso no hay problema para establecer esa relacción con n por tanto n = N
Pero a pesar de eso n sigue siendo N pues como demuestra Cantor, R no tiene una relación biyectiva con N mientras que en este caso no hay problema para establecer esa relacción con n por tanto n = N
Hay otro método alternativo para ver que H no existe.
Como H no cambia el resultado del
programa podemos decir que H(k,k) = 1 si el programa tiene una salida y H(k,k)
= 0 si el programa no para.
Entonces podemos escribir que
1 + Prog(n) x H(n,m) = Tk(n)
Siendo Tk(n) el supuesto
algoritmo que se encuentra más abajo en una posición k. Pero si n = k
(diagonal)
1 + Prog(k)
x H(k,k) = Tk(k)
Pero si Tk(k) se para entonces
1 + Prog(k) x 1
= Tk(k) -> 1 +
Prog(k) = Tk(k)
Mientras que si no para
1 +
Prog(k) x 0 = Tk(k) -> 1 = Tk(k)
Lo cual es una inconsistencia.
Por tanto podemos concluir que no
existe un algoritmo capaz de determinar si un determinado algoritmo se parará.
Es decir no se puede programar cualquier algoritmo.
El mundo real
Podemos pensar que esto es sólo teoría, pues en el mundo práctico la mayoría de las veces nos
basta con 4 decimales para realizar cualquier cálculo con precisión. Por tanto
la máquina de Turing o programa que calcular pi, nos bastarían los 4 primeros decimales
y luego el algoritmo para. De este modo, supuestamente desaparecerían los problemas de las
Máquinas de Turing que no finalizan pues podemos implementar cualquier programa
para que finalice una vez alcanzados n decimales de precisión.
El caso práctico
que más decimales podría requerir es un cálculo de precisión, sería por ejemplo el
acelerador de partículas LHC del CERN donde el haz de partículas necesita estar
alineado con una precisión de un diámetro de un protón sobre un recorrido de
varias decenas de kilómetros. Aun así en este caso extremo bastarían unas pocas
decenas de decimales para realizar los cálculos, lo que apenas cambia nada pues
a una máquina de Turing le da igual calcular 4 que 40 decimales si al final
para.
Pero aun así en el mundo real no tenemos la garantía de que prácticamente todas las máquinas de Turing finalicen sus cálculos. Así pues, a pesar de esta consideración práctica. Existen procesos que pueden ser prácticamente infinitos o indefinidos, como ya se ha comentado anteriormente, un algoritmo que calcule para un número dado si este cumple la conjetura de Golbach. Elegido un número muy grande, este proceso de cálculo puede convertirse en virtualmente infinito o ilimitado.
Pero aun así en el mundo real no tenemos la garantía de que prácticamente todas las máquinas de Turing finalicen sus cálculos. Así pues, a pesar de esta consideración práctica. Existen procesos que pueden ser prácticamente infinitos o indefinidos, como ya se ha comentado anteriormente, un algoritmo que calcule para un número dado si este cumple la conjetura de Golbach. Elegido un número muy grande, este proceso de cálculo puede convertirse en virtualmente infinito o ilimitado.
No hay comentarios:
Publicar un comentario