Estudiante Universitario

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 deComputació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 loscientí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 problemamatemá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 entretenimientoalgo 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 unproblema 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 determinadanaturaleza 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 unaafirmació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...