Maquina de turing

-------------------------------------------------
Máquina 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 conjuntode estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento 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 ala izquierda o a la derecha(solo una celda a la vez), repitiendo esto 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.
Contenido [ocultar] * 1 Historia * 2 Definición formal * 2.1 Funcionamiento * 2.2 Representación como diagrama de estados. * 2.3 Descripción instantánea(DI). * 3 Ejemplo* 4 Modificaciones Equivalentes * 4.1 Máquina de Turing con movimiento "Stay" o "Esperar" * 4.2 Máquina de Turing con cinta infinita a ambos lados * 4.3 Máquina de Turing con cinta multipista * 4.4 Máquina de Turing con multicintas * 4.5 Máquinas de Turing Multidimensionales * 5 Máquinas de Turing deterministas y no deterministas * 6 Problema de la parada (haltingproblem) * 7 Codificación de una máquina de Turing * 8 Máquina Universal de Turing * 9 Máquina de Turing Cuántica * 10 Véase también * 11 Enlaces externos * 12 Referencias * 12.1 Notas al pie * 12.2 Bibliografía |
-------------------------------------------------
[editar]Historia

Diagrama artístico de una máquina de Turing.
El concepto de Máquina de Turing fueintroducido 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 a cualquier sentencia matemática y que nos diga si esa sentencia es cierta ono. 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.
Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionalesde 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 la má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 Tesisde Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.1
La idea subyacente es el concepto de que una máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible.-------------------------------------------------
[editar]Definición formal
Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla , donde:2
*  es un conjunto finito de estados.
*  es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
*  es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta. ()
*  es el estado...