Maquinas de turing

Máquinas de Turing
Actualmente existen gran cantidad de ordenadores, capaces de realizar sorprendentes funciones. Todos ellos, sin embargo, están basados en un simplísimo artilugio imaginario capaz de hacer cualquier operación matemática computable; esto es, que se pueda realizar de una forma totalmente mecánica. Son las máquinas de Turing.
Alan M. Turing.
Biografía
Alan Mathison Turingnació en 1912, y muy pronto mostró una extraordinaria intuición científica.
Mientras su padre se hallaba en Madrás, trabajando para el Indian Civil Service, Turing ganó numerosos premios escolares, y más tarde una beca que le llevaría al King's College de Cambridge. Fue aquí cuando empezó a interesarse seriamente por los problemas de lógica matemática.
En 1931, el matemático checo Kurt Godeldescubrió que había teoremas matemáticos que eran verdaderos aún cuando no se pudiesen probar. Ante esto, Alan Turing se puso a investigar aquellos que sí podían ser probados. Quería intentar demostrar la vieja idea de que las matemáticas no son un arte misterioso, sino una ciencia exacta regida por reglas lógicas.
Para hacerlo, ideó una máquina imaginaria capaz de realizar de manera totalmente mecánicalos procesos que normalmente llevaría a cabo un matemático. Había una máquina para cada proceso; así, había una máquina que sumaba, otra que multiplicaba, etc. Estas máquinas acabarían por recibir el nombre de "Máquinas de Turing". Básicamente, lo que quería era hacer una lista de los problemas que una máquina sería capaz de resolver siguiendo reglas lógicas. Si esta lista abarcaba todos losproblemas matemáticos, entonces su tesis quedaría demostrada, y con ella la teoría de la computabilidad.
Tras estudiar con detenimiento el funcionamiento de sus máquinas, concluyó que era posible diseñar un artilugio único capaz de cumplir las funciones de cualquier otra máquina de Turing. A ésta se le llamó la "Máquina Universal de Turing".
Al estallar la Segunda Guerra Mundial, Turing fue alejadodel mundo académico y reclutado por la Escuela de Códigos y Cifrados del gobierno británico. Las actividades que realizaba consistían de manera primordial en descifrar el código militar alemán ENIGMA. Para ello desarrolló el invento más secreto de dicha guerra: el Colossus, primer ordenador electromecánico del mundo. Más adelante, sería destinado a los Estados Unidos con el fin de crear unos códigosseguros para las comunicaciones transatlánticas entre los países aliados. Acabada la guerra, Turing colaboró en la construcción del ENIAC. Posteriormente recibió el encargo de empezar a trabajar en la construcción de un ordenador totalmente británico, destinado al National Physical Laboratory, y que recibiría el nombre de ACE (Automatic Computing Engine).
Esta máquina tardó mucho tiempo en serconstruida, pero era superior a ENIAC en muchas características. Frustrado por el lento avance, dimitió y se fue a vivir a Manchester, colaborando en el proyecto del MARK I, el ordenador de la universidad. Al mismo tiempo, era asesor de la compañía Ferranti y, por tanto, colaboró en la construcción de los primeros ordenadores fabricados en Gran Bretaña.
En 1952, Turing fue acusado dehomosexualidad, y dos años más tarde se suicidó.
¿Qué es una máquina de turing?

Es un dispositivo de reconocimientos de lenguaje, es más general que cualquier autómata finito y cualquier autómata de pila, debido a que ellas pueden reconocer tanto los lenguajes regulares, como los lenguajes independientes de contexto y además muchos otros tipos de lenguajes.

La máquina de Turing (abreviado MT) tiene, uncontrol finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el
carácter blanco (que representaremos con “t”). La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el...