Aké sú vlastnosti uzávierky rozpoznateľných jazykov Turing?

Turing-rozpoznateľné jazyky, známe tiež ako rekurzívne vymeniteľné jazyky, majú nasledujúce vlastnosti uzavretia:

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 r (Zvrátenie L) je tiež rozpoznateľné. Turingový stroj môže ľahko zvrátiť vstupný reťazec a potom spustiť Turingov stroj pre L na obrátenom reťazci.

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ý.

• Predchádzajúca strana: Aké sú výhody používania n v programovacích jazykoch? 
• Ďalšia strana: Aké sú vlastnosti uzávierky rozhodných jazykov?