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

Máquina de Turing

No description
by

Ivan Alfredo Gomez

on 31 March 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Máquina de Turing

Máquina de Turing
Lenguajes aceptados por una maquina Turing
Aceptan lenguajes formales que pueden ser generados por una gramática de tipo 0: recursivamente innumerable. Las maquinas de Turing son los reconocedores de lenguaje más poderosos que existen.

Lenguajes regulares: las gramáticas (de tipo 3) formales definen un lenguaje describiendo como se pueden generar las cadenas del lenguaje… Las gramáticas regulares (aquellos reconocidos por un autómata finito). Son las gramáticas más restrictivas. El lado derecho de una producción debe contener un símbolo Terminal y como máximo un símbolo no Terminal.
¿QUE ES UNA MAQUINA DE TURING?
Una máquina de Turing es un “dispositivo” como lo eran los autómatas finitos o los autómatas a pila, con más capacidades que éstos.

Dispone también de un número finito de estados, uno de ellos inicial, y algunos de ellos finales. Dispone también de una cinta, que es una sucesión “doblemente infinita” de “celdas”, en cada una de las cuales hay un símbolo.

La cinta está inicialmente “en blanco” salvo en una porción finita, en la que está almacenada la entrada. La máquina de Turing puede leer y escribir símbolos en la cinta, y moverse a lo largo de ella en ambos sentidos. Para ello dispone de una cabeza de lectura-escritura. Su operación viene determinada por su función de transición.
Ejemplos de aplicación de las MT
Ejemplo del Funcionamiento: se construye una MT que acepte el lenguaje L={a^i b^i c^i:i≥0}, sobre Σ={a,b,c}.


1. Se cambia la “a” por una X y se mueve hacia la derecha pasando por encima de todas las “a” e “Y”, hasta llegar a la primera “b”, cambia la primera “b” por una Y, se mueve a la derecha pasando por encima de las “b” y “Z”, y luego encuentra la primera “c” y la cambia por “Z” y se mueve a la izquierda.

2. Luego se mueve a la izquierda pasando por encima de “b”, “Y”, “a”, hasta encontrar la “X”, la reemplaza por una “X” y repite el proceso anterior, cuando la máquina reemplaza la cadena “X”, “Y” y “Z” reconoce la cadena vacía y busca el estado de aceptación.


Máquinas de Turing Deterministas y no Deterministas
La entrada de una máquina de Turing viene determinada por el estado actual y el símbolo leído, un par [estado, símbolo], siendo el cambio de estado, la escritura de un nuevo símbolo y el movimiento las acciones a tomar en función de una entrada. En el caso de que para cada par estado y símbolo posible exista a lo sumo una posibilidad de ejecución, se dirá que es una máquina de Turing determinista, mientras que en el caso de que exista al menos un par [estado, símbolo] con más de una posible combinación de actuaciones se dirá que se trata de una máquina de Turing no determinista.
Alan Turing
(1912-1954)
fue un matemático, lógico, científico de la computación, criptógrafo y filósofo británico.

Es considerado uno de los padres de la ciencia de la computación siendo el precursor de la informática moderna. Proporcionó una influyente formalización de los conceptos de algoritmo y computación: la máquina de Turing. Formuló su propia versión de la hoy ampliamente aceptada Tesis de Church-Turing.



Alan Turing
Comprobación de la aceptación de la cadena w = aabbcc:
Otra de las capacidades importantes es la de generar lenguajes, tarea en la

MT M=(Q,Σ,Γ,q_0,T,B,δ)

Cual los estados finales son necesarios. Concretamente una MT genera un lenguaje LΣ^* si:

M comienza a operar con la cinta en blanco en el estado inicial “q0”.

Cada vez que M retorna al estado inicial “q0”, hay una cadena uL escrita sobre la cinta.

Todas las cadenas de L son, eventualmente, generadas por M.

El siguiente MT genera cadenas con un numero par de “a” sobre Σ={a}
MT como generadoras de lenguaje
EQUIPO:

Ivan Alfredo Gomez Mendez
Ulises Osorio Perez
Emmanuel Campos Ramirez
Ulises Osorio Perez
Jesus manuel diaz ceballos ayala
Carlos Alfonso Esparza Martinez
Full transcript