Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Vlastnosti kladného uzavretia (uzavreté v rámci týchto operácií):
* únia: Ak sú L1 a L2 rozpoznateľné, potom je tiež rozpoznateľná L1 ∪ L2. Môžete simulovať oba Turing stroje pre L1 a L2 paralelne. Ak akceptuje, kombinovaný stroj akceptuje.
* zreťazenie: Ak sú L1 a L2 rozoznateľné, potom je tiež rozpoznateľný L1L2. Je to trochu zložitejšie. Nedeterministicky môžete rozdeliť vstupný reťazec na dve časti a potom spustiť Turing Stromes pre L1 a L2 na týchto častiach. Ak obidve akceptujú, kombinovaný stroj akceptuje.
* kleene hviezda: Ak je L Turingovo rozpoznateľný, L* je tiež rozpoznateľný. Podobne ako v prípade zreťazenia, môžete neterministicky rozdeliť vstupný reťazec na nulu alebo viac častí a otestovať, či je každá časť v L.
* RADSAL: Ak je L Turingovo rozpoznateľný, potom l
Vlastnosti negatívneho uzavretia (pri týchto operáciách nie sú uzavreté):
* priesečník: Turing-rozpoznateľné jazyky nie sú * uzavreté pri križovatke. To znamená, že ak sú L1 a L2 rozpoznateľné, L1 ∩ L2 nie je * nevyhnutne * rozpoznateľný. Ak sú však*L1 aj L2 Turing-*Decidable*, potom je L1 ∩ L2 dec.
* Doplnok: Turing-rozpoznateľné jazyky nie sú * uzavreté v rámci doplnku. Ak je L oboznámiteľný, ¬L (doplnok L) nie je nevyhnutne * rozpoznateľný.
* Jazyk L je during dec. (Rekurzívny), ak a iba vtedy, ak sú obidve L a ¬L rozpoznateľné (rekurzívne spomenuté). Toto je zásadné spojenie medzi rozpoznateľnými a rozhodujúcimi sa jazykmi.
v súhrne:
| Operácia | ZATVORENÉ? | Vysvetlenie
| --------------- | --------- | ----------------------------------------------------------------------------------------------------------------------
| Únia | Áno | Simulujte oba stroje paralelne, akceptujte, ak akceptuje. |
| Zreťazenie Áno | Deterministicky rozdelený vstup a testujte každú časť. |
| Kleene hviezda Áno | Deterministicky rozdelenie vstupu do viacerých častí a otestujte každú časť. |
| Zvrátenie | Áno | Zmeňte vstup a spustite TM. |
| Križovatka Nie | Môže zlyhať. Vyžaduje, aby boli oba jazyky rozhodujúce pre uzavretie. |
| Doplnok Nie | Doplnok zužiteľného jazyka nie je vždy rozpoznateľný. |
Prečo nie sú križovatka a komplementácia uzavreté?
Tento problém vyplýva zo skutočnosti, že Turing Stroje pre rozpoznávané jazyky môžu navždy slučku.
* priesečník: Ak jeden zo strojov slučky na konkrétnom vstupe, kombinovaný počítač by tiež mohol slučku, aj keď by druhý stroj nakoniec odmietol (čo znamená, že vstup nie je * na križovatke). Potrebujete spôsob, ako poznať *, kedy * prestať čakať na stroj, ktorý by mohol navždy opakovať.
* Doplnok: Turingový stroj pre L buď prijíma, odmieta alebo slučky pri vstupe. Aby ste rozpoznali doplnok ¬L, musíte * odmietnuť * všetky reťazce akceptované l a * akceptovať * všetky reťazce odmietnuté * alebo slučené na * L. nemôžete spoľahlivo rozlišovať medzi strojom, ktorý * bude * nakoniec odmietnu a ten, ktorý bude navždy slučka. Museli by ste byť schopní nejako vedieť *, keď * stroj chystá slučka, čo je vo všeobecnosti nemožné.
Príklad demonštrujúci nezakúvanie v rámci komplementácie:
Zvážte problém s zastavením, ktorý je rozpoznateľný (Turingov stroj môže simulovať iný Turingov stroj a akceptovať, ak sa zastaví). Doplnok problému s zastavením je * nie * rozpoznateľný. Keby to tak bolo, potom by problém zastavenia bol dec. (Pretože problém zastavenia, ako aj jeho doplnok by boli rozpoznateľné), čo vieme, že je nepravdivý.