¿Qué es una Máquina de Turing? (i)

Una respuesta que genera muchas preguntas

Una Máquina de Turing es un modelo matemático que consiste en un autómata capaz de implementar cualquier problema matemático expresado por medio de un algoritmo. Dicho esto, alguien podría preguntarse porqué esta sección no se llama Respuestas difíciles a preguntas fáciles, pero no se alarmen. Para poder explicar bien los que es una máquina de Turing y, lo que me interesa más, porqué es tan importante, voy a necesitar que comprendan bien la frase con la que se inicia este artículo. Así que, como dijo aquel, vayamos por partes.

Alan Turing

Antes de meternos de lleno en esta explicación acerca de la Máquina de Turing, hagamos una pequeña referencia a la persona que la descubrió y que le da nombre.

Alan Turing fue un matemático inglés que vivió durante la primera mitad del siglo XX. Aunque fue un matemático brillante en muchos campos, destacando especialmente en criptografía, su principal interés se centraba en la lógica, que en aquellos momentos se encontraba en plena ebullición gracias al intento de David Hilbert de hallar una formulación de las matemáticas sobre una base estricta de lógica formal. La Máquina de Turing, o Máquina de Computación Lógica como la llamaba él, fue quizás la mayor aportación de Alan Turing a esta tarea y con seguridad su descubrimiento de mayor transcendencia, ya que abrió el camino de la ciencia de la Computación, que a su vez nos lleva al computador que en estos momentos estoy utilizando para escribir esto, o al que usted está usando para leerlo. En definitiva, Alan Turing fue uno de los científicos más importantes de la primera mitad del siglo XX y, sin duda, una de las mentes que más influyó en la manera actual que tenemos de ver el mundo e interactuar con él.

El problema de la decisión

Dentro del esfuerzo de Hilbert y su equipo por formalizar las matemáticas, se planteó una pregunta para la que no había respuesta: ¿Es posible encontrar una manera sencilla de decidir si un problema matemático cualquiera tiene solución? Cuidado que nos podemos confundir, la pregunta no es si podemos encontrar un método sencillo para descubrir la solución de cualquier problema, sino de decidir (o, si se prefiere, comprobar) si un problema cualquiera puede solucionarse siempre o si existen problemas para los que no puede encontrarse ninguna solución.

Esto, que parece un mero entretenimiento algo freak, tuvo una importancia trascendental, ya que una respuesta afirmativa significaba que todos los problemas matemáticos tenían una solución, y por tanto el proyecto de formalizar todo el conocimiento matemático como una ciencia completa y sin fisuras tendría mayores posibilidades de ser viable.

Problemas matemáticos

Pero ¿qué es exactamente un problema matemático? Cuando se habla de un problema de matemáticas, a la mayoría de las personas les viene a la cabeza la idea de una serie de cálculos más o menos complicados que hay que resolver, algo que es lógico teniendo en cuenta la forma en la que nos enseñaron las matemáticas a la mayoría de nosotros. Pero la realidad está bastante lejos de eso.

Se podría decir que un problema matemático es una afirmación de una determinada naturaleza que hay que determinar si es cierta o falsa. Veámoslo con un ejemplo.

Uno de los problemas matemáticos más célebres es el de la cuadratura del circulo, que dice:

¿Se puede construir un cuadrado, utilizando regla y compás, que posea un área igual a la de un círculo dado?

Alguien podría decir: pero vamos a ver, esto es una pregunta, ¿no acaba de decir que un problema matemático es una afirmación? Bueno sí, es cierto, pero si nos fijamos podemos escribir:

Se puede construir un cuadrado, utilizando regla y compás, que posea un área igual a la de un círculo dado.

Ésta expresión, que es una afirmación, es equivalente a la primera. Lo único que cambia es la forma de la respuesta: en el primer caso será sí o no, y en el segundo caso será la afirmación es verdadera o es falsa, pero el significado es el mismo en ambos casos.

Haciendo un pequeño esfuerzo, nos podemos imaginar cualquier problema matemático en forma de afirmación: Dos y dos suman cuatro es una afirmación verdadera, el área de un cuadrado es el cuadrado de la longitud de su lado es una afirmación verdadera y para cualquier trío de números enteros a, b y c y cualquier número entero n mayor que dos se cumple que aⁿ+bⁿ=cⁿ es una afirmación falsa (hay una demostración maravillosa para esto, pero la que conocemos tiene 98 páginas)

Por tanto, ahora sí podemos comprender que el problema de la decisión consiste en decidir si se puede saber siempre si una afirmación (vista como un problema matemático) es verdadera o falsa, o por el contrario existen afirmaciones cuya naturaleza no se puede determinar.

Por cierto, la afirmación referente a la cuadratura del círculo es falsa.

Implementar un algoritmo

Ya sabemos lo que es un problema matemático, pero ¿qué es un algoritmo? Por suerte esto es mucho más sencillo.

Un algoritmo es un conjunto ordenado de pasos elementales que nos ayudan a resolver un problema. Por ejemplo, si quiero ver el televisor, podría utilizar el siguiente algoritmo para hacerlo:

1. ¿Estoy en el salón?

1.1 No → ir al salón, volver a 1

1.2 Si → pasar a 2

2. ¿Está encendido el televisor?

2.1 No → encenderlo, volver a 2

2.2 Si → pasar a 3

3. ¿Quiero seguir castigando mi cerebro?

3.1 No → apagarlo, FIN

3.2 Si → volver a 2, tú verás lo que haces

Así, un problema matemático expresado por medio de un algoritmo no es más que una afirmación que puede resolverse en un número determinado de pasos elementales. Por ejemplo, dos más dos es cuatro se puede resolver partiendo del dos, sumándole uno, sumándole otro uno y comprobando el resultado. Como éste es cuatro, la afirmación es verdadera.

Definir ahora lo que significa implementar es fácil: implementar un algoritmo es leerlo y ejecutarlo (ponerse a ver la tele o apagarla, vamos). Así que lo que hemos sacado en claro por ahora es que una Máquina de Turing es algo que implementa algoritmos que representan un problema matemático.

Llegados a este punto, nos tomaremos un pequeño respiro y volveremos con la segunda parte del artículo, en la que explicaré lo que es un autómata, un modelo matemático y, por fin, una Máquina de Turing.

Lo publicó Javier Oribe en  El Máquina de Turing.