La Maquina De Turing

REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL POLITECNICA
DE LA FUERZA ARMADA NACIONAL BOLIVARIANA
NUCLEO FALCON SEDE CORO

la maquina de turing





Bachilleres:
Molleda Freddy
Santa Ana de Coro, mayo de 2012

Lamaquina de turing
Una máquina de Turing es una representación abstracta de un dispositivo de cómputo o informático. Consiste en una cabeza de lectura/escritura que examina una dimensión posiblemente infinita de una cinta bidireccional dividida en cuadros cada uno de los cuales está identificado con un 0 o un 1. El Cómputo empieza con la máquina, en un estado dado, examinando un cuadrado. Borra loque encuentra allí, imprime un 0 o 1, se mueve a un cuadrado adyacente, y entra en un nuevo estado. Esta conducta es completamente determinada por tres parámetros: (1) el estado en que la máquina está, (2) el número en el cuadrado está examinando, y (3) una tabla de instrucciones. Esta es una máquina ideal -formalmente hablando se trata de un algoritmo- en dos aspectos básicos. La primeraidealización se debe a que su memoria es ilimitada. La segunda idealización se produce por el hecho de una máquina de Turing nunca comete errores. A efectos de representar una máquina de Turing, podemos imaginarla como una cinta infinita dividida en cuadros sobre la que se realizan las operaciones de manipulación de símbolos.
Una máquina de Turing con una sola cinta puede definirse como una 7-tupladonde:
*  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 inicial.
*  es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
*  esel conjunto de estados finales de aceptación.
*  es una función parcial denominada función de transición, donde  es un movimiento a la izquierda y  es el movimiento a la derecha.
Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo  como símbolo de "no movimiento" en un paso decómputo.

Idea principal de la maquina de turing
En 1931, el matemático checo Kurt Godel descubrió que había teoremas matemáticos que eran verdaderos aun 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 reglaslógicas.
Para hacerlo, ideó una máquina imaginaria capaz de realizar de manera totalmente mecánica los 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 queuna máquina sería capaz de resolver siguiendo reglas lógicas. Si esta lista abarcaba todos los problemas 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 maquinas concluyo que era posible diseñar un articulo único capaz de cumplir las funciones de cualquier otra maquina de turing. A esta se lellamo la “maquina universal de turing”.
Donde nació la maquina de turing
Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application to theEntscheidungsproblem, 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...