En el año 1900 el prestigioso matemático alemán David Hilbert propuso
una serie de problemas, cuya resolución se consideraba clave para el avance
de las matemáticas y la ciencia en general, entre ellos estaba el conocido
con el Entscheidungsproblem, que se pregunta si existe un procedimiento
mecánico que resuelva todos los problemas matemáticos pertenecientes a un
tipo dado bien definido. Este problema fue el que motivó a Turing a
proponer la famosa máquina que lleva su nombre.
La máquina de Turing
 |
| Alan Turing |
Una máquina de Turing es un modelo formal de ordenador, un concepto
teórico de computación que formaliza el concepto de algoritmo. Más
adelante se dará una definición más formal de algoritmo, de momento puede
servir, la siguiente definición: un algoritmo es todo procedimiento que
realiza una tarea determinada en un número finito de pasos. Una máquina de
Turing consiste en una cinta de longitud infinita, dividida en celdillas, donde
cada una contiene una letra de un alfabeto o está en blanco. El alfabeto
consiste en un conjunto finito de símbolos, incluido el espacio en blanco. La
máquina tiene un cabezal para leer los símbolos en las celdillas y escribir
nuevos símbolos que sustituyan a los existentes cuando corresponda; cuando
el cabezal ha terminado de leer o escribir en una celdilla se mueve a la
derecha o a la izquierda de esa celdilla, una sola posición cada vez, salvo que
se llegue al estado de parada. La máquina tiene un número finito de estados,
y se dice que siempre se encuentra en cierto estado. Un programa consiste
en una lista de instrucciones, cada instrucción le indicará a la máquina una
computación a realizar; es decir, una serie de acciones, dados un estado
actual y un símbolo determinado bajo el cabezal, la instrucción le indicará
qué símbolo debe ser escrito en la cinta, y si el cabezal debe moverse un
paso a la izquierda o uno a la derecha. Una instrucción viene definida por una
quíntupla como la siguiente:
(estado inicial, valor inicial, nuevo estado, nuevo valor, movimiento)
La cinta se utiliza para almacenar datos, pero también se puede utilizar
para guardar una serie de instrucciones (pequeños programas o
subprogramas). En este último caso se dice que la máquina de Turing emula a
otra, la que se encuentra en la cinta, este tipo de máquina se conoce con el
nombre de máquina universal. Una observación crucial es que se demuestra
que solo hay un número contable de máquinas de Turing. Entendiendo por
conjunto contable aquel que es finito o se puede poner en correspondencia
uno a uno con el conjunto de los números naturales.
Tesis Church-Turing
El nombre algoritmo, y los adjetivos computable, mecánico y recursivo se
utilizan todos para denotar el carácter propio de las operaciones que puede
realizar una máquina de Turing. Definamos lo que es un procedimiento
mecánico M:
- M se expresa mediante un número finito de instrucciones, donde cada instrucción se construye a partir de un número finito de símbolos.
- M producirá, si se ejecuta sin error, el resultado deseado en un número finito de pasos.
- Un ser humano puede ejecutar M (en la práctica o en teoría) sin necesidad de utilizar ninguna máquina o artilugio, sólo provisto de lápiz y papel.
- El humano que ejecutase el procedimiento M simplemente tiene que seguir las instrucciones y los pasos que definen a M, no necesita de intuiciones o comprensión de lo que se está haciendo.
 |
| Alonzo Church |
Para cualquier procedimiento mecánico se puede encontrar una máquina
de Turing que lo represente y ejecute. En este sentido nos preguntamos si
el concepto de máquina de Turing incorpora todo procedimiento M mecánico.
Casi paralelamente al trabajo de Turing, sólo un poco antes Alonzo Church
descubrió el cálculo landa para abordar el mismo problema propuesto por
Hilbert en 1900. Un poco más tarde estos mismos autores demostrarán que
el cálculo landa y la máquina de Turing son equivalentes. Esto vino a
conocerse como la tesis de Church-Turing y viene a decir, que la máquina de
Turing (y el cálculo landa) definen lo que se entiende por algoritmo o
proceso mecánico. Esta tesis no era tan evidente hace 70 años, como lo
puede ser ahora gracias a la capacidad computacional de los ordenadores de
hoy día.
Turing demostró que hay cierta clase de problemas que no tienen
solución algorítmica, entre ellos el más famoso es “El problema de la
parada”. Turing muestra que para cierta clase de problemas la máquina que
lleva su nombre no para; es decir, no decide sobre los problemas, es lo que
llamamos la cuestión de la indecidibilidad. Con la
indecidibilildad el problema propuesto por Hilbert queda resuelto con una
respuesta negativa: No puede haber un algoritmo general que resuelva todo
problema matemático. Hay que tener cuidado de no extender las
conclusiones más allá de lo que permite el mismo problema resuelto. Los
algoritmos no dicen, ni pueden decir por sí mismos, nada sobre las verdades
de las sentencias o proposiciones matemáticas. Es indiscutible que la validez
de un algoritmo debe establecerse por medios externos al propio algoritmo.
Menos aún se pueden sacar conclusiones que impliquen a sistemas físicos
como el cerebro. De momento solo se puede decir que existen problemas
para los que no existe una máquina de Turing mientras esos mismos
problemas sí se intuyen por la mente humana. O de otra forma hay procesos
que puede realizar la mente humana que no son algorítmicos en el sentido de
existencia de una máquina de Turing.
No hay comentarios:
Publicar un comentario