Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Maquina de Turing

Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas.
by

jose doria

on 16 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Maquina de Turing

Maquina de Turing La má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, La máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de un computador. Alan Turing Características hablemos de historia Ejemplo FUNCIONAMIENTO Construcción lógica Dispositivo mecánico: cinta infinita, dividida en celdas, con un cabezal de lectura/escritura que se mueve sobre dicha
cinta, avanzando una celda cada vez.
Analogía: humano con un papel cuadriculado infinito, con lápiz y goma, que puede escribir/leer un símbolo en cada cuadrícula cada vez. Operaciones que realiza: a) Estando en un estado p, lee un símbolo en la celda sobre la que se encuentra la cabeza.
b) Pasa a un nuevo estado
c) Escribe un nuevo símbolo en la cinta (que reemplaza al anteriormente leído, salvo que se escriba el mismo)
d) Mueve la cabeza de L/E a izda., dcha o se para Características de la Cinta: cinta infinita
• puede contener un carácter por celda
• se puede leer de ella
• se puede escribir en ella
• se considera con blancos a la derecha e izquierda
• se puede desplazar a izda, dcha, una celda cada vez, o parar Presentado En el siguiente ejemplo muestra una de estas tablas.  Representa el comportamiento de una máquina de turing que es capaz de sumar 1 a cualquier número unario.  El alfabeto solo tiene dos símbolos:  Vacío (0) y valor (1).  La máquina puede adoptar tres estados diferentes numerados del 0 al 2 (es costumbre señalar el estado inicial con 0).  El movimiento H ("Halt") significa no desplazar el cabezal.  En este caso la máquina se detiene (o entra en un bucle sin fin). La tabla suele definirse mediante una matriz de cinco columnas que contiene:

Estado/Carácter-leído/Carácter-a-escribir/Movimiento/Nuevo-estado También es posible representar la tabla de acción mediante un grafo.  Los diferentes estados internos se representan por círculos.  Los cambios de estado con flechas a las que se añade una leyenda.  Generalmente se utiliza una flecha para señalar el estado inicial.  En la figura 1 se muestra el grafo correspondiente a la tabla. Existe una tabla de acción , que contiene las instrucciones de lo que hará el autómata.  Estas instrucciones representan en cierta forma el "programa" de la máquina.  Las ejecución de cada instrucción de la tabla de acción incluye cuatro pasos:

Leer un carácter en la posición actual.
Escribir un nuevo símbolo en esta posición (puede ser el mismo que había).  El símbolo a escribir es alguno del alfabeto de la máquina, y depende del carácter leído y del estado actual.
Desplazar el cabezal una celda a derecha o izquierda (R/L);  en algunos modelos el desplazamiento puede ser nulo (detener H).
Decidir cual será el nuevo estado en función del carácter que se acaba de leer y del estado actual.  Si la tabla de acción no contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su funcionamiento. En principio todas las celdas que no se hayan escrito antes contienen un carácter especial nulo o vacío (que se representa por 0 o #).  La cinta puede contener tantas celdas a derecha e izquierda del cabezal como sean necesarias para el funcionamiento de la máquina.

El cabezal puede moverse a derecha (R) a izquierda (L) de su posición actual, así como leer el contenido de una celda o escribir en ella cualquier carácter de su alfabeto.

Existe un registro de estado que almacena el estado de la máquina.  El número de estados posibles es finito, y no se exige ningún estado especial con el que sea iniciada la máquina. En realidad la máquina de Turing es más una abstracción matemática que un dispositivo físico o mecánico.  El hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren una implementación real muy simple.

Existen diversas "variedades" de una máquina de Turing, pero la más simple puede ser descrita diciendo que es cualquier dispositivo que cumple las siguientes condiciones:

Tiene una cinta sobre la que puede desplazarse a izquierda y derecha, un cabezal de lectura/escritura.  La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo de un conjunto finito;  este conjunto de símbolos se denomina el alfabeto de la máquina.  Jose Doria
Ricardo Jaramillo
Edgar Perez GRACIAS POR:
Full transcript