Maquina de Turing

Investigación: Máquina de Turing
¿Qué es una máquina de Turing?
Una máquina de Turing (MT) es un dispositivo de reconocimientos de lenguaje, que permite reconocer lenguajes tanto regulares, comolibres de contexto y sensibles al contexto, entre otros.
La máquina de Turing en esencia es un mecanismo que formaliza el concepto de algoritmo, siendo tan general como para poder resolver cualquierproblema que pueda representarse por medio de un programa computable. Esto también implica que, si el problema es irresoluble para una máquina de Turing, entonces lo es para cualquier computadora.Esta máquina fue creada por Alan Turing, de quien obtuvo su nombre, en un trabajo publicado por la Sociedad Matemática de Londres en 1936. En este trabajo se aborda el tema de si las matemáticas sondecidibles. Esto quiere decir, que si hay una forma definida de demostrar si una determinada sentencia matemática es cierta o no. Turing diseñó un modelo formal de computador para demostrar que existíanproblemas que un ordenador no era capaz de solucionar; así, la máquina que él diseñó permitió realizar cualquier operación que una computadora pudiera realizar. Todos aquellos problemas que no pudieranser resueltos, Turing los incluyó en un conjunto de "problemas no enumerables".
¿Cómo funciona una máquina de Turing?
La máquina de Turing tiene un control finito, así como una cinta donde seencuentra la palabra de entrada. Esta cinta es de longitud infinita hacia la derecha, donde todos los espacios inutilizados son caracteres blancos (nulos), y finita hacia la izquierda. La cabeza lectora estanto de escritura como de lectura y se mueve bidireccionalmente, por lo que puede hacer modificaciones sobre la cinta durante el curso de la ejecución, y repetir una parte de la cinta cuantas vecessea necesario.
Se conforma por un alfabeto de entrada, uno de salida, un carácter blanco (ya sea b o 0), un conjunto de estados finitos y otro conjunto de transiciones entre dichos estados....