Máquina de Turing

INTRODUCCIÓN


El concepto de Máquina de Turing fue introducido por Alan Turing en el trabajo “On computable numbers, with an application to the Entscheidungsproblem”, publicado por la Sociedad Matemática de Londres en 1936, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse acualquier sentencia matemática y que nos diga si esa sentencia es cierta o no.

Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

También descubrió que existen una serie de problemas que noson computacionalmente abordables y que reciben el nombre de “problemas no enumerables”.

Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y nodeterminismo respectivamente de la máquina de Turing.
La Máquina de Turing
Alan Mathison Turing (23 de junio de 1921 – 7 de junio de 1954)

Alan Mathison 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. En 1936 publicóel famoso artículo llamado “On computable numbers, with an application to the Entscheidungsproblem”. La Máquina de Turing, o Máquina de Computación Lógica, como la llamaba él, es una entidad matemática abstracta que formalizó el concepto de algoritmos y resultó ser la precursora de las computadoras digitales. Con ayuda de su máquina pudo demostrar que existen problemas irresolubles, tales queninguna máquina de Turing será capaz de obtener su solución. Fue quizás su mayor aportación y con seguridad su descubrimiento de mayor transcendencia, ya que abrió el camino de la ciencia de la Computación.

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 elmundo e interactuar con él.

Uno de los conceptos más importantes relacionados con la máquina de Turing es que ésta sirve como un modelo para la definición de algoritmo. El concepto de máquina de Turing captura a todos los algoritmos. Dado que la definición formal de algoritmo fue dada mediante la máquina de Turing, es posible escribir cualquier algoritmo computacional en términos ésta, de hecho,en teoría, todo algoritmo computacional puede ser resuelto por una máquina de Turing.
Descripción de la máquina de Turing
La máquina de Turing modela matemáticamente a una máquina que opera mecánicamente sobre una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, usando un cabezal lector/escritor de cinta. La operación está completamente determinada por unconjunto finito de instrucciones elementales.

Turing describe el dispositivo de la siguiente manera:
“A la máquina se le suministra una ‘cinta’ (análoga al papel) que pasa a través de ella, y está dividida en secciones (llamadas ‘cuadrados’) cada uno con la capacidad de contener un ‘símbolo’. En cualquier momento solo hay un cuadrado, digamos el r-th, el cual contiene el símbolo G(r) el cualestá ‘en la máquina’. Llamaremos a este cuadrado el ‘cuadrado escaneado’. El símbolo en el cuadrado escaneado puede ser llamado el ‘símbolo escaneado’. El símbolo escaneado es el único del cual la máquina está ‘directamente consiente’, por decirlo de alguna forma. Sin embargo, mediante la modificación de su configuración la máquina puede recordar efectivamente algunos de los símbolos que ha...