La maquina de turing

CONTENIDO

DEFINICION 5
HISTORIA 5
CARACTERISTICAS FORMALES 6
FUNCIONAMIENTO 7
REPRESENTACION COMO DIAGRAMAS DE ESTADOS 8
Máquina de Turing con movimiento stay o "esperar" 8
MÁQUINA DE TURING CON CINTA INFINITA A AMBOS LADOS 9
MÁQUINA DE TURING CON CINTA MULTIPISTA 9
MÁQUINA DE TURING MULTICINTA 10
MÁQUINA DE TURING MULTIDIMENSIONAL 10
MAQUINA DE TURING DETERMINISTA Y NODETERMINISTA 11
MAQUINA UNIVERSAL DE TURING 11
EN CONCLUSION 14

INTRODUCCION

En el siguiente trabajo se mostrará una consulta realizada con respecto al tema de la Máquina de Turing, en el se observara una definición general con respecto al tema en cuestión.
Una vez realizada la definición al tema propuesto, entraremos a tratar aspectos netamente ligados a dicho tema, es decir, revisaremosun poco su historia y por quien fue propuesto el concepto o invención del mismo. A partir de ello revisaremos un poco los diferentes modelos o tipos de Máquina de Turing, como funcionan dichos modelos y las características que los diferencian a cada uno de los modelos revisados y dentro de dichas características observaremos algunas imágenes que han sido adheridas al texto para tratar deilustrar un poco los tipos explicados.

LA MAQUINA DE TURING

DEFINICION
La máquina de Turing (MT) es un diseño de las ciencias de la computación que realiza una lectura y una escritura de manera automática sobre una entrada la cual se denomina cinta, generando una salida ó resultado en dicha cinta. Básicamente la máquina de Turing resulta ser un autómata que se mueve sobre una secuencia de datos. Se dice que la máquina de Turing es más un modelo matemático que un dispositivo físico o mecánico, el hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren la implementación real de un dispositivo, lo que ha motivado que existan muchas versiones prácticas del mismo modelo.
Este modelo está formadopor 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. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso,borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite 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.

HISTORIA
Alan Turingintrodujo el concepto de máquina de 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 que 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 esasentencia 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.
Mediante este modelo teórico y el análisis de la complejidad de los algoritmos, fue posible la categorizaciónde problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones pueden encontrarse en tiempo polinomico por máquinas de Turing deterministas y no deterministas, respectivamente.
Precisamente, la tesis de Church-Turing formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX caracteriza la...