Jei turime dvi TM, apibūdinančias sprendžiamą kalbą, ar lygiavertiškumo klausimas vis dar neišspręstas?
Skaičiavimo sudėtingumo teorijos srityje sprendžiamumo sąvoka atlieka esminį vaidmenį. Sakoma, kad kalba yra sprendžiama, jei egzistuoja Tiuringo mašina (TM), kuri gali nustatyti, ar bet kuri įvestis priklauso kalbai, ar ne. Kalbos sprendžiamumas yra svarbi savybė, nes ji leidžia mums algoritmiškai samprotauti apie kalbą ir jos savybes.
Tiuringo mašinų lygiavertiškumo klausimas yra susijęs su nustatymu, ar du tam tikri TM atpažįsta tą pačią kalbą. Formaliai, atsižvelgiant į du TM M1 ir M2, lygiavertiškumo klausimas klausia, ar L(M1) = L(M2), kur L(M) reiškia kalbą, kurią atpažįsta TM M.
Yra žinoma, kad bendra dviejų TM lygiavertiškumo nustatymo problema yra neišspręsta. Tai reiškia, kad nėra algoritmo, kuris visada galėtų nuspręsti, ar dvi savavališkos TM atpažįsta tą pačią kalbą, ar ne. Šį rezultatą įrodė Alanas Turingas savo pagrindiniame darbe apie apskaičiuojamumą.
Tačiau svarbu pažymėti, kad šis rezultatas galioja bendram savavališkų TM atveju. Konkrečiu atveju, kai abi TM apibūdina sprendžiamas kalbas, lygiavertiškumo klausimas tampa sprendžiamas. Taip yra todėl, kad sprendžiamos kalbos yra tos, kurioms yra TM, galinti nuspręsti dėl narystės kalba. Todėl, jei dvi TM aprašo sprendžiamas kalbas, galime sukurti naują TM, kuri nusprendžia jų lygiavertiškumą.
Norėdami tai iliustruoti, panagrinėkime pavyzdį. Tarkime, kad turime dvi TM M1 ir M2, kurios apibūdina sprendžiamas kalbas. Galime sukurti naują TM M, kuris nusprendžia jų lygiavertiškumą taip:
1. Jei yra įvestis x, vienu metu imituokite M1 ant x ir M2 ant x.
2. Jei M1 priima x, o M2 priima x, tada priimkite.
3. Jei M1 atmeta x, o M2 atmeta x, tada priimkite.
4. Priešingu atveju atmeskite.
Pagal konstrukciją TM M priims įvestį x tada ir tik tada, kai ir M1, ir M2 priima x, arba abu M1 ir M2 atmeta x. Tai reiškia, kad M nustato M1 ir M2 atitiktį bet kuriai įvesties x.
Nors bendra dviejų savavališkų TM lygiavertiškumo nustatymo problema yra neišspręsta, jei TM aprašo sprendžiamas kalbas, lygiavertiškumo klausimas tampa sprendžiamas. Taip yra todėl, kad TM gali nuspręsti dėl sprendžiamų kalbų, todėl galime sukurti TM, kuris nusprendžia jų lygiavertiškumą. Ekvivalentiškumo klausimo sprendžiamumas TM, apibūdinantis sprendžiamas kalbas, suteikia svarbių įžvalgų apie šių kalbų skaičiavimo sudėtingumą.
Kiti naujausi klausimai ir atsakymai apie Sprendžiamumas:
- Ar juosta gali būti apribota įvesties dydžiu (tai atitinka tiūringo mašinos galvutės apribojimą, kad jis judėtų už TM juostos įvesties)?
- Ką reiškia, kad skirtingi Turingo mašinų variantai yra lygiaverčiai skaičiavimo galimybėmis?
- Ar turinti atpažįstama kalba gali sudaryti sprendžiamos kalbos poaibį?
- Ar Tiuringo mašinos stabdymo problemą galima išspręsti?
- Kuo linijinių ribojimų automatų priėmimo problema skiriasi nuo Tiuringo mašinų?
- Pateikite problemos, kurią gali išspręsti tiesinės ribos automatas, pavyzdį.
- Paaiškinkite sprendžiamumo sąvoką tiesinės ribos automatų kontekste.
- Kaip juostos dydis linijiniuose automatuose įtakoja skirtingų konfigūracijų skaičių?
- Koks yra pagrindinis skirtumas tarp tiesinės ribos automatų ir Tiuringo mašinų?
- Apibūdinkite Turingo mašinos pavertimo PCP plytelių rinkiniu procesą ir kaip šios plytelės atspindi skaičiavimo istoriją.
Peržiūrėkite daugiau klausimų ir atsakymų „Decidability“.