Taijf 81-100

• Dla akceptacji języków, po zakończeniu obliczeń maszyny akceptujące są w następującej konfiguracji:
• - Głowica znajduje się nad pierwszą komorką taśmy
• - Wszystkie komórki wypełnione są symbolem pustym

• Dla obliczania wartości funkcji:
• - Głowica znajduje się na początku taśmy
• - Wynik zapisany jest w pierwszych komórkach, a pozostałe komórki wypełnione są symbolem pustym.

Klasa maszyn Turinga niedeterministycznych jest równoważna klasie maszyn Turinga deterministycznych. Jest to równoważność w sensie akceptowanych języków, obliczanych funkcji, rozwiązywanych problemów.

Definicja jest analogiczna do Maszyny Turinga w modelu podstawowym z tym, że funkcja przejścia zdefiniowana jest następująco

• δ : Q × Γ→∪k=0∞ (Q × Γ× {L, R})k
• k=0 maszyna zaczyna wykonywać nieskończone obliczenia
• k=2 maszyna wykonuje dwa ruchy

Zatem ruch tej maszyny polega na niedeterministycznym wyborze jednej z wartości funkcji przejścia a następnie wykonaniu ruchu takiego, który prowadzi do akceptacji wejścia.

Stopniem niedeterminizmu jest maksymalna liczba możliwych ruchów dla danej konfiguracji,

Powiemy, że maszyna akceptuje słowo wejściowe (oblicza wartość funkcji) wtedy i tylko wtedy, gdy pewna ścieżka obliczeń kończy się konfiguracją końcową, a stanem sterowania konfiguracji końcowej jest stan akceptujący. Językiem akceptowanym przez maszynę Turinga niedeterministyczną nazywamy zbiór słów akceptowanych przez tę maszynę

• Obliczenie niedeterministycznej maszyny Turinga jest drzewem w którym:
• - korzeń etykietowany jest opisem chwilowym konfiguracji początkowej
• - wierzchołki etykietowane są opisem chwilowym maszyny
• - potomkami dowolnego wierzchołka są wierzchołki pozostające z nim w relacji ruchu

Powiemy, że niedeterministyczna maszyna Turinga kończy obliczenie wtedy i tylko wtedy, gdy w drzewie obliczenie istnieje ścieżka kończąca się konfiguracją końcową

Relacją ruchu |- niedeterministycznej maszyny Turinga będziemy nazywać relację binarną nad zbiorem opisów chwilowych maszyny taką, że dwa opisy chwilowe α1 i α2 są w relacji ruchu wtedy i tylko wtedy, gdy opis chwilowy α2 może być otrzymany przez zastosowanie jednej z wartości funkcji przejścia dla argumentów określonych opisem chwilowym α1.

Maszyna niedeterministyczna będzie akceptować słowo <=> gdy w drzewie będzie istniał liść, którego stan będzie stanem akcteptującym

Maszyny z własnością stopu są podklasą maszyn deterministycznych i niedeterministycznych

Automaty liniowo ograniczone są to Maszyny Turinga z własnością stopu, które prowadzą obliczenia na części taśmy o długości równej wielokrotności słowa wejściowego. Dodatkowo maszyna ta musi być jednotaśmowa

Automaty liniowo ograniczone akceptują klasę języków kontekstowych. To znaczy, że są równoważne klasie gramatyk kontekstowych.

Klasa języków akceptowanych przez automaty liniowe ograniczone zawiera się w klasie języków akceptowanych przez maszyny Turinga z własnością stopu

Klasa maszyn Turinga akceptuje klasę języków rekurencyjnie przeliczalnych to znaczy, że są równoważne gramatykom nieograniczonym.

Automatem ze stosem nazywamy system

M= (Q, Σ, Γ, δ, q0, |-, F)

• Σ- skończony alfabet taśmy
• Γ- skończony alfabet stosu
• gdzie |- jest dnem stosu a funkcja przejścia zdefiniowana jest następująco

δ : Q × {Σ ∪ {ε} } × Γ → Uk=0∞ (Q × Γ*)k

Automat ze stosem jest Maszyną Turinga, to znaczy można skonstruować Maszyne Turinga równoważną automatowi ze stosem

Językiem akceptowanym przez automat ze stosem nazywamy zbiór słów nad alfabetem ∑, dla których istnieje ścieżka w drzewie obliczenia kończąca się konfiguracją końcową zawierającą stan akceptujący.

• Obliczenie automatu że stosem jest drzewem w którym:
• - korzeń etykietowany jest opisem chwilowym
• konfiguracji początkowej automatu.
• - wierzchołki etykietowane są opisem chwilowym automatu.
• - potomkami dowolnego wierzchołka są wierzchołki pozostające z nim w relacji ruchu |-.

Relacją ruchu automatu ze stosem nazywamy relację binarną nad zbiorem opisów chwilowych, gdzie |- jest symbolem tej relacji. Dwa opisy chwilowe są w relacji ruchu wtedy i tylko wtedy, gdy drugi z nich został otrzymany z pierwszego przez wykonanie ruchu automatu.

• Dla stanu sterowania q, symbolu wejściowego a (albo bez uwzględnienia wejścia, jeśli argumentem jest słowo puste) oraz symbolu wierzchołka stosu Z, automat ze stosu wykonuje następujące akcje:
• - jeśli wartością argumentu jest symbol wejściowy przeczytany przez głowicę czytającą, to głowica jest przesuwana nad następny symbol wejścia
• - jeśli wartością argumentu jest słowo puste, to głowica nie czyta symbolu wejściowego i nie jest przesuwana nad następny symbol wejścia
• - Zastępuje wierzchołek stosu symbolem γ z wartości funkcji przejścia, symbole słowa γ są umieszczane na stosie w kolejności od ostatniego do pierwszego, tak że po wykonaniu tej akcji na wierzchołku stosu jest dostępny symbol słowa γ. Jeżeli wierzchołkiem był symbol początku stosu, wtedy pierwszym symbolem słowa γ musi być ten symbol.
• - sterowanie przechodzi do stanu opisanego wartością funkcji przejścia