Maquinas de turing

Máquina de Turing (MT)

Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Sufuncionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres(la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando el símbolo, escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una celda a la vez), repitiendoesto según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
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 planteadapor David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier 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 cualquiercómputo que un computador digital sea capaz de realizar.
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 no determinismo respectivamente de lamáquina de Turing.
De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX..
La idea subyacente es el concepto de que una máquina de Turing es una persona ejecutando unprocedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible.

Las maquinas de Turing se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

Imagen 1.0
Modificaciones Equivalentes
• Una Razón para aceptar la Máquina de Turingcomo un modelo general de cómputo es que el modelo que hemos definido anteriormente es equivalente a muchas versiones modificadas que en principio pareciera incrementar el poder computacional.
Máquina de Turing con movimiento "Stay" o "Esperar"
• La función de transición de la MT sencilla esta definida por δ :Q x Γ → Q x Γ x {L, R}, la cual puede ser modificada como δ: Q x Γ → Q x Γ x {L, R, S} .Donde S significa "permanecer" o "esperar", es decir no mover el cabezal de lectura/escritura. Por lo tanto δ(q, σ ) = (p, σ’, S) significa que se pasa del estado q al p, se escribe σ’ en la celda actual y la cabeza se queda sobre la celda actual.

Máquina de Turing con cinta infinita a ambos lados
• Esta modificación se denota al igual que una MT sencilla, lo que la hace diferente es que lacinta es infinita tanto por la derecha como por la izquierda lo cual permite realizar transiciones iniciales como δ(q0, x) = (q1, y, L).
Máquina de Turing con cinta multipista
• Es aquella que mediante la cual cada celda de la cinta de una máquina sencilla se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas. Se...