Síntesis videos mt

Instituto Tecnológico Superior
Ingeniería en Sistemas Computacionales

Síntesis de Video

Máquina de Turing

Las máquinas de Turing son mecanismos de cómputo de muy bajo nivel, pero son muypotentes al igual que los lenguajes de programación que utilizamos cotidianamente. No son fáciles de programar, debido a su sencillez, y gracias a esta característica se utilizan para demostrar que algono se puede resolver con ningún lenguaje de programación.

Unas de las características de estas máquinas es que tienen memoria infinita. En cambio nuestras máquinas reales, tienen memoria finita,por lo tanto se pueden describir por un AFD.

Las máquinas de Turing tienen un grafo de estados y transiciones, y además tienen una cinta, es decir, una palabra con infinitas posiciones. Lasposiciones se numeran de 0 al infinito. En la posición 0 hay un símbolo de inicio que no forma parte del alfabeto de entrada. Para que un autómata pueda manejarlo, debe de haber siempre un apuntador a una delas posiciones de la cinta. Ese apuntador es llamado cabezal. Las transiciones de ese autómata tendrán la condición de que el valor dentro de la posición que apunta el cabezal debe ser 1 concreto.Cada transición debe de tener acciones, que indica que símbolo se debe de escribir a donde apunta el cabezal y si se desea mover a éste hacia la derecha, a la izquierda o simplemente no moverlo.

Alprincipio la máquina se encontrará en el estado inicial, el cabezal apuntará a la posición 1 y en el resto de la cinta se encontrará la palabra de entrada. Al final de la palabra, es decir, después delúltimo símbolo de entrada, tendremos un símbolo de blanco; a partir de ahí, los símbolos serán blancos.

La máquina comienza a ejecutar sus transiciones siempre y cuando se cumplan las condicionesdadas. El cabezal se desplazará y el contenido de la cinta cambiará. Los símbolos escritos pueden ser del mismo alfabeto de entrada o no serlo. Esa palabra será aceptada si se llega al estado...