Rekurzivní a rekurzivně spočetné jazyky. Turingovy stroje. Pojem nerozhodnutelnosti a částečné rozhodnutelnosti.

Definice

Jazyk nazýváme

• rekurzivně spočetný ⇔ L = L(M) pro nějaký Turnigův stroj M
• rekurzivní ⇔ L = L(M) pro nějaký úplný Turnigův stroj M

Ke každému rekurzivnímu jazyku L existuje Turingův stroj, který ho rozhoduje, tj. výpočet na každém vstupním slovu je konečný. Rekurzivně spočetný jazyk musí splňovat slabší podmínku: musí pro něj existovat Turingův stroj, který ho akceptuje, tj. akceptuje každé slovo z L, ale výpočet na slovu nepatřícím do L může být bud’ zamítající, nebo nekonečný.
Mezi rekurzivní jazyky patří regulární, bezkontextové, kontextové jazyky a další jazyky, které splňují podmínku rekurzivního jazyka. Každý rekurzivní jazyk je i rekurzivně spočetný (opačně to neplatí). Rekurzivně spočetné jazyky se dají generovat gramatikami typu 0. Metodou diagonalizace se dá dokázat, že existuje jazyk, který není rekurzivně spočetný.

S rekurzivními a rekurzivně spočetnými množinami úzce souvisí rozhodnutelné, nerozhodnutelné a částečně rozhodnutelné problémy:

Věta

Třídy rekurzivních a rekurzivně spočetných jazyků jsou uzavřeny vzhledem k operacím

Důkaz pro sjednocení

Necht’ L1, L2 jsou jazyky akceptovány Turingovými stroji M1,M2 a mají disjunktní množiny stavů. Nedeterministický stroj M∪, akceptující L1∪L2, dostaneme sjednocením strojů M1 a M2. Stroj M∪ bude mít navíc nový počáteční stav a v prvním kroku výpočtu stroj M∪ nedeterministicky přejde bud’ do požátežního stavu stroje M1, nebo do počátečního stavu stroje M2. V druhém kroku simuluje výpočet zvoleného stroje.

Důkaz pro průnik

Stroj M∩, akceptující L1∩L2, bude mít pásku se třemi stopami. Na první stopě je zapsán vstupní řetěz a její obsah se v průběhu výpočtu nemění. Stroj M∩ okopíruje svůj vstup w na druhou stopu a na ní simuluje výpočet M1 na w. V případě, že M1 akceptoval, okopíruje vstup w na třetí stopu a na ní pak simuluje výpočet M2 na w. Jestliže M2 akceptoval, pak M∩ též akceptuje. Jinak zamítá.

Nedeterministický stroj M∗, akceptující L₁^∗, je zobecněním stroje M·.

Důkaz pro komplement

Necht’ L je jazyk akceptovaný úplným deterministickým Turingovym strojem TM. Stroj co–M, akceptující jazyk co–L, získáme tak, že všude v definici přechodové funkce δ zaměníme navzájem akceptující stav q_accept a zamítající stav q_reject . Protože M je úplný, bude i co–M úplný.

Důsledkem Postovy věty je, že třída rekurzivně spočetných jazyků není uzavřená na komplement. Pokud by platil opak, třídy rekurzivních a rekurzivně spočetných jazyků by se rovnaly.

Definice

Turingův stroj (TM) je 9-tice kde:

• je konečná množina stavů

• je konečná množina vstupních symbolů

• je konečná množina páskových (pracovních) symbolů, obsahující jako svou podmnožinu abecedu

• je levá koncová značka

• je symbol označující prázdne políčko

• je totální přechodová funkce

• je počáteční stav

• je akceptující stav

• je zamietající stav

Turingův stroj má konečnou množinu stavů Q, pásku, která je rozdělena na jednotlivá políčka, a hlavu, která se může po pásce pohybovat doleva a doprava, číst a zapisovat symboly. Na každém políčku pásky je zapsán právě jeden z konečně mnoha páskových (pracovních) symbolů. Páska je jednosměrně nekonečná. Na nejlevějším (nultém) políčku je zapsán speciální symbol , označující levý konec pásky. Na začátku výpočtu je na prvním až n-tém, n ≥ 0, políčku pásky zapsán vstupní řetěz (vstupem tedy může být i prázdný řetěz). Ostatních nekonečně mnoho políček napravo od vstupu je prázdných — tuto skutečnost vyjádříme pomocí speciálního znaku . Výpočet začíná v počátečním stavu q0, přičemž hlava snímá nulté políčko obsahující levou koncovou značku . Krok výpočtu spočívá v tom, že stroj v závislosti na momentálním stavu a symbolu snímaném hlavou

1. změní svůj stav (či přesněji může změnit),
2. zapíše symbol na políčko snímané hlavou (čímž přepíše symbol, který tam byl zapsán předtím) a
3. posune hlavu o jedno políčko doprava, nebo doleva.

Způsob, jakým se má změnit stav, přepsat symbol a posunout hlava, předepisuje přechodová funkce δ. Stroj akceptuje vstupní řetěz, právě když přejde do speciálního akceptujícího stavu q_accept. Stroj zamítá právě když přejde do speciálního zamítajícího stavu q_reject. Na některých vstupech může výpočet běžet nekonečně dlouho, aniž by stroj vstupní slovo akceptoval, nebo zamítnul. V takovém případě říkáme, že stroj pro daný vstup cyklí.
Navíc požadujeme, aby Turingův stroj nikdy nepřepsal levou koncovou značku jiným symbolem a aby nikdy neposunul svou hlavu vlevo od políčka obsahujícího levou koncovou značku. Formálně, požadujeme aby pro každé existoval stav takový, že:

Problém, kdy se má určit, zda řetěz w má vlastnost P, nazýváme:

• rozhodnutelný právě když množina všech řetězů majících vlastnost P je rekursivní, tj. existuje úplný Turingův stroj M, který akceptuje každý řetěz mající vlastnost P a zamítne každý řetěz, který tuto vlastnost nemá (M rozhoduje jazyk obsahující právě všechna ta slova, která mají vlastnost P);

• nerozhodnutelný právˇe když není rozhodnutelný;

• částečně rozhodnutelný (semirozhodnutelný) právě když množina všech řetězů majících vlastnost P je rekursivně spoěetná, tj. existuje Turingův stroj, který akceptuje každý řetěz mající vlastnost P (a zamítá anebo cyklí pro řetěz nemající vlastnost P).

Namísto ”problém určit, zda řetěz w má vlastnost P je rozhodnutelný (částečně rozhodnutelný)“ zkráceně říkáme, že vlastnost P je rozhodnutelná resp. že problém P je rozhodnutelný (částečně rozhodnutelný). Ačkoli vlastnost rekursivní resp. rekursivně spočetný vypovídá o množinách, zatímco rozhodnutelnost resp. semirozhodnutelnost je vlastnost problémů, jsou oba pojmy úzce spjaty.

Platí mezi nimi tato ekvivalence:
P je rozhodnutelný ⇔ jazyk {w | w má vlastnost P} je rekursivní
L je rekursivní ⇔ problém ”w?∈L“ je rozhodnutelný
P je semirozhodnutelný ⇔ jazyk {w | w má vlastnost P} je rekursivně spočetný
L je rekursivně spočetný ⇔ problém ”w?∈L“ je semirozhodnutelný

IB102 Automaty a gramatiky
IB005 Formální jazyky a automaty

Marek Menšík UČO 255679
Nevím přesně, kdo otázky zpracoval přede mnou, pouze jsem je sem umístil, doplnil chybějící věci a opravil nepřesnosti. Připomínám, že věci zde uvedené nemusí být korektní a zatím neprošly kontrolou žádného z profesorů. Z mé strany je tato otázka dokončena a případné chybějící věci a chyby mě můžete napsat na UČO mail nebo se registrujte a upravte je sami.

Z mě strany prozatím hotovo
Možná by se u nerozhodnutelných problémů dalo doplnit více věcí jako Postův korespondenční problém, diagonalizace a jiné.