Máquina de Turing: modelo estándar, componentes y configuración instantánea

Apuntes

Introducci ́on a la Teor ́ıa de la Computaci ́on I Semestre 2022 Profesor: Rodrigo De Castro K. Cap ́ıtulo 5 M ́aquinas de Turing 5.1. El modelo est ́andar de M ́aquina de Turing Una m ́aquina de Turing (MT), M = (Q, q0, F, Σ, Γ, δ), consta de seis componentes: 1. Q es el conjunto (finito) de estados internos de la unidad de control. 2. q0 ∈ Q es el estado inicial. 3. F es el conjunto de estados finales o de aceptaci ́on, ∅̸ = F ⊆ Q. 4. Σ es el alfabeto de entrada. 5. Γ es el alfabeto de cinta, que incluye a Σ, es decir, Σ ⊆ Γ. Los s ́ımbolos de Γ que no hacen parte de Σ (o sea, los s ́ımbolos en Γ − Σ) se utilizan como s ́ımbolos auxiliares. 6. δ es la funci ́on de transici ́on de la m ́aquina: δ : Q × (Γ ∪ {□}) −→ Q × (Γ ∪ {□}) × {←, →, −}. δ es una funci ́on parcial, es decir, puede no estar definida en algunos elementos del dominio. El s ́ımbolo □ no hace parte del alfabeto de cinta Γ sino que es un s ́ımbolo “externo” que representa una casilla en blanco. Por simplicidad, Γ∪{□} se denotar ́a como Γ□. Una m ́aquina de Turing M lee cadenas de entrada u ∈ Σ ∗ colocadas sobre una cinta infinita en ambas direcciones. Una entrada u se coloca en una porci ́on cualquiera de la cinta y...