22 - Turingovy stroje (jazyky přijímané TS, varianty TS, lineárně omezené automaty, univerzální TS)

Question 1

Formální definice TS

Answer 1

Turingův stroj je 6-tice M=(Q, Σ, Γ, δ, q₀, qF)
• Q – konečná množina stavů
• Σ – konečná vstupní abeceda, Δ ∉ Σ
• Γ – konečná pásková abeceda, Σ ⊂ Γ, Δ ∈ Γ
• δ – parciální přechodová funkce, δ: (Q{q_F })×Γ→Q×Γ∪{L, R}, kde L, R∉Γ
○ a∈Γ - zápis symbolu a na pásku, L - posun hlavy doleva, R - posun hlavy doprava

• q_0  – počáteční stav, q₀ ∈ Q
• q_F  – koncový stav, q_F  ∈ Q
	○ Podle Wikipedie může být i množina koncových stavů F⊆Q.

Jestli má stroj více pásek, nebo je nedeterministický nijak nezvětšuje jeho schopnost přijímat jazyky!

Alternativní definice TS
• je povoleno více koncových stavů
• místo jednoho koncového stavu zavedeny stavy accept a reject
• na prvním políčku pásky je napevno zapsán symbol konce pásky
• operace přepis a posun jsou spojeny do jedné operace
• a další

Question 2

TS - funkce, konfigurace, výpočet a přijímaný jazyk

Answer 2

Funkce Turingova stroje
1. Přečte symbol pod hlavou
2. Dle přečteného symbolu a aktuálního stavu je provedena změna stavu a provedena akce:
○ přepíše symbol jiným symbolem
○ posune se o jednu pozici doleva nebo doprava

Konfigurace pásky
• Nekonečný řetezec s obsahem pásky a aktuální pozice hlavy (prvek z {γΔ^ω∣γ∈Γ^* }×N)
• zapisujeme: aΔb▁a bcΔ… (podtržení značí pozici)

Konfigurace TS = trojce (stavRidJednotky,obsahPasky,cisloBunkyKdeJeHlava)
• Stav řídící jednotky + konfigurace pásky (prvek z Q×{γΔ^ω∣γ∈Γ^* }×N)

Krok výpočtu TS (⊢) = Přechod od jedné konfigurace TS k jiné
Výpočet TS = Posloupnost konfigurací

Typy výpočtů
• nekonečný
• Konečný (s koncovou konfigurací (q, γ, n) a rozlišujeme dva typy zastavení:)
○ normální (přechod do koncového stavu) - automat přijme
○ abnormální (posun mimo pásky, nedefinovaná žádná přechodová funkce pro aktuální konfiguraci) - automat nepřijme
- stroj se zasekne
● pro daný stav a symbol není definován přechod
● hlava je na nejlevější pozici pásky a dojde k posunu doleva

Přijímání zvláštní konfigurací pásky (ukončení výpočtu po přehodu do konfigurace ∆w∆ω na∆Y∆…,kdeY ∈Γ−Σ)

Question 3

Jazyky přijímané TS

Answer 3

Množina všech řetězců v obsahu pásky ve vstupní konfiguraci pro které TS normálně zastaví.

• Úplný Turingův stroj (vždy zastaví) ⇔ rekurzivní jazyk
• Turingův stroj ⇔ rekurzivně vyčíslitelný jazyk (Jazyky přijímané TS odpovídají typu 0 Chomského hierarchie - TS přijímající rekurzivně vyčíslitelný jazyk zastaví pro všechna slova z L, ale pro ostatní slova se může zaseknout, nebo donekonečna cyklit.)

Speciálním případem TS jsou linárně omezené automaty (LOA), je to vlastně TS ale s konečnou páskou, a dokáží přijímat kontextové jazyky.

Question 4

Varianty TS

Answer 4

TS zastavující se zapsáním výsledku na pásku = TS po rozhodnutí výsledku smaže obsah pásky a výsledek (ACCEPT nebo REJECT) zapíše v nějaké podobě na pásku

Vícepáskové TS
• TS nepoužívá pouze jednu pásku a hlavu, ale více pásek (každá s vlastní hlavou)
• TS přečte symboly na všech páskách, provede operaci (na každé pásce může jinou) a změní řídící stav
• Je ekvivalentní jednopáskovému TS (stav více pásek lze zakódovat i na jednu pásku)
Zvětšení paměťových možností TS jeho výpočetní možnosti nerozšiřuje.

Úplný TS = TS, který pro každý vstup zastaví (neskončí v nekonečném cyklu) -> Přijímá rekurzivní jazyky

Nedeterministické TS (NTS)
• V každém kroku vybírá z konečného počtu možností
• přechodová funkce má tvar: (Q∖{q_F })×Γ→2^(Q×(Γ∪{L,R}))
• ekvivalentní deterministickému TS (deterministický TS proste postupně vyzkouší všechny možnosti)
Zavedení nedeterminismu nezvětšuje výpočetní schopnosti TS (ale může výrazně zlepšit časovou složitost výpočtu)

Lineárně omezený automat (LOA) - Nedeterministický TS, který nikdy neopustí část pásky na které je zapsán jeho vstup (páska má konečnou velikost) -> Přijímají jazyky typu 1 Chomského hierarchie (kontextové jazyky)

Deterministický lineárně omezený automat - Deterministický TS, který nikdy neopustí část pásky na které je zapsán jeho vstup (páska má konečnou velikost) - Není známo zda je striktně slabší než nedeterministický LOA.

Question 5

Univerzální TS

Answer 5

• zavádí koncept programovatelného stroje - TS, který simuluje běh jiného TS
  
  • na vstupní pásce jsou umístěna data i program (program je nějakým způsobem zakódovaný TS, který chceme simulovat)
  • může být implementován jako 3-páskový TS (vstup/výstup, simulace pásky daného TS, stav daného TS).

Question 6

Alternativy TS

Answer 6

Existuje celá řada výpočetních modelů, které svojí výpočetní silou odpovídají TS
• Zásobníkový automat s alespoň dvěma zásobníky
• λ-kalkul (Lambda kalkul je teoretickým základem funkcionálního programování. Každý výraz popisuje funkci jednoho argumentu, který je sám funkcí jednoho argumentu, a jejímž výsledkem je opět funkce jednoho argumentu.)
• Parciální rekurzivní funkce
• automaty s frontou
• automaty s 2 a více čítači

Question 7

Churchova-Turingova teze

Answer 7

Turingovy stroje a jim ekvivalentní systémy definují svojí výpočetní silou to, co intuitivně považujeme za efektivně vyčíslitelné (vypočitatelné v konečném čase)
○ (nelze to ale formálně dokázat)
○ známe i jiné výpočetní systémy s odpovídající silou - lambda kalkul, parciálně rekurzivní funkce, DEVS systémy, …
• Není znám žádný výpočetní proces, který bychom označili za efektivně vyčíslitelný a který by nebylo možné realizovat na Turingově stroji.

Question 8

Turingův stroj ekvivalence s parciálně rekurz. funkcí

Answer 8

“Parametry funkce můžeme hodit na pásku TS a odělit pomocí Δ. Pokud po provedení výpočtu bude na pásce výsledek funkce pro tyto parametry, TS přijme. Pokud není pro dané parametry funkce definována, TS cyklí.”

Hlavně tam půjde o to, že se ten důkaz dělá jako platnost dvou podmnožin (A ⊆ B ∧ B ⊆ A). Tj. ukázat algoritmus, jak jakýkoliv TS převedeš na par. rek. fci a potom ukázat algoritmus, jak jakoukoliv p. r. fci převedeš na TS (u státnic bych čekal, že musíš říct, že je potřeba dokázat oba směry a pak by se tě možná náhodně zeptali na jeden)