La Máquina de Turing

Alan Turing fue un matemático, informático teórico y criptógrafo, considerado el padre de la computación, ya que fue el precursor de la informática moderna, gracias a la máquina de Turing, aporto conceptos de algoritmos y computación de forma influyente.

El día de hoy, he visto una pequeña escena de la película biográfica de Alan Turing llamada “Breaking the code” en YouTube, esta escena toma lugar en 1939, cuando Alan Turing está siendo reclutado por el Gobierno Británico para descifrar el código de los Nazi llamado “Enigma”, y muestra la entrevista con Dillwyn Knox, quien encuentra el trabajo de Turing incomprensible, por lo que le pide a Turing que le dé una explicación en “términos generales” sobre una frase que tiene en su expediente que dice: “Los números computables, con una aplicación al Entscheidungproblem”, la respuesta que le da Turing a Knox es asombrosa, muy compleja e interesante.

Alan Turing empieza a hablar sobre lo difícil que es determinar lo bueno de lo malo ya que la mayoría de la gente piensa que en las matemáticas siempre se sabe lo que está bien y lo que está mal, y el cómo es que Bertrand Russel escribió un libro inmenso sobre el tema llamado “Principia Mathematica”, en el cual deseaba romper todos los conceptos matemáticos y argumentos en pedazos y luego demostrar que podían derivarse de la lógica pura, lo cual no pudo hacer, pero expuso que este libro fue muy importante e influyente, ya que logro influir tanto a David Hilbert como a Kurt Gödel, dando lugar a una nueva clase de matemáticas. Luego Turing explica que David Hilbert miro el problema desde un ángulo completamente diferente, y dijo: “si vamos a tener un sistema fundamental para las matemáticas, debe cumplir tres requisitos básicos: coherencia, completitud y decidibilidad”.

Turing explica los tres requisitos de la siguiente manera:

1. Coherencia: “se entiende que usted no obtendrá jamás una contradicción en su propio sistema, es decir, usted nunca será capaz de seguir las reglas de su sistema y acabar mostrando que dos y dos son cinco.”
2. Completitud: “significa que si cualquier declaración es verdadera, tiene que haber alguna manera de probarlo utilizando las reglas de su sistema.”
3. Decidibilidad: “significa que debe de existir algún método, algún procedimiento definido o de prueba, que se puede aplicar a cualquier afirmación matemática determinada y que decidirá si esa afirmación es o no demostrable.”

Turing expresa que Hilbert pensaba que estos tres requisitos eran un conjunto muy razonable de requerimientos a imponer, pero después Kurt Gödel demostró que ningún sistema para las matemáticas puede ser a la vez coherente y completo, mediante la construcción de una afirmación matemática que decía: “Esta afirmación no puede probarse.”, esta afirmación fascinaba a Turing, ya que se pudiera demostrar o no, simplemente demostraba que las matemáticas son siempre inconsistentes o incompletas, ya que si se podía demostrar, teníamos una contradicción, y el sistema sería incoherente, y en caso de que no se pudiera demostrar, la afirmación era verdadera, pero no podría probarse, lo que significa que el sistema es incompleto.

Pero Turing expresa que faltaba el tercer punto, ya que debería existir un método claramente definido para decidir si o no las afirmaciones matemáticas son demostrables, el problema de la decisión llamado “El Entscheidungsproblem.”

Turing expresa que demostró que no puede haber un método que funcione para todas las preguntas, ya que resolver problemas matemáticos requiere de una fuente infinita de nuevas ideas, siendo necesario examinar la demostrabilidad de todas las afirmaciones matemáticas del pasado, presente y futuro, pero gracias a que la gente había estado hablando sobre la posibilidad de un método mecánico, por lo que Turing concibió la idea de una máquina que sería capaz de escanear símbolos matemáticos, para leer una afirmación matemática y llegar al veredicto de si la afirmación es demostrable o no, con lo que fue capaz de demostrar que Hilbert estaba equivocado.

Todo eso para explicar en términos generales sobre los números computables con una aplicación al Entscheidungproblem, definitivamente Turing es considerado lo que es debido a su gran capacidad e intelecto, definitivamente es una de las personas que vale la pena admirar por sus grandes aportes a la humanidad.

Dejo el vídeo para que lo puedan ver, y espero que les guste.