Kolmogorovo DI alfa ir omega

„Žmonija man visad atrodė kaip aibė klaidžiojančių rūke švieselių, kurios tik silpnai tejaučia kitų skeidžiamą spindesį. Tačiau jos sujungtos aiškių šviesių gijų tinklu, kiekvina jų viena, dviem, trimis, ... kryptimis. Ir tokių proveržių rūke link kitos švieselės susidarymą protinga pavadinti stebuklu“,
A.N. Kolmogorovas, iš rinkinio „Kolmogorovas ir kibernetika“, 2001 (rus.)

Mokykloje kai kuriems senesnės kartos (ypač rusų) atstovams yea tekę algebros vingrybes krimsti iš A. Kolmogorovo redaguoto vadovėlio. Tačiau ar kas žinojo, kad labai „prie ko“ ir Viduramžių dirbtiniai homunkulai, ir A. Azimovo robotai, ir šiuolaikiniai mokslinės fantastikos biorobotai. Mat ir A. Kolmogorovas buvo greta dirbtinio intelekto ištakų, 1964 m. pareiškęs: „Principinė pilnaverčių dirbtinių gyvų būtybių, sukonstruotų iš diskrečių, skaitmeninių informacijos apdorojimo ir valdymo mechanismų, sukūrimo galimybė neprieštarauja materialistinės dialektikos principams“.

Visų pirma jis buvo genialiu matematiku, kurio mokiniu buvo ir J. Kubilius. Tačiau jis pasižymėjo neįtikėtina mokslinių interesų gausa. Ir jis nemažai nuveikė ir kibernetikos srityje; su juo siejamos tokios sąvokos kaip algoritmas, automatas, atsitiktinumas, entropija, informacija, sudėtingumas... pirmiausia tai Kolmogorovo-Uspenskio algoritmai, labai artimi mašinoms su keičiama atmintimi. Jų atmintį galima struktūriškai perkonfigūruoti, suvedant informacijos apdorojimą prie atminties elementų būsenų ir ryšių tarp jų. Kolmogorovo algoritmų teorijos pagrindine sąvoka tapo atskiro objekto entropija (objekto sudėtingumas). Tai minimalus informacijos kiekis, būtinas objekto atstatymui (apibrėžta 1962-65 m.). AI

Ar galima sukurti dirbtinę mąstančią būtybę? Bulgakovo „Šuns širdyje“ prof. Preobraženskis : „Prašau, paaiškinkite man, kam reikia dirbtinai fabrikuoti Spinozą, kai bet kuri boba gali jį pagimdyti kada panorus?“
Taigi, užduotis kita. Ne panašią, o pranašesnę, kad būtų žingsnis pirmyn, kitas evoliucijos etapas. Juk kai kūrė automobilį, nesiekė mechaniškai atgaminti arklį, - su visais vidaus organais ir refleksais, ir kad ji temptų tokį pat vežimą.

Bet ar gali žmogaus protas sukurti „didesnį už savo protą“? Ar tai neprimena barono Miunhauzeno pastangų ištraukti save iš pelkės suėmus save už plaukų?

Pirmoji kibernetikos entuziastų karta to nepastebėjo, tačiau netrukus paaiškėjo, kad kalbėti galima tik apie kažkokio „embriono sukūrimą“; o tasai jau vėliau imtų vystytis ir tobulėti, t.y. tai, ką S. Lemas pavadino „protingumo slenksčiu“, kurio nepasiekusi, sistema negali vystytis toliau. Tai panašu į grandininę branduolinę reakciją, kuri nevyksta žemiau kritinės masės.

Kaip pavyzdį paimkim šachmatus – sritis, kurioje mašina pradėjo aplošinėti čempionus. Tai akivaizdu – programos nuolat tobulėja, o žmonės lieka tokiais pat. 7-8 dešimtm. ESM (tuo metu žodis „kompiuteris“ dar nebuvo prigijęs TSRS) mokymas žaisti šachmatais buvo madoje. Tai buvo poligonas kompiuterio galimybių tyrinėjimui. Programoms buvo bendra tai, kad jos buvo euristinėmis. Esmę bendrais bruožais galima apibūdinti taip: euristiniai algorinmai tenkinasi nepilnai optimaliais sprendimais, t.y. „atrodančiais artimais optimaliems“, dažnai remiantis intuityviais samprotavimais. Bet argi taip nesielgia kiekvienas mūsų?

1997 m. „Deep Blue“ įveikė G. Kasparovą (apie tai žr. >>>>>), o vėliau šachmatų programos dar tobulėjo. 2016 m. „Stockfish“ reitingas buvo 3341, kai to meto stipriausio šachmatininko M. Karlseno tik 2850.

Aišku, intuityvi dalis privalėjo būti kažkaip formalizuota. Šachmatuose dažnai pavykdavo kokybės kaina stipriai sumažinti uždavinio sudėtingumą, t.y., programos parinkti ėjimai nebuvo geriausiais, tačiau buvo laikomi tokiais dėl apytikslio veiksnių įvertinimo. Ir kilo klausimas: ar gali ESM savo greitaveikos dėka žaisti be klaidų? Juk šachmatai priklauso vadinamųjų žaidimų su pilna informacija grupei, kuriai neklaidingos strategijos buvimas griežtai įrodytas. Tokią strategiją galima surasti per baigtinį ėjimų skaičių – tik šachmatams tas pasirodė esąs nepasiekiama kartele, apie 1016, t.y., tai tuo metu buvo įveikiama tik milijardui greičiausių kompiuterių per milijardą metų.

Bet argi tokios jau svarbios euristinės idėjos taikomos vienam stalo žaidimui. Apie tai Edgaras Po pastebėjo: „Šachmatuose, kur figūros nelygiavertėsir kur joms priskirti įvairiausi ir keisčiausi ėjimai, sudėtingumas (kaip dažnai būna) klaidingai painiojamas su gilumu. Tuo tarpu čia viską sprendžia dėmesys. Tereikia jam susilpnėti ir padarote klaidą, vedančią prie apsiskaičiavimo ar pralaimėjimo. O kadangi šachmatuose ėjimai ne tik įvairūs, bet ir daugiareikšmiai, tai šansai suklysti didėja; ir 9 atvejais iš 10 laimi ne gabesnis, o labiau susikaupęs žmogus. Kas kita šaškės, kur ėjimai vienodi. Tai gryna intelektualų dvikova. Nesant kitų galimybių, analitikas stengiasi pranikti į varžovo mintis, save įsivaizduodamas jo vietoje“.

Dirbtinė gyvybė ... skamba kažkaip nejaukiai, šokiruojančiai. Tačiau terminą (A-life) 1987 m. seminare Los Abamoje, skirtame gyvybės sintezei ir modeliavimui, įvedė Kristoferis Lengtonas1). Bet dar 7-o dešimtm. pradžioje anglų matematikas Džonas Konvėjus skelbė darbus apie vadinamuosius ląstelinius automatus (žr. >>>>>); jų aktyvią ir pasyvias būsenas jis greičiau poetiškai nei formaliai siejo su „gyvenimu“ ir „mirtimi“, o vėliau jau minėjo ir „gimimą“ bei „išgyvenimą“, kai aprašinėjo perėjimus tarp būsenų.

Bet ir Konvėjus nebuvo pirmuoju – supratimo apie „dirbtinę gyvybę“ pradininku reikia laikyti A. Kolmogorovą. 1961 m. balandį MGU mechmato seminare jis skaitė pranešimą „Automatai ir gyvybė“, kuriame jis kėlė klausimus: ar galima sukurti būtybę, kuri ne tik daugintųsi, bet ir evoliucionuotų? ar ji gali mąstyti, turėti laisvą valią, emocijas? Ir atsakė: „Jei tos ar kitos sistemos savybė ‚būti gyva‘ ar ‚mąstyti‘ bus apibrėžta grynai funkcionaliai (pvz., bet kuri sistema su kuria galima aptarti šiuolaikinio mokslo ir literatūros klausimus, būtų laikoma mąstančia), tai teks prpažinti iš principo pilnai įmanomą dirbtinių gyvų ir mąstančių būtybių sukūrimą. [ ... ] Gyvybės reiškinių analizėje svarbi ne begalinio dialektika, o didumo dialektika. Didesnio skaičiaus elementų grynai aritmetinė kombinacija sukurs ir nenutrūkstamumą, ir naujas savybes. Gamtamoksliniame griežtumo lygmenyje įmanomas tikslus tokių sąvokų kaip mąstymas, valia, emocijos apibrėžimas“.

Dirbtinės gyvybės klausimas papildo dirbtinio intelekto klausimą. Čia prisiminkime dialogą iš vieno fantastinio romano:

- O ką, tikro dirbtinio proto pas jus dar nesukūrė?
- Sukūrė, nelaimei. Tikras protas laisvas, būtų jis mašininis ar kitoks. Kai į jį įvedami dirbtiniai apribojimai, jis liaujasi būti protu, kad ir kaip sparčiai apdorotų informaciją. 0 kas žino iš anksto, ką sumanys protinga, t.y. laisva mašina? Štai kai kurios ir primąstė... Algondo planeta sudeginta iki pagrindų, daugeliui kitų planetų irgi kliuvo... Buvo ir taip – protingo kompiuterio valdomas žvaigždėlėkis atidengė ugnį į mokslinių tyrimų stotį ir ją sunaikino... Toli gražu ne visos buvo tokios, bet juk ir mes ne visi mąstom vienodai, tačiau... nuo tada tokių kompiuterių gamyba kategoriškai uždrausta, ir net teoriniai tyrinėjimai ta linkme – sunkus nusikaltimas.

Vienu svarbiausių žmogaus proto kriterijų – efektyvus nepilnos, prieštaringos, netikslios informacijos apdorojimas. A. Kolmogorovas dar 1925 m. atkreipė dėmesį į dalies logikos dėsnių sąlyginumą, pvz., „trečio negalimumo“ (tertium non datur), t.y., kad turint du teiginiai, kurių vienas neigia kitą, negali tuo pačiu metu abu būti teisingi arba abu klaidingi. Bet Kolmogorovas sako, kad tai paistalai. Juk tame ir glūdi kūrybos paslaptis. Ir 1932 m. „Intuistinės logikos išaiškinime“ jis pasiūlė klausimų sąrašą, tiesiogiai susijusių su dirbtiniu intelektu. „Trečio negalimumo“ dėsnis pakeistas silpnesniu prieštaravimo principu. Formuluotę 1930 m. pasiūlė Amsterdamo un-to prof. Arendas Heitingas, tačiau jau 1932 m. Kolmogorovas iškėlė naują Heitingo predikatų intuistinį skaičiavimą, kai kintamiesiems formulėse priskiriami bet kokie uždaviniai. Šią kryptį išvystė amerikietis Stivenas Kleinis2) bei rusas A. Markovas3) – ji gavo konstruktyviosios logikos4) pavadinimą.


Kolmogorovo sudėtingumo principas

Tarkime, turime tokią eilutę 111111..., pakartojančią 1 šimtą kartų. Šimto tokių ženklų eilutę galite atspausdinti trumpa tokio tipo programa:

repeat 100 
    print "1" 
end repeat

O dabar paimkime eilutę "231048322087232.." ir t.t. iki 100 skaitmenų, atseit atsitiktinių, bet tokiais nesančių, nes bandžiau kuo geriau juos parinkti. Bet vis tiek vargu ar parašysite programą, trumpesnę nei jos ilgis. Kitaip tariant, nėra kito būdo nurodyti šią atsitiktinai atrodančią eilutę kitaip, nei ją pakartoti.

Šių dviejų eilučių pavyzdys iliustruoja Kolmogorovo sudėtingumo idėją.
Pirma eilutė atspausdinama maždaug iš 30 ženklų sudaryta programa, tuo tarpu antrajai eilutei reikia programos, atkartojančios jos šimtą ženklų, - tad ji turi 100 baitų informacijos. AI

Atrodytų, kad tai puiki mintis, tačiau su ja yra problemų. Aišku, kad baitų, kurių reikia programai, kad išvestų šimtą 1, nėra aiškiai apibrėžtas skaičius – tai prikluso nuo pasirinktos programavimo kalbos. Tačiau kiekvienai kalbai galima apibrėti Kolmogorovo sudėtingumą kaip trumpiausios programos eilutės atspausdinimui (mūsų pavyzdžių atveju) ilgį. Taigi, sudėtingumas yra apibrėžtas atsižvelgiant į apibrėžiančiąją kalbą

Kiek įdomesnis atvejis yra su begalinio ilgio eilutėmis, nes, jei neturite eilutę generuojančios programos, iš esmės neturite, praktine prasme, ir pačios eilutės. Ta problema susijus ir su iracionaliais bei neiškaičiuojamais skaičiais. Iracionalus skaičius yra begalinė skaitmenų seka, pvz., 2.31048322087232 ...

Kai kuriems iracionaliems skaičiams turimos juos generuojančios programos – ir tokiu atveju jiems Kolmogorovo sudėtingumas nėra begalinis. Tačiau tokių skaičių tėra baigtinis skaičius tarp begalinio iracionalių skaičių kiekio. Paprasčiau sakant, nėturime pakankamai programų visų iracionalių skaičių paskaičiavimui.

Kalbant tikslesne kalba, iracionalių skaičių aleph-0 arba suskaičiuojama begalybė iracionalių skaičių, kuriems Kolmogorovo sudėtingumas mažesnis už begalybę ir aleph-1 - su begaliniu sudėtingumu. Pirmieji yra labai išskirtiniai („reikalingi“, kaip p ar e), todėl jiems yra parengtos programos, paskaičiuojančios norimu tikslumu.

Bet kaip paskaičiuoti tuos, kurių sudėtingumas mažesnis už begalybę? Paprasčiausiai suskaičiuojant visas juos programas, kurias galite sukurti. Ne visos jos generuos skaičių, netgi dauguma nedarys nieko naudinga, tačiau tame programų aleph-0 atsiras „reikalingų“ iracionalių skaičių aleph-0.

Tarp tų „reikalingųjų“ kai kurie yra transcendentiniai, t.y. tokie, kurie nėra jokios polinominės lygties šaknimi. Aišku, kad jei skaičius yra algebrinis, galima parašyti programą, sprendžiančią polinomą. Pvz., sqrt(2) yra iracionalus skaičius, tačiau galima programa, sprendžianti lygtį x2=2.

Kolmogorovo sudėtingumas nėra paskaičiuotinas

Kitas sunkumas dėl Kolmogorovo sudėtingumo mato yra tas, kad turėdami atsitikinai atrodančią eilutę negalite būti tikri, kad yra paprasta ją generuojanti programa. Tai kiek blogiau, nei atrodo, nes eilutei tas matas pats yra nepaskaičiuojama funkcija, t.y. nėra programos, kuri paimtų eilutę ir praneštų jos Kolmogorovo sudėtingumą. Tačiau tai nereiškia, kad viskas prarasta.

Galima tikėtis, kad Kolmogorovo sudėtingumas bet kuriai eilutei randamas gana lengvai. Jei eilutės ilgis L ir jai galima panaudoti kompresijos algoritmą, duodantį L-C ilgio rezultatą, tada eilutę galima sugeneruoti iš L-C ilgio išraiškos panaudojant dekompresijos programą. Eilučių sudėtingumas

Eilutė, kurios neįmanoma labiau suspausti, vadinama nesuspaudžiama. Ir galima įrodyti, kad nepakaks trumpesnių eilučių atvaizduoti visoms N ilgio eilutėms, nes žinoma, kad yra 2N eilutės, kurių ilgis N, tačiau tik 2N-1 eilutė, kurios ilgis mažesnis už N. ir vėl galime įrodyti, kad dauguma eilučių nėra stipriai suspaudžiamos, t.y. jos turi aukštą Kolmogorovo sudėtingumo reikšmę. Paėmę 50 ženklų eilutes, pamatysime, kad dauguma eilučių blogai spaudžiamos jau pasiekus C=5.

Turėdami visas šias idėjas, matome, kad eilutė yra algoritmiškai atsitiktine, jei nėra už ją trumpesnės programos, galinčios ją sugeneruoti – ir dauguma eilučių yra algoritmiškai atsitiktinės. Jei sudėtingumas yra susijęs su atsitiktinumu, tai jis turi būti susijęs ir su entropija.

Atsitiktinis ir pseudo-atsitiktinis

Verta aptarti ir atsitiktinių sekų generavimą. Pseudo atsitiktinių skaičių generatorius dažniausiai yra paprasta programa, kurios pateikti skaičiai gana gerai statistiškai atsitiktiniai, tačiau aišku, kad nėra algoritmiškai atsitiktiniais, nes jų Kolmogorovo sudėtingumas yra žemas. Bet kaip galime sukurti algoritmišką atsitiktinių skaičių generatorių? Jūs turite pastebėti esant paradoksą, kad algoritminis generatorius turi būti didesnis, nei jo generuojama seka. Tikriausiai tai ir yra skirtumas, kuo pseudo atsitiktiniai skaičiai skiriasi nuo realiai atsitiktinių skaičių.

Kolmogorovo sudėtingumas pasižymi tuo, kad jį lengva suprasti, tačiau jo negalima panaudoti realiam matavimui. Tačiau vis tik, atrodo, jis daug pasako apie fizinio pasaulio prigimtį ir mūsų bandymus jį aprašyti.


Biografijos ir paaiškinimai

1) Kristoferis Langtonas (Christopher Gale Langton, g. 1948 m.) - amerikiečių kompiuterių teoretikas, vienas dirbtinio intelekto pradininkų, įvedęs šį terminą 9-o dešimtm. pabaigoje, kai dirbo Los Alabamos nacionalinėje laboratorijoje. Vėliau jau Santa Fe inst-te jis tęsė dirbtinės gyvybės tyrimus. Prieš 2000-uosius jis paliko Santa Fe ir užmetė darbus su dirbtiniu intelektu, nuo tada nepaskelbęs nė vieno darbo iš šios srities.

2) Stivenas Kleinis (Stephen Cole Kleene, 1909-1994) – amerikiečių matematikas, su kitais pradėjęs matematikos šaką, vadinamą rekursijos teorija, padėjusiai pagrindus kompiuterijos mokslui. Pagrindinė tyrimų sritis buvo paskaičiuojamų funkcijų studijos. Jo vardas suteiktas daugeliui matematinių koncepcijų: Klino hierarchija, Klino algebra, Klino žvaigždė ir t.t. įskaitant Klino fiksuoto taško teoremą. Be viso to jis sukūrė reguliariąsias išraiškas (formalią paieškos ir manipuliacijų teksto eilutėse kalbą panaudojant metasimbolius – dabar paplitusią programavimo ir duomenų bazių kalbose, bei kitur) ir prisidėjo prie matematinio intuicionizmo bei baigtinių automatų teorijos (Klino teorema) vystymo.

3) Andrejus Markovas, jaunesnysis (1903-1979) – tarybinis matematikas, vienas konstruktyviosios matematikos rusų mokyklos įkūrėjų; poetas. Prisidėjo prie diferencialinių lygčių, topologijos, matematinės logikos ir matematikos pagrindų vystymo. Įvedė normaliojo algoritmo sąvoką. 1960 m. įrodė, kad 4-mačių daugdarų klasifikacija neįmanoma (nėra bendro algoritmo, leidžiančio atskirti dvi atsitiktinai paimtas daugdaras), nes jos yra pakankamai lanksčios, kad į savo struktūrą įtrauktų bet kurį algoritmą. http://www.vartiklis.lt/science/math/poincare.htm#terms

4) Konstruktyvizmas matematikos filosofijoje laiko, kad būtina rasti („sukonstruoti“) matematinį objektą norint įrodyti, kad jis egzistuoja. Įprastinėje matematikoje matematinio objekto egzistavimą leidžiama įrodyti jo tiesiogiai nesurandant, pvz., tarus jį neegzistuojant ir tada gaunant prieštaravimą iš tokios prielaidos. Konstruktyvizmas yra įvairių formų – tai ir Bauerio intuityvizmas, ir Hilberto baigtinumas (egzistuoja tik baigtiniai ojektai), Markovo konstruktyvi rekursyvi matematika, Bišopo konstruktyvi analizė ir kt.
Konstruktyvistinė (arba intuicionistinė) logika yra viena konstruktyvizmo matematikoje šaka. Tai formali sistema, atspindinti samprotavimus, priimtinus intuicionizmo požiūriu. Ją 1930 m. pasiūlė A. Heitingas. Pagrindinis jos skirtumas nuo tradicinio teiginių skaičiavimo yra tai, kad nėra negalimo trečiojo dėsnis. tarkim, kad turime teiginį „A arba B“. Intuicionistui tai reiškia, kad A arba B gali būti įrodyta. Tačiau trečio varianto nebuvimas „A arba ne A“ nepriimtinas, nes, atseit, ne visada įmanoma įrodyti, kad teisinga A arba jo neiginys.

Poezija ir skaitiniai
Filosofijos sritis
HOT.LT svetainė
Vartiklis