Maquina de turnig
Mauricio Vinueza M., Universidad Autónoma de Quito - UNAQ, Quito - Ecuador
Objetivo
Explicar que es una Maquina de Turing y su funcionamiento general.
Definición
Unamáquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular lalógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador.
Introducción
La máquina de Turing fue descrita por AlanTuring como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society, La máquina de Turing no está diseñada como una tecnología de computación práctica, sino comoun dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.
Una máquina de Turing que es capazde simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal).
Una definición más matemáticamente orientada, con una similarnaturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una formal teoría de la computación conocida como la tesis de Church-Turing.La tesis señala que las máquinas de Turing de hecho capturan la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una precisa definición de un algoritmo o'procedimiento mecánico'.
Trabajo Técnico
Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia(generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos...
Regístrate para leer el documento completo.