Hasta ahora en el desarrollo de la teoría de computación hemos presentado varios modelos de dispositivos informáticos. Los autómatas finitos son buenos modelos para los dispositivos que poseen una pequeña cantidad de memoria. Automata pushdown son buenos modelos para dispositivos que tienen una ilimitada memoria que es utilizada solo en los últimos en, primero en salir de forma de una pila. Hemos demostrado que algunas son tareas muy simples más allá de la compatibilidad de estos modelos.

Maquina de Turing
Pasamos ahora a un modelo mucho más potente, propuesta por primera vez por Alan Turing en 1936, llamado la máquina de Turing. Una maquina de turing puede hacer todas las cosas que una computadora real puede hacer. Sin embargo, incluso una maquina de turing no puede resolver determinados problemas. En un sentido muy real, estos problemas están más allá de los límites teóricos de la computación.
El modelo de máquina de Turing utiliza una infinidad de cintas como su memoria ilimitada. Como una cinta de cabeza que puede leer y escribir símbolos moverse en la cinta.
Inicialmente, la cinta sólo contiene la cadena de entrada está en blanco y en todas partes. Si la maquina necesita para almacenar información, puede escribir esta información en la cinta. Para leer la información que ha escrito, la máquina sigue la informática hasta que se decida a producir una salida, el aceptar y rechazar los productos se obtienen mediante la introducción de la aceptación y el rechazo designado estados. Si no entra una aceptación o un rechazo de Estado, se van para siempre, nunca detener.

Si te gusto la información de esta pagina web puedes dejarnos un comentario en nuestro libro de visitas click aquí :)