Лекция 12 Flashcards
(15 cards)
Машина на Тюринг
Абстрактен автомат с безкрайна лента, върху която чете, пише и се движи наляво или надясно.
Дефиниция 2
Детерминистична машина на Тюринг е осморка M = ⟨Q,Σ,Γ, δ, t, qstart, qaccept, qreject⟩.
Конфигурация на Тюрингова машина
Подредена тройка (α, q, β), където q ∈ Q, α ∈ Γ*, β ∈ Γ+ – съдържание на лентата и текущо състояние.
Начална конфигурация
(ε, qstart, αt), където α е входната дума.
Приемаща конфигурация
(β, qaccept, γ).
Отхвърляща конфигурация
(β, qreject, γ).
Релация `M
Конфигурационна стъпка, базирана на δ(q,x) = (q′,y,d) и движение на главата.
Релации ``M и `?M
Рефлексивно и транзитивно затваряне на `M, определящо достижимост за даден брой стъпки.
Приемане на дума α
Ако (ε, qstart, αt) `?M (λ, qaccept, ρ).
Отхвърляне на дума α
Ако (ε, qstart, αt) `?M (λ, qreject, ρ).
Зацикляне върху α
Ако не достига заключително състояние – безкрайно изчисление.
Дефиниция 3
Език L е полуразрешим, ако съществува машина на Тюринг M, такава че L = L(M).
Разрешител (тотална машина)
Машина, която винаги спира (в qaccept или qreject) за всеки вход.
Дефиниция 4
Език L е разрешим, ако съществува разрешител M с L = L(M).
Многолентова машина на Тюринг
Вариант с k ленти, всяка с независима глава, и δ : Q′ × Γ^k → Q × Γ^k × {C,B,S}^k.
