17 - Turingovy stroje
pátek 13. května 2016
10:26
Turingovy stroje (jazyky přijímané TS, varianty TS, lineárně omezené automaty, univerzální TS).
Turingův stroj (TS)
Turingův stroj se skládá z
řídící jednotky s konečným počtem stavů (konečná série pravidel)
jednosměrně neohraničená páska
čtecí/zapisovací hlava pracující s páskou
Funkce Turingova stroje
Přečte symbol pod hlavou
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
Prázdný (blank) symbol Δ
Nachází se na buňkách pásky na které dosud nebylo nic zapsáno.
Konfigurace pásky
Nekonečný řetezec s obsahem pásky a aktuální pozice hlavy (prvek z 𝛾Δ𝜔𝛾∈Γ*×ℕ)
zapisujeme: 𝑎Δ𝑏𝑎𝑏𝑐Δ… (podtržení značí pozici)
Konfigurace TS
Stav řídící jednotky + konfigurace pásky (prvek z 𝑄×𝛾Δ𝜔𝛾∈Γ*×ℕ)
Tedy je to trojce (𝑠𝑡𝑎𝑣𝑅𝑖𝑑𝐽𝑒𝑑𝑛𝑜𝑡𝑘𝑦,𝑜𝑏𝑠𝑎ℎ𝑃𝑎𝑠𝑘𝑦,𝑐𝑖𝑠𝑙𝑜𝐵𝑢𝑛𝑘𝑦𝐾𝑑𝑒𝐽𝑒𝐻𝑙𝑎𝑣𝑎)
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ý
normální (přechod do koncového stavu)
abnormální (posun mimo pásky, nedefinovaná žádná přechodová funkce pro aktuální konfiguraci)
𝑄 – konečná množina stavů
𝛴 – konečná vstupní abeceda, Δ ∉ Σ
𝛤 – konečná pásková abeceda, Σ ⊂ Γ, Δ ∈ Γ
𝑎∈Γ - zápis symbolu 𝑎 na pásku, 𝐿 - posun hlavy doleva, 𝑅 - posun hlavy doprava
𝑞0 – počáteční stav, q₀ ∈ Q
𝑞𝐹 – koncový stav, 𝑞𝐹 ∈ 𝑄
Podle Wikipedie může být i množina koncových stavů 𝐹⊆𝑄.
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ší
Grafická prezentace
stavy značíme stejně jako u konečného automatu
přechody značíme šipkou mezi stavy s popiskem 𝑥/𝑠 (x-co se čte z pásky, s - prováděná operace - zápis/L/R)
Jazyky přijímané TS
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
Důkaz L(TS) = L0:
Sestrojí se gramatika na základě TS s pravidly:
Počáteční stav: S -> [qf blank w blank]
Prodlužování a zkracování pásky: 
Pravidla odpovídající přechodům:
Sestrojí se TS na základě gramatiky:
Použivají se 2 pásky:
Na první je zapsaný vstupní řetězec w
Na druhé se TS pokouší simulovat použití přepisovacích pravidel a dostat se k w
Při simulaci si TS nedeterministicky uhodne jaké pravidlo má zvolit. 
Pokud se obsah 1. pásky rovná obsahu 2. pásky, tak přejde do stavu qf a řetězec přijímá.
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.
Varianty TS
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
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.
Nedeterministické TS (NTS)
V každém kroku vybírá z konečného počtu možností
přechodová funkce má tvar: 𝑸∖𝒒𝑭×𝚪→𝟐𝑸×(𝚪∪{𝑳,𝑹})
ekvivalentní deterministickému TS (deterministický TS proste postupně vyzkouší všechny možnosti)
Např. 3 páskový TS, na 1. pásce je vstupní řetězec, na 2. je pracovní páska, kde se simulují přechody. Na 3. je zakódovaná posloupnost přechodů.
Pokud se zjistí, že daná posloupnost přechodů nevede k cíli, tak se 2. páska znovu inicializuje z první, obmění se sekvence pravidel na 3. pásce a znovu se simuluje
Zavedení nedeterminismu nezvětšuje výpočetní schopnosti TS (ale může výrazně zlepšit časovou složitost výpočtu)
TS, který pro každý vstup zastaví (neskončí v nekonečném cyklu)
Přijímá rekurzivní jazyky
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.
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).
Alternativy TS
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.)
automaty s frontou
automaty s 2 a více čítači
Churchova-Turingova teze
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)
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.
Notes
1. Otazka (predmet) (okruh): Turingovy stroje (jazyky přijímané TS, varianty TS, lineárně omezené automaty, univerzální TS).
Kdo me primarne zkousel: prof. Holub
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Za tie 4 minúty som stihol akorát na tabuľu zadefinovať TS a jeho prechodovú funkciu, konfiguráciu TS a reťazec prijmaný TS a zazvonil budík. prof. Holub sa ma potom opýtal na zastavenia TS (normálne a abnormálne). Varianty TS (NTS, DTS, úplný, LOA). Aké jazyky to príjmá.. niečo k univerzálnemu TS. A nakoniec či by sa dal TS skonštruovať z súčiastok dostupných na VUT (na čo som povedal že až na nekonečnú pásku áno).
From <[link]> 
1. Otazka (predmet) (okruh): TIN - Turingovy stroje
Kdo me primarne zkousel: Janoušek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Krásná otázka, říkám si pohoda. Sednu na bobek a po minutě budík a já v hlavě nenašel jednu jedinou myšlenku. Tak jsem začal definicí Turingova stroje, samozřejmě jsem úplně zasklil koncový stav, no po chvilce jsem se oklepal, omluvil a jal se definovat přechodovou funkci, ve které jsem udělal ještě jednu krpu a taky se opravil. Mozek měl fakt nějakej blok nebo nevím... Napsal jsem pak definici pro nedeterministický TS (už vpohodě) a Janoušek se zeptat na srovnání výpočetní síly (stejná) -> dokaž to. Tak jsem zmínil vícepáskový TS a simulaci pomocí 3 pásek. Tady chtěl přesně pospat jak to funguje (zapisuju si posloupnosti pravidel/přechodů, nejprve délky 1, pak 2). Chvilku to ze mě tahal. Jednoduchá otázka, ale já měl prostě blok... nakonec za D.
From <[link]> 
1. Otazka (predmet) (okruh): Turingovy stroje - jazyky přijímané TS, varianty TS
Kdo me primarne zkousel: Hrubý Martin
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Měl jsem začít neformálně: co to je ten Turingův stroj, k čemu se používá. Jaké znám druhy turingova stroje. Dostali jsme se až k vyčíslitelnostem u Turingových strojů. Byl jsem trochu nervozní a neodpovídal jsem moc formálně. Vedlo se to duchem diskuze. Nakonec to bylo celkem příjemné zkoušení.
C
From <[link]> 
1. Otazka (předmět) (okruh): Turingovy stroje (TIN)
Kdo me primarne zkousel: Holub ?
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Snažil jsem se tam popsat ten TS. Pak jsem se minutu snažil napsat přechodovou funkci. Pak se jsme začali mluvit o tom kdy TS zastaví a kdy příjme. Dostal jsem se do stavu kdy se zeptal "Je pro vás zastavení a přijetí ta samá věc?" Věděl jsem, že ne, ale nedokázal jsem si vybavit proč. Až po skončení mě napadlo abnormální zastavení a cyklení. Pak přišly otázky na lineárně omezený TS. Pak se do toho vložil Meduna? a zeptal se na existenci nevyčíslitených jazyků. Ale to bylo dávno po limitu.
From <[link]> 
1. Otazka (předmět) (okruh): 17. Turingovy stroje.
Kdo me primarne zkousel: Křivka Zbyněk, Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal jsem obecnou definicí, ale napsal jsem blbě tu přechodovou funkci, sám jsem si toho všiml, a řekl jsem to, že mi to nějak nesedí, tak mi řekl, ať napíšu relaci přechodu a konfiguraci, což mě krásně navedlo, u toho jsem si uvědomil kde je chyba a opravil jsem to. Dále se ptal na NTS a DTS a nějaké další varianty... řekl jsem qaccept, qreject, potom jsem se zmínil o LOA, a univerzálním TS, zmínil jsem se i o vícepáskových strojích, definoval přijímaný jazyk a bylo. Zkrátka dobrá otázka... za A.
From <[link]> 
1. Otazka TIN (Turingovy stroje):
Kdo me primarne zkousel: Češka Milan, prof. RNDr., CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Otázka byla konkretizována na univerzální TS. Prof. Češka řekl, že s touto otázkou můžeme být rychle hotoví. Chtěl napsat definici TS, což jsem zvládl, ale v tom stresu jsem zapomněl na počáteční stav. Pak chtěl přechodovou funkci, kterou jsem taky napsal neúplnou. Důležité bylo, že jsem přemýšlel nahlas a on mě doplňujícími otázkami nakonec dovedl ke správné odpovědi. U úplného TS jsem se už chytil a zodpovídal na všechny dotazy správně. Výsledně C.
From <[link]> 
2. Otazka (předmět) (okruh): Turingovy stroje
Kdo me primarne zkousel: Janoušek 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Z pocatku sem mel totalni okno, nastesti rekl ze chce slyset jake sou varianty TS, povede sem. Pak napsat funkci prechodu, vysvetlit jak urcime ze NTS prijma jazyk (v tom sem se zamotal, ve vysledku chtel slyset jak teda probiha probiha simulace NTS pomoci DTS). Byl ale uplne vklidu, kdyz sem nevedel co mysli tak otazku preformuloval, nehrotil, takze i prez momentalni vypadek sem ze sebe neco vypotil. Vysledek A.
From <[link]> 
1. Otazka (okruh): Turingovy stroje (byla u toho poznamka: zamereni na vycislitelnost)
Kdo me primarne zkousel: Pouze a jen dr. Hruby
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Rovnou se chopil slova a rekl, co by chtel slyset. Byl to rozhovor otazka-odpoved, nenechal me mluvit samotneho (coz mi vyhovovalo). Ptal se na vycislitelnost, definici TS (poloformalne, neveril mi ze TS je sestice, ale pak z toho vyplynulo ze chtel slyset, ze krome formalni n-tice ma ten stroj jeste cosi jako pasku a cteci hlavu:-). Dost jsem pletl terminy, ale vzdycky me na to upozornil a nejak jsem to zvladl opravit. Nebyl vubec zlej. Dal mi B.
From <[link]> 
1. Otazka (předmět) (okruh): 17. Turingovy stroje
Kdo me primarne zkousel: Janoušek Vladimír, doc. Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Chtěl jsem začít popisem co je TS tak me hned zastavil ze veri ze toto znam a zacal se ptat, chtel abych napsal prechodovou funkci, pak se zeptal na dalsi varianty rekl sem k-paskovy tak chtel jen slovne rict jak by vypadala prechodova funkce, to same u nedeterministickeho a pak jak bych tyto dva simuloval pomoci deterministickeho. Pak se zeptal jestli bych popsal v obrysech dukaz ekvivalnce TS a parcialne rekurzivnich funkci, neco sem vypotil ale pochopil ze to nepujde tak to neresil, pak jen jake jazyky to prijima a naky priklad ktery to umi aspon castecne rozhodnout a naky ktery je nerozhodnutelny. Uplna pohoda ptal se ja odpovidal, pohodovy pokec.
From <[link]> 
1. Otazka (předmět) (okruh): Turingovy stroje (TIN) (17)
Kdo me primarne zkousel: Meduna Alexander, prof. RNDr., CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Dostali jsme se jen na definici plus nějaké doplňkové otázky (jako
hlavní principiální rozdíl oproti konečným automatům).
Určitě znal spousty variací, ale asi nevěděl, kterou přesně
jsme se učili jako základní, takže jsme se u přechodového zobrazení
museli společně ujednodit.
Navíc jsem omylem místo dvojtečky napsal podmnožinu (začal jsem
totiž původně trochu jinak, než jsem pak pokračoval), čehož si
všiml a vzápětí jsem to spravil.
From <[link]> 
2. Otazka (okruh): Turingovy stroje
Kdo me primarne zkousel: Meduna
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Rekl, ze to chce neformalne a chce videt, ze tomu rozumim. Rekl sem, co to je, popsal sem tu sestici, prechodovou funkci, pak se ptal co je na te pasce a co se s ni da delat, pak jak ten stroj prijima, jak je to s determinismem/netedeterminismem a v cem se TS lisi od KA. Chtel slyset, ze ten stroj muze cyklit donekonecna a nikdy nemusi zastavit. Opet byl velice mily a nic nechtel dopodrobna.
U obou otazek bezely stopky, po 4 minutach uz oba meli pouze doplnujici drobne otazky. Celkove to slo hladce jak po masle - nad moje ocekavani.
From <[link]> 