Maquinas de turing

Maquinas de Turing
Definiciones Básicas
Como ya sabemos, existen varios tipos de dispositivos para el reconocimiento de lenguajes, por ejemplo, los autómatas, en este caso se explicará en quéconsiste y a que nos referimos con máquinas de Turing.
Las máquinas de Turing son más generales que los autómatas ya sean finitos o de pila, ya que éstas son capaces de reconocer lenguajes regulares,lenguajes independientes del contexto (también llamados lenguajes libres del contexto) y muchos otros tipos de lenguajes. Las máquinas de Turing resultan muy similares a los dos tipos de autómatasmencionados con respecto a la acción que realizan y a sus componentes.
Una máquina de Turing es una 7-tupla M= (Q, Σ, Γ, s, b, F, δ), donde:
Q es un conjunto finito de estados
Σ es el alfabeto de entradaΓ es un alfabeto llamado alfabeto de la cinta
s Є Q es el estado inicial
b Є Γ es el símbolo blanco (y no está en Σ)
F ⊆ Q es el conjunto de estados finales
δ: Q × Γ → Q × Γ × {L,R} es unafunción parcial llamada función de transición
En la definición anterior, el valor inicial de todas las celdas de la cinta de la máquina de Turing es el símbolo b. La definición requiere que b ∉ Σ.Máquinas de Turing Universales
La máquina de Turing universal es aquella que, a partir de una descripción adecuada de una máquina de Turing M y una cadena de entrada w, simula el comportamiento de M sobre lacadena w.
De otra manera, podemos decir que una máquina de Turing universal, abreviada MTU, es una máquina con tres cintas, de las cuales:
* En la primera de ellas se coloca la codificación deuna máquina de Turing M.
* En la segunda, la codificación de M, w.
* En la tercera, la codificación de q1.
Siendo así, la máquina de Turing concatena el contenido de la tercera cinta con loque se encuentre en la segunda (hasta el primer símbolo de w), por último busca en la primera cinta la subcadena obtenida debido a la concatenación y la transición (δ) aplicable. Una vez...