Taijf 61-80

• Maszyny Turinga służą do:
• -akceptacji języków
• -obliczania wartości funkcji
• -rozwiązywania problemów

• -Gramatyki regularne są równoważne automatom skończonym.
• -Gramatyki bezkontekstowe są równoważne niedeterministycznym automatom ze stosem.
• -Gramatyki kontekstowe są równoważne automatom liniowo ograniczonym.
• -Gramatyki nieograniczone są równoważne maszynom Turinga.

Obliczenie jest ciąg kolejnych konfiguracji:

1) Ciąg zaczyna się od konfiguracji początkowej.

2) Każda następna konfiguracja jest otrzymana z poprzedniej przez wykonanie ruchu maszyny (zastosowania funkcji przejścia).

3) Jeżeli dla pewnej konfiguracji zostanie spełniony warunek zakończenia obliczenia to ta konfiguracja jest ostatnim elementem ciągu.

4) W przeciwnym przypadku ten ciąg jest nieskończony.

Obliczenie maszyny Turinga może być skończone lub nieskończone:

1. Jeśli dla dowolnych danych wejściowych obliczenie maszyny Turinga jest skończone, to mówimy, że maszyna ma własność stopu.

2. Jeśli dla pewnych danych wejściowych obliczenie będzie nieskończone, to mówimy, że maszyna jest bez własności stopu.

Konfiguracją Maszyny Turinga (opisem chwilowym) nazywamy ciąg symboli: αqβ

• α - to ciąg symboli taśmy położonych na lewo od głowicy,
• q - stan, w którym aktualnie znajduje się sterowanie
• β - to ciąg symboli taśmy w komórkach począwszy od komórki pod głowicą w
• prawo do ostatniej zawierającej niepusty symbol.

• 1) sterowanie w stanie q0
• 2) głowica w pierwszej komórce taśmy
• 3) dane w początkowych komórkach taśmy

W przypadku gdy maszyna kończy obliczenie, to sterowanie może być w stanie akceptującym lub nieakceptującym.

Jeśli maszyna Turinga akceptuje język, to ten język jest zbiorem wszystkich słów, dla których obliczenie kończy się w stanie akceptującym.

Jeśli słowo nie należy do tego języka to obliczenie kończy się w stanie nieakceptującym lub jest nieskończone.

Maszyną Turinga ze stanem akceptującym z własnością stopu nazywamy system:

• M = (Q, Σ, Γ, δ, q0, B,F= {ACC})
• gdzie poszczególne elementy systemu są określone tak jak w modelu podstawowym

• Ten model różni się od modelu podstawowego:
• - ograniczeniem zbioru stanów akceptujących do jednego ustalonego stanu oznaczonego symbolem ACC,
• - założeniem, że przejście do stanu akceptującego jest równoważne zakończeniu obliczenia.

Jeśli dla dowolnych danych wejściowych obliczenie maszyny Turinga jest skończone, to mówimy, że maszyna ma własność stopu

• Maszyna z własnością stopu dla której wyróżniono dwa stany: jedyny stan akceptujący qA i stan
• nieakceptujący qR:

M = (Q, Σ, Γ, δ, q0, B, {qA}, {qR}, C)

gdzie C to warunek zakończenia obliczenia. Warunek zakończenia obliczenia jest równoważny przejściu do któregoś z tych dwóch stanów.

Maszyną Turinga z wartownikiem nazywamy Maszynę Turinga, która od Maszyny Turinga w Modelu Podstawowym, różni się wyróżnionym symbolem wartownika ¢.

W trakcie obliczenia głowica może znaleźć się nad komórką z wartownikiem. Wówczas jedynym dopuszczalnym ruchem jest (~,¢,R), gdzie ~ jest pewnym stanem.

Konfiguracja początkowa: w pierwszej komórce umieszczony jest symbol wartownika, a dalej dane wejściowe, głowica jest nad 1-szym symbolem danych wejściowych (2-gąd komórką), a sterowanie jest w stanie początkowym.

• Maszyną turinga z taśmą wielościeżkową nazywamy system
• M= (Q, Σ, Γ, δ, q0, B, F) gdzie funkcja przejścia zdefiniowana jest następująco

Stan początkowy: Głowica nad pierwszymi komórkami ścieżek, dane wejściowe zapisane na pierwszej ścieżce. Pozostałe ścieżki wypełnione symbolem pustym.

Dla tego modelu głowica jednocześnie odczytuje symbole ze wszystkich ścieżek i jednocześnie drukuje na wszystkich ścieżkach.

δ : Q × Γk → Q × Γk × {L, R}

Maszyna Turinga z taśmą wielościeżkową jest równoważna Maszynie Turinga w modelu podstawowym (jednościeżkowej)

• Maszyną turinga wielotaśmową nazywamy system
• M= (Q, Σ, Γ^(k), δ, q0, B, F) gdzie funkcja przejścia zdefiniowana jest następująco

δ : Q × Γ^(k) → Q × Γ^(k) × {L, R,S}^(k)

Zakładamy, że taśmy są dwustronnie nieograniczone

• - Dane wejściowe umieszczone są na pierwszej taśmie.
• - Głowica umieszczona jest nad pierwszym od lewej symbolej danych wejściowych.
• - Pozostałe komórki wszystkich taśm wypełnione są symbolem pustym.

Klasa maszyn Turinga wielotaśmowych jest równoważna klasie maszyn Turinga w modelu podstawowym.

• Na podstawie stanu, w którym jest sterowanie oraz symboli czytanych przez głowicę, maszyna wykonuje następującą akcje:
• 1) Każda głowica drukuje pewien symbol alfabetu (niezależnie).
• 2) Sterowanie przechodzi do pewnego stanu.
• 3) Każda głowica przesuwa się w lewo w prawo lub pozostaje w miejscu niezależnie od ruchu pozostałych głowic.

• Definijca maszyny Turinga z taśmą dwustronnie nieograniczoną jest identyczna z definicją maszyny w modelu podstawowym,
• różnica między oboma modelami polega na możliwości przesunięcia głowicy w lewo o dowolną liczbę komórek.

Klasa maszyn Turinga z taśmą dwustronnie nieograniczoną jest równoważna klasie maszyn Turinga w modelu podstawowym.

Taki sam jak Opis chwilowy- konfiguracja maszyny Turnga z tym, że

• α - to ciąg symboli taśmy w komórkach począwszy od pierwszej komórki taśmy położonej najbardziej na lewo i zawierającej symbol różny od symbolu pustego B, a kończąc na komórce poprzedzającej komórkę obserwowaną przez głowicę.
• Jeśli wszystkie komórki na lewo od komórki obserwowanej przez głowicę zawierają symbole puste B, to α jest ciągiem pustym.

• Maszyna Turinga ze stanem akceptującym i odrzucającym to system M = (Q, Σ, Γ, δ, q0, B, {Acc}, {Rej}, C) gdzie:
• Q - skończony zbiór stanów
• Σ - skończony alfabet wejściowy
• Γ - skończony alfabet taśmy
• δ - funkcja przejścia
• q0 - wyróżniony stan nazwany stanem początkowym
• B - wyróżniony symbol alfabetu taśmy zwany symbolem pustym
• {Acc} - zbiór zawierający 1 stan akceptujący
• {Rej} - zbiór zawierający 1 stan odrzucający
• C - warunek zakończenia obliczenia

• q0 ∈ Q
• Acc ∈ Q
• Rej ∈ Q
• B ∈ Γ
• Σ ⊂ Γ − {B}
• δ : Q × Γ → Q × Γ × {L, R}