August 20th, 2010

bebras

Tiuringinė metarekursija praktikoje

Straipsnis su visais komentarais perkeltas į http://rokiskis.popo.lt/2010/08/20/tiuringine-metarekursija-praktikoje/

Panašu, kad nuo teorijos apie metateorijas reiktų truputį šoktelt link praktikos. Nes kaip bebūtų, man kažkodėl nesinori eiti link sudėtingesnės semiotikos dalies, nepraknaisiojus bazinės dalies, bent jau tos, kuri yra pagrindžiama formaliais metodais, t.y., per matematinį aparatą.

Kaip jau matėme iš tos teorijos apie metateorijas ir poros klausimų apie metateorijų tarpusavio santykius, pilnumą ir santykį tarp metakalbos ir natūralių kalbų, natūralioji kalba mažų mažiausiai gali būti panaudota, kaip metakalba visų matematinių teorijų aprašymui ir, sprendžiant iš Derida darbų, gali turėti net ir didesnį gilumą, t.y., ją naudojant, galima aprašyti Universalią Tiuringo Mašiną (UTM), tačiau naudojant UTM, nebūtinai galima, o gal būt ir negalima pilnai aprašyti natūralios kalbos. Pakankamai griežto pagrindimo, kuris būtų priimtinas matematikams, gal ir nėra, tačiau visgi daugybinė interpretacija kelia problemas.

Taigi, panagrinėkim nedidelį praktinį pavyzdį - tiesiog kompiuterį. Kaip žinia, kiekvienas mums įprastas kompiuteris yra pilnavertė UTM, kaip ir kiekviena programavimo kalba. Ir štai pavyzdys: koks nors Pentium grupės procesorius išties turi RISC branduolį, kuris emuliuoja i386 tipo CISC architektūrą, naudojant mikrokodą ir kai kurias aparatines priemones. T.y., viena Tiuringo mašina sukasi ant kitos. Jau ant tos emuliuojamos architektūros gali suktis kokia nors virtualių mašinų sistema. Ant šios - gali suktis kokia nors Java, ant kurios - vėl koks nors i386 emuliatorius, ant kurio - vėl kokia nors OS, virtualios mašinos, kita Java, ant kurios dar kas nors ir t.t., ir t.t. - kitaip tariant, turime krūvą kalbinių sluoksnių - kiekvienas su tam tikromis sintaksinės, semantinės ir pragmatinės analizės priemonėmis..

Iš matematinės pusės - viskas tvarkoje. Bet tiktai tol, kol visa ta daugiasluoksnė interpretatorių sistema nepradedama optimizuoti. Įsivaizduokime, kad, pvz., tiesiog turime Java mašiną, kuri sukasi ant kitos Java mašinos ir norime pagreitinti visą reikalą. Žinoma, paprasčiausias būdas - tai perkelti visas antrosios Java mašinos funkcijas į pirmąją ir antrosios programą vykdyti pirmojoje atskirai, tik pažymėtą, kaip emuliuojamą. Viskas labai gražu, kol neužduodi klausimo: o kaip nustatyti, ar emuliacija yra pilna, ar tik virtuali?

Kitaip tariant, klausimas gali būti suformuluotas ir kitaip: ar teksto/programos interpretatorius gali nustatyti, kad jo interpretacija yra pirminė, t.y., neįtakojama fundamentalesnių interpretacijų nustatomų apribojimų ar dėsnių? Galime įtarti, kad ne, nes įmanoma emuliacija, kuri neleidžia to nustatyti. Bet ar tai galioja praktiniams atvejams, t.y., ar pvz., gyvoji kalba gali būti emuliuojama taip, kad negalėtų nustatyti savo emuliavimo?

Dabar neprisimenu nei autoriaus, nei pavadinimo... Kadaise, prieš daugybę metų, buvo pakliuvusi į nagus nuostabi fantastinė knyga apie tai, kaip kažkokiame ateities pasaulyje iš kažkur atsirado virusinė kalba, ėmusi valdyti žmones. Autorius, kiek atsimenu, labai neblogai buvo susipažinęs su teoriniais semiotikos pagrindais. Ir nagrinėjo būtent panašų atvejį žmogaus galvoje. Žinoma, interpretacija buvo fantastinė, hipotetinė ir t.t., tačiau įdomi: o kas, jei tiesiog pasąmonė masto kita kalba, turi kitą prasmių, reikšmių ir ženklų sistemą?

Gerai, dar truputis iš formaliosios pusės: tie, kas giliau domėjosi senosios kartos virusais (tais, kurie plito dar DOS sistemoje), atsimena tokią virusų klasę, kaip polimorfikai. Tai buvo absoliučiai genialios programėlės, kurios generuodavo pačios save. Per kiekvieną tokio viruso pasidauginimą gaudavosi vis kitas kodas, kurio negalėdavo identifikuoti joks antivirusas pagal jokį šabloną - programa keisdavosi tiesiog neatpažįstamai, keisdama netgi ne tik pačią save, bet ir savo pačios generatorių. Ar tik neprimena tai natūraliųjų kalbų, kurios irgi nuolat keičiasi, mutuoja ir pasižymi išskirtiniu polimorfizmu visais požiūriais - ir semantiniu, ir pragmatiniu, ir sintaksiniu? Klausimas vėl: kaip atrasti tam tikrą pirminę struktūrą, jei ji išvis yra?