Rekurzivně spočetný jazyk
Formální jazyk L je rekurzivně spočetný, jestliže pro něj existuje Turingův stroj (dále TS), který všechna slova z tohoto jazyka přijímá (akceptuje). Slova, která nejsou z tohoto jazyka, pak může buď odmítat, nebo se může stroj zacyklit. Tím se liší od rekurzivního jazyka, u kterého TS vždy zastaví (buď akceptuje nebo zamítne, i když mu je dáno slovo z doplňku jazyka). Pokud takový TS M existuje, říkáme, že TS M přijímá jazyk L.
Množina je rekurzivně spočetná právě tehdy, pokud je definičním oborem nějaké ČRF. Také platí, že množina je rekurzivně spočetná právě tehdy, pokud je oborem hodnot nějaké ČRF.
Uzávěrové vlastnosti editovat
Třída rekurzivně spočetných jazyků je uzavřená na sjednocení, průnik, zřetězení a iteraci. To znamená, že pokud jsou některé jazyky rekurzivně spočetné, jsou rekurzivně spočetné i jazyky vzniklé z nich za pomocí výše uvedených operací.
Třída rekurzivně spočetných jazyků není uzavřená na komplement.
Důkaz uzavřenosti sjednocení editovat
Máme-li jazyky L1 a L2, které jsou rekurzivně spočetné, existují i TS M1 a M2, které tyto jazyky přijímají. Sestrojíme-li sjednocení jazyků L1 a L2, vznikne nám nový jazyk Ls. Pro tento nový jazyk musí opět existovat TS, který ho bude přijímat. Nejprve zkusíme použít stejný algoritmus, jaký je použit u rekurzivních jazyků. Sestrojíme TS Ms!, kterým se pokusíme přijmout sjednocený jazyk Ls:
- Simuluj TS M1 pro slovo w. Pokud TS M1 slovo přijme, přijmi slovo. Pokud odmítne, pokračuj dále.
- Simuluj TS M2 pro slovo w. Pokud TS M2 slovo přijme, přijmi slovo. Pokud odmítne, odmítni slovo w.
Nyní vyzkoušíme, jak TS Ms! funguje. Zkusíme do něj vložit slovo ze sjednocení jazyků L1 a L2, přičemž slovo w spadá do jazyka L2, ale nespadá do jazyka L1 – TS M1 se dokonce pro slovo w zacyklí. Postupujme podle algoritmu TS Ms!. Jako první nasimulujeme TS M1 se vstupem w. Jenže M1 se zacyklí a tak se nikdy nedostane ke slovu TS M2, který teprve slovo w přijímá. Jak vidíme, tento TS Ms! nepřijímá sjednocení dvou rekurzivně spočetných jazyků. Musíme zkusit jinou myšlenku.
Podle předpokladu platí, že alespoň jeden TS M1 nebo M2 musí pro slovo w z Ls zastavit a přijmout slovo. My nevíme, který z nich to je a nemůžeme to zkusit sériově, protože by se první TS mohl zacyklit. Namísto toho můžeme zkoušet oba TS M1 i M2 paralelně. Náš nový TS Ms bude simulovat oba TS zároveň a bude se mezi nimi přepínat. Nejdříve provede jeden krok výpočtu M1 a poté jeden krok výpočtu M2. A tak dále, dokud buď alespoň jeden TS nepřijme slovo nebo dokud oba neodmítnou. Pokud jeden odmítne a druhý cyklí, cyklí i náš TS Ms, což nevadí, protože dané slovo zřejmě nebude z jazyka Ls. Popis stroje:
- Simuluj jeden krok výpočtu TS M1. Pokud M1 došel do přijímající stavu, přijmi slovo w.
- Simuluj jeden krok výpočtu TS M2. Pokud M2 došel do přijímající stavu, přijmi slovo w.
- Pokud oba TS odmítají w, odmítni w.
- Vrať se zpět k prvnímu bodu.
Důkaz uzavřenosti průniku editovat
Máme-li jazyky L1 a L2, které jsou rekurzivně spočetné, existují i TS M1 a M2, které tyto jazyky přijímají. Sestrojíme-li průnik jazyků L1 a L2, vznikne nám nový jazyk Lp. Pro tento nový jazyk musí opět existovat TS, který ho bude přijímat. Použijeme stejnou myšlenku, jakou jsme použili u sjednocení. TS Mp, který bude přijímat Lp, bude vypadat takto:
- Simuluj jeden krok výpočtu TS M1. Pokud M1 došel do odmítajícího stavu, odmítni slovo w.
- Simuluj jeden krok výpočtu TS M2. Pokud M2 došel do odmítajícího stavu, odmítni slovo w.
- Pokud oba TS přijímají w, přijmi w.
- Vrať se zpět k prvnímu bodu.
Jednoduchý sériový algoritmus nemůžeme použít proto, že by se první TS mohl opět zacyklit, přičemž druhý TS by mohl slovo zamítnout, čímž by bylo jasné, že slovo do jazyka nepatří.
Komplement editovat
Máme-li rekurzivně spočetný jazyk (dále RSJ) L a jeho komplement L', který je také RSJ, pak jazyky L a L' jsou rekurzivní. Důkaz: pokud je L RSJ, pak existuje TS M, který tento jazyk přijímá. To znamená, že přijme každé slovo z L. Dále máme TS M', které přijme každé slovo z L'. To znamená, že neexistuje slovo, pro které by se TS M nebo M' zacyklil. Jsme tedy schopni sestavit takový TS R, který přijme všechna slova z L a odmítne všechna slova z L' nebo naopak. TS R tudíž rozhoduje jazyk L a ten tak musí být rekurzivní.
Komplementem čistě RSJ (tedy jazyka, který je RSJ, ale není rekurzivní) je vždy jazyk, který není rekurzivně spočetný. Vezměme pro příklad jazyk HALT, který je čistě RSJ, ale jeho komplement (NotHALT) není RSJ. To vyplývá z definice NotHALT: HALT obsahuje dvojice TS:slovo takové, že TS pro dané slovo zastaví. NotHALT tedy obsahuje dvojice TS:slovo takové, kdy daný TS nezastaví pro slovo, že se zacyklí. Protože nejsme schopni identifikovat cyklus, nejsme schopni sestavit TS, který by jazyk NotHALT přijímal. Obecně: pokud máme jazyk L, který je čistě RSJ, pak jeho komplement L' musí obsahovat takové slovo, pro něž se TS M' zacyklí a tudíž tento TS M' nemůže přijímat jazyk L'.