Maquina de Turing Funcionamiento

August 12th, 2010 Categoria Lenguajes formales, Maquina de Turing

Maquina de TuringDescripcion de la maquina de Turing.

La idea de la maquina funcion con un Cabeza de Lectura y Escritura que lee una cinta infinita.

Cada vez que lee, borrar el contenido anterior, escribe un nuevo contenido, para luego Avanzar un lugar hacia la izquierda o Derecha.

Con esta maquina se puede realizar cualquier computo de las maquinas computadoras actuales

La maquina de Turing puede considerarse un automata capaz de leer lenguajes formales (es un conjunto de palabras (Palabras son cadenas de caracteres) de longitud finita que se forman a partir de un alfabeto (_Conjunto de caracteres) finito.

Definicion de una maquina de Turing de una sola cinta :una 6- tuplaM=(Q, \Gamma, s, b, F, \delta)\,,

  • Q \, es un conjunto finito de estados.
  • \Gamma \, El alafabeto de la cinta, un conjunto finito de símbolos de cinta
  • s \in Q Estado Incial.
  • b \in \Gamma Ssímbolo denominado blanco.
  • F \subseteq Q es el conjunto de estados finales de aceptación.
  • \delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}\, función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.
Tags: , ,
This entry was posted on Thursday, August 12th, 2010 at 7:58 pm and is filed under Lenguajes formales, Maquina de Turing. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

You must be logged in to post a comment.