Prečo je predpoklad existencie rozhodcu pre prázdny jazykový problém v rozpore s konštrukciou rozhodcu pre problém akceptácie?
Predpokladu existencie rozhodcu pre prázdny jazykový problém odporuje konštrukcia rozhodcu pre akceptačný problém v oblasti teórie výpočtovej zložitosti. Aby sme pochopili, prečo je tento predpoklad v rozpore, je dôležité zvážiť povahu týchto dvoch problémov a ich vzťah k Turingovým strojom.
Turingov stroj (TM) je teoretický model výpočtu, ktorý pozostáva z pásky rozdelenej na bunky, čítacej/zapisovacej hlavy a riadiacej jednotky. Riadiaca jednotka pohybuje hlavou po páske, číta symbol na aktuálnej bunke a na základe sady preddefinovaných pravidiel určí ďalšiu akciu, ktorú treba vykonať. TM môže byť reprezentovaná ako diagram prechodu stavu, kde každý stav zodpovedá inej konfigurácii stroja.
Akceptačný problém pre TM je definovaný nasledovne: Ak je daný TM M a vstupný reťazec w, akceptuje M w? Inými slovami, chceme určiť, či M, keď sa spustí na vstupe w, nakoniec vstúpi do akceptujúceho stavu. Tento problém je rozhoditeľný, pretože preň môžeme skonštruovať rozhodovacie zariadenie. Rozhodujúci je TM, ktorý sa zastaví a dá správnu odpoveď pre každý vstup.
Na druhej strane je problém s prázdnym jazykom pre TM definovaný nasledovne: Pri TM M akceptuje M nejaký reťazec? Inými slovami, chceme zistiť, či existuje aspoň jeden vstupný reťazec, ktorý M akceptuje. Tento problém je nerozhodnuteľný, to znamená, že preň nemôže existovať žiadny rozhodujúci subjekt.
Aby sme dokázali nerozhodnuteľnosť prázdneho jazykového problému, môžeme použiť techniku nazývanú diagonalizácia. Predpokladajme kvôli rozporu, že existuje rozhodujúci faktor D pre prázdny jazykový problém. Potom môžeme skonštruovať novú TM N, ktorá vezme svoj vlastný popis ako vstup a simuluje D na tomto popise. Ak D akceptuje popis N, potom N odmietne jeho vstup; inak N akceptuje svoj vstup. Teraz uvažujme, čo sa stane, keď N dostane svoj vlastný popis ako vstup. Ak N akceptuje svoj vstup, potom podľa svojej konštrukcie by mal svoj vstup odmietnuť. Naopak, ak N odmietne svoj vstup, potom podľa svojej konštrukcie by mal svoj vstup prijať. Vzniká tak rozpor, ktorý dokazuje, že predpoklad existencie rozhodcu pre prázdny jazykový problém je nesprávny.
Predpokladu existencie rozhodcu pre prázdny jazykový problém je v rozpore s konštrukciou rozhodcu pre akceptačný problém. Problém akceptácie je rozhoditeľný, keďže preň môžeme skonštruovať rozhodovací prvok, zatiaľ čo problém s prázdnym jazykom je nerozhodný, keďže preň nemôže existovať žiadny rozhodujúci.
Ďalšie nedávne otázky a odpovede týkajúce sa Rozhodovateľnosť:
- Môže byť páska obmedzená na veľkosť vstupu (čo je ekvivalentné tomu, že hlava Turingovho stroja je obmedzená tak, aby sa pohybovala za vstupom pásky TM)?
- Čo to znamená, že rôzne variácie Turingových strojov sú ekvivalentné vo výpočtovej schopnosti?
- Môže Turingov rozpoznateľný jazyk tvoriť podmnožinu rozhoditeľného jazyka?
- Je problém zastavenia Turingovho stroja rozhodnutý?
- Ak máme dve PP, ktoré opisujú rozhoditeľný jazyk, je otázka ekvivalencie stále nerozhodnutá?
- Ako sa problém akceptácie pre lineárne ohraničené automaty líši od problému Turingových strojov?
- Uveďte príklad problému, ktorý môže vyriešiť lineárny ohraničený automat.
- Vysvetlite pojem rozhodnuteľnosť v kontexte lineárne ohraničených automatov.
- Ako ovplyvňuje veľkosť pásky v lineárne ohraničených automatoch počet rôznych konfigurácií?
- Aký je hlavný rozdiel medzi lineárne ohraničenými automatmi a Turingovými strojmi?
Pozrite si ďalšie otázky a odpovede v časti Rozhodnuteľnosť