Turingo mašinos pavertimas korespondencijos problemos (PCP) plytelių rinkiniu apima kelis veiksmus, kurie leidžia mums pateikti Tiuringo mašinos skaičiavimo istoriją naudojant šias plyteles. Šiame paaiškinime apžvelgsime šio proceso detales ir pabrėšime jo didaktinę reikšmę.
PCP yra gerai žinoma neišsprendžiama problema skaičiavimo sudėtingumo teorijoje. Tai apima domino tipo plytelių rinkinį, ant kurių kiekvienoje yra parašytos dvi eilutės, ir kyla klausimas, ar yra plytelių seka, kurią galima išdėstyti tam tikra tvarka taip, kad viršutinių eilučių jungtis atitiktų apatinės stygos.
Norėdami paversti Tiuringo mašiną PCP plytelių rinkiniu, turime atsižvelgti į Turingo mašinos skaičiavimo istoriją. Skaičiavimo istorija fiksuoja būsenų perėjimus ir juostos modifikacijas, įvykusias vykdant Turingo mašiną. Kiekvienas skaičiavimo istorijos žingsnis atitinka Tiuringo mašinos konfigūraciją, kuri apima dabartinę būseną, juostos turinį ir galvos padėtį.
Pirmiausia turime apibrėžti plytelių rinkinį, galintį pavaizduoti Tiuringo mašinos būsenas ir simbolius. Tarkime, kad turime Tiuringo mašiną su būsenų rinkiniu Q ir abėcėlę Σ. Kiekvieną būseną q ∈ Q galime pavaizduoti kaip plytelę su dviem eilutėmis: viena eilutė žymi viršutinę plytelės dalį, o kita eilutė – apatinę plytelės dalį. Panašiai kiekvienas simbolis σ ∈ Σ gali būti pavaizduotas kaip plytelė su dviem eilutėmis.
Toliau turime sukurti plyteles, kurios atspindi būsenos perėjimus ir juostos modifikacijas. Kiekvienam perėjimui δ(q, σ) = (q', σ', D), kur q ir q' yra būsenos, σ ir σ' yra simboliai, o D yra kryptis (kairėn arba dešinėn), sukuriame aibę plytelių. Šios plytelės vaizduoja perėjimą iš būsenos q į būseną q', simbolio σ pakeitimą simboliu σ' ir juostos galvutės judėjimą D kryptimi.
Norėdami pavaizduoti skaičiavimo istoriją, išdėliojame plyteles tokia seka, kuri atitinka Tiuringo mašinos veiksmus. Kiekviena sekos plytelė nurodo Tiuringo mašinos konfigūraciją tam tikrame žingsnyje. Išnagrinėję viršutines plytelių eilutes seka, galime atkurti juostos turinį kiekviename žingsnyje. Panašiai, ištyrę apatines plytelių eilutes, galime atkurti būsenų perėjimus ir juostos modifikacijas.
Pavyzdžiui, panagrinėkime Tiuringo mašiną, kuri padidina dvejetainį skaičių 1. Mašina turi dvi būsenas: q0 ir q1, o abėcėlė susideda iš dviejų simbolių: 0 ir 1. Šią Tiuringo mašiną galime paversti plytelių rinkiniu PCP taip:
– Plytelės, vaizduojančios būsenas:
– 1 plytelė: viršutinė eilutė: q0, apatinė eilutė: q0
– 2 plytelė: viršutinė eilutė: q1, apatinė eilutė: q1
– Plytelės, vaizduojančios simbolius:
– 3 plytelė: viršutinė eilutė: 0, apatinė eilutė: 0
– 4 plytelė: viršutinė eilutė: 1, apatinė eilutė: 1
– Plytelės, vaizduojančios būsenų perėjimus ir juostos modifikacijas:
– 5 plytelė: viršutinė eilutė: q0,0,q1,1,R, apatinė eilutė: q1,1,q0,0,R
Išdėsčius šias plyteles seka, atitinkančia skaičiavimo istoriją, galime pavaizduoti Tiuringo mašinos vykdymą. Pavyzdžiui, jei Tiuringo mašina prasideda nuo juostos turinio „101“, o galvutė iš pradžių yra ant kairiojo krašto simbolio, skaičiavimo istoriją galima pavaizduoti tokia plytelių seka:
1 plytelė, 3 plytelė, 2 plytelė, 4 plytelė, 1 plytelė
Ištyrę viršutines šių plytelių eilutes, kiekviename žingsnyje galime atkurti juostos turinį: „101“, „101“, „101“, „101“, „101“. Panašiai, nagrinėdami apatines eilutes, galime rekonstruoti būsenų perėjimus ir juostos modifikacijas: q0,0,q1,1,R; q1,1,q0,0,R; q0,0,q1,1,R; q1,1,q0,0,R.
Tiuringo mašinos transformavimas į PCP plytelių rinkinį apima Tiuringo mašinos būsenų, simbolių, būsenų perėjimų ir juostos modifikacijų atvaizdavimą naudojant plyteles. Išdėstę šias plyteles seka, galime pavaizduoti Tiuringo mašinos skaičiavimo istoriją. Ši transformacija leidžia mums ištirti PCP savybes ir neapibrėžtumą Turingo mašinų kontekste.
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?
- Jei turime dvi TM, apibūdinančias sprendžiamą kalbą, ar lygiavertiškumo klausimas vis dar neišspręstas?
- 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ų?
Peržiūrėkite daugiau klausimų ir atsakymų „Decidability“.