Máquina de Turing

Turing

Alan Mathison Turing, OBE, fue un matemático, lógico, científico de la computación, criptógrafo, filósofo, biólogo teórico, maratoniano y corredor de ultradistancia británico. ​​​​​ Es considerado uno de los padres de la ciencia de la computación y precursor de la informática moderna.

DISEÑAR UNA MAQUINA DE TURING QUE CALCULA EL NUMERO CONSECUTIVO DE UN NUMERO DADO EN BINARIO

Si el número es par, su último bit es 0. La máquina sólo tiene que cambiar este 0 por un 1.
Si el número es impar, su último bit es 1. En este caso, se tiene que cambiar por 0’s todos los 1’s seguidos que haya escritos de derecha a izquierda hasta llegar al primer 0, que se cambia por un 1. Si no hay ningún 0, entonces se tiene que añadir un 1 delante del número (añadir un bit). Es decir, escribir un 1 en la casilla en blanco (B) a la izquierda del número.
Vamos a considerar tres estados:

q0,q1,q2q0,q1,q2

·                     Inicialmente, la MT está en el estado q0 con la cabeza señalando la primera cifra del número.
La MT recorre todo el número para ver si es par o impar sin modificar su cinta.

δ(q0,0)=(q0,0,R)δ(q0,0)=(q0,0,R)
δ(q0,1)=(q0,1,R)δ(q0,1)=(q0,1,R)

·                     Notemos que, por ahora, la MT se detiene al llegar al primer símbolo en blanco a la derecha del número.
La MT vuelve a la anterior casilla (último número). Si es un 0, lo cambia por un 1 y pasa al estado final que es q2 . Para hacer esto usaremos el estado q1 :

δ(q0,B)=(q1,B,L)δ(q0,B)=(q1,B,L)
δ(q1,0)=(q2,1,R)δ(q1,0)=(q2,1,R)

·                     Si el número es impar, la MT no ha cambiado el último número, pero está en el estado q1 . Tiene que cambiar todos los 1's consecutivos que haya de derecha a izquierda.

δ(q1,1)=(q1,0,L)δ(q1,1)=(q1,0,L)
·                     Por ahora, la MT se para cuando llega al primer 0 (de derecha a izquierda) ó en un símbolo en blanco. Si es un 0, lo cambia por un 1 y el proceso finaliza:

δ(q1,0)=(q2,1,L)δ(q1,0)=(q2,1,L)

(Hemos escrito un desplazamiento a la izquierda, pero esto no tiene importancia ya que la MT ha llegado al estado final).
·                     Si lo que señala la cabeza es un blanco en vez de un 1, tiene que cambiarlo por un 1 y finalizar el proceso.

δ(q1,B)=(q2,1,L)δ(q1,B)=(q2,1,L)

El diagrama de la máquina es



Donde el cuadro representa el símbolo en blanco B.
Vamos a simular la MT para varias entradas. Mostraremos el estado final de la cinta y la posición de la cabeza (sombreado en color rosa).

Entrada: 000; Resultado esperado: 001.

Entrada: 0011; Resultado esperado: 0100.

Entrada: 111; Resultado esperado: 1000.


Entrada: 1; Resultado esperado: 10.


EJERCICIO:

Aparte de la cadena 001 demostrar 5 cadenas que acepte  y 3 que no acepte esta Máquina de Turing.

Comentarios

Publicar un comentario

Entradas más populares de este blog

Traductores: Ensambladores, compiladores e intérpretes

  Ensambladores:  son los encargados de transformar o traducir los programas escritos en ensamblador a su equivalente en código maquina o binario para que pueda ser ejecutado por la CPU. Este fue el primer lenguaje de programación que tradujo el lenguaje maquina a un lenguaje más natural para el ser humano. Con todo esto podemos decir que el lenguaje ensamblador es un lenguaje de programación de bajo nivel que se utiliza para escribir programas para computadoras, es la representación más directa del código máquina comprensible por los programadores. El lenguaje ensamblador se usó para la creación de programas en el pasado, actualmente se usa muy poco. Únicamente cuando se requiere un control directo del hardware o se quiere conseguir rendimientos poco comunes de los equipos. Un programa escrito con el lenguaje ensamblador seguirá los siguientes pasos: este programa tiene una serie de instrucciones que contienen las órdenes a seguir para llevar a cabo una acción. Todas...
Leer más

Clasificación de los Compiladores

El programa compilador traduce las instrucciones en un lenguaje de alto nivel a instrucciones que la computadora puede interpretar y ejecutar. Para cada lenguaje de programación se requiere un compilador separado. El compilador traduce todo el programa antes de ejecutarlo. Los compiladores son, pues, programas de traducción insertados en la memoria por el sistema operativo para convertir programas de cómputo en pulsaciones electrónicas ejecutables (lenguaje de máquina). Tipos compiladores: Una sola pasada:  examina el código fuente una vez, generando el código o programa objeto Pasadas múltiples:  requieren pasos intermedios para producir un código en otro lenguaje, y una pasada final para producir y optimizar el código producido durante los pasos anteriores. Optimación:  lee un código fuente, lo analiza y descubre errores potenciales sin ejecutar el programa. Compiladores incrementales:  generan un código objeto instrucción por instrucción (en vez de hacerlo ...
Leer más

Automatas de pila Unidad 2

Introducción De igual manera que los lenguajes regulares se pueden representar mediante autómatas finitos deterministas, los lenguajes independientes del contexto tienen su correspondencia en otro tipo de dispositivo: el Autómata a Pila (AP). Un autómata a pila es un dispositivo que tiene acceso a: Una secuencia de símbolos de entrada, que en general se representa por una cinta que se desplaza frente a un mecanismo de captación de dichos símbolos. El símbolo superior de una memoria en pila (LIFO) Un autómata a pila se encuentra en cada momento en un estado determinado y el estado siguiente depende de los tres elementos siguientes:  estado actual símbolo de entrada  símbolo superior de la pila Generalmente, el autómata a pila es no determinista en el sentido de que se permite que haya varias acciones posibles en cada momento. Un AP puede realizar dos tipos de operaciones elementales: Dependientes de la entrada.  Se lee la cinta y se av...
Leer más