Алгоритмдік күрделілік өлшемі

Кіріспе

Алгоритмдік күрделіліктің өлшемі

Алгоритмдік ақпарат теориясында (компьютер ғылымы мен математиканың бір саласы), мәтін сияқты объектінің Колмогоров күрделілігі – объектіні нәтиже ретінде шығаратын ең қысқа компьютерлік бағдарламаның (алдын ала белгіленген бағдарламалау тілінде) ұзындығы. Бұл объектіні сипаттауға қажетті есептеу ресурстарының өлшемі, және оны алгоритмдік күрделілік, Соломонов-Колмогоров-Чайтин күрделілігі, бағдарлама көлемінің күрделілігі, сипаттамалық күрделілік немесе алгоритмдік энтропия деп те атайды. Ол 1963 жылы осы тақырыпта алғаш жариялаған Андрей Колмогоровтың есімімен аталған және классикалық ақпарат теориясының кеңейтілген түрі болып табылады. Колмогоров күрделілігінің түсінігі Кантордың диагональдық аргументіне, Гёдельдің толық еместік теоремасына және Тьюрингтің тоқтау проблемасына ұқсас, мүмкін емес екенін көрсету және дәлелдеу үшін қолданылуы мүмкін. Атап айтқанда, кез келген мәтіннің Колмогоров күрделілігі үшін төменгі шекті есептейтін P бағдарламасы, P-нің өзінің ұзындығынан салмақты түрде үлкен мәнді қайтара алмайды (қараңыз бөлім); сондықтан, ешбір бағдарлама шексіз көп мәтін үшін дәл Колмогоров күрделілігін есептей алмайды.

Қарапайым Колмогоров күрделілігі C

Колмогоровтың күрделілігінің екі анықтамасы бар: қарапайым және префикссіз. Қарапайым күрделілік – кез келген бағдарламаның ең аз сипаттама ұзындығы, және осымен белгіленеді, ал префикссіз күрделілік – префикссіз кодта кодталған кез келген бағдарламаның ең аз сипаттама ұзындығы, және осымен белгіленеді. Қарапайым күрделілік түсінуге оңайырақ, бірақ префикссіз күрделілікті зерттеу ыңғайлы. Дәстүр бойынша, барлық теңдеулер тек қосымша тұрақтыға дейін ғана дұрыс. Мысалы, шын мәнінде , яғни, .
демек, .
Берілген екілік тізбектерді екілік тізбектерге бейнелейтін есептеуге болатын функцияны қарастырайық. Егер және тек қана кез келген есептеуге болатын функцияны «бағдарламаға» кодтауға болады десек, онда ол әмбебап функция болады, мұнда біз оны бағдарламаны түсіндіретін құрал деп есептейміз, ол бағдарламаны сипаттайтын бастапқы бөлігін, содан кейін бағдарлама өңдеуі керек деректерді қабылдайды. Қарапайым күрделілікпен байланысты бір мәселе – , себебі интуитивті түрде айтқанда, біріктірілген тізбекті қарап ғана оны қалай бөлуге болады екенін анықтаудың жалпы жолы жоқ. Оны немесе ұзындығын көрсете отырып бөлуге болады, бірақ бұл қосымша символдарды қажет етеді. Шындығында, кез келген үшін мұндай болады.
Көбінесе, қарапайым күрделіліктегі теңсіздіктердің бір жағында ұқсас мүше болады, ал префикссіз күрделіліктегі теңсіздіктерде тек қана болады.
Қарапайым күрделіліктің басты мәселесі – бағдарламаға сырттан бір нәрсе қосылып кеткені. Бағдарлама тек өзінің кодымен ғана емес, сонымен қатар өзінің ұзындығын да көрсетеді. Атап айтқанда, бағдарлама тек өзінің ұзындығы арқылы дейін екілік санды көрсете алады. Басқаша айтқанда, сөздің соңы қайда екенін көрсету үшін тоқтату символын қолданғандаймыз, сондықтан біз 2 емес, 3 символ қолданамыз. Бұл кемшілікті жою үшін біз префикссіз Колмогоров күрделілігін енгіземіз.

Тарих және мәнмәтін

Алгоритмдік ақпарат теориясы – компьютер ғылымының тізбектерде (немесе басқа да дерек құрылымдарында) Колмогоров күрделігін және басқа да күрделік өлшемдерін зерттейтін саласы. Колмогоров күрделігі туралы түсінік пен теория алғаш рет 1960 жылы жарияланған Рей Соломоновтың маңызды теоремасына негізделген. Ол оны «Индуктивті қорытындының жалпы теориясы туралы алдын ала хабарлама» деп атап, алгоритмдік ықтималдықты ойлап табудың бір бөлігі ретінде сипаттады. Ол 1964 жылы жарық көрген «Индуктивті қорытындының формалды теориясы» басылымында толық сипаттама берді, «Ақпарат және басқару» журналының 1-ші және 2-ші бөлімдері. Андрей Колмогоров кейіннен осы теореманы 1965 жылы «Problems Inform. Transmission» журналында жариялады. Грегори Чайтин де осы теореманы J. ACM журналында ұсынды – Чайтиннің мақаласы 1966 жылдың қазан айында тапсырылып, 1968 жылдың желтоқсан айында қайта қарастырылды және ол Соломоновтың және Колмогоровтың мақалаларын сілтеме жасайды. Теорема, тізбектерді олардың сипаттамаларынан (кодтарынан) кодтайтын алгоритмдердің арасында ең оңтайлысы бар дейді. Бұл алгоритм барлық тізбектер үшін кез келген басқа алгоритмге рұқсат етілгендей қысқа кодтарды ұсынады, бірақ бұл алгоритмдерге байланысты, тізбектердің өзіне емес, қосымша тұрақтыға дейін. Соломонов осы алгоритмді және оның ұсынған код ұзындығын қолданып, тізбектің келесі сандарының индуктивті қорытындысын негізге алуға болатын «жалпыға ортақ ықтималдықты» анықтады. Колмогоров осы теореманы күрделік, кездейсоқтық және ақпарат сияқты бірнеше функцияларды анықтау үшін пайдаланды. Колмогоров Соломоновтың жұмысын білгенде, оның басымдығын мойындады. Бірнеше жыл бойы Соломоновтың жұмысы Батыс әлемінен гөрі Кеңес Одағында жақсы танылды. Дегенмен, ғылыми қауымдастықтың жалпы пікірі, осы типтегі күрделікті реттіліктің кездейсоқтығымен айналысатын Колмогоровпен байланыстыру болды, ал алгоритмдік ықтималдық – Соломоновпен байланысты болды, ол өзінің ойлап тапқан жалпыға ортақ алдын ала ықтималдық үлестірілімін пайдаланып болжауға баса назар аударды. Сипаттамалық күрделік пен ықтималдықты қамтитын кеңірек сала көбінесе Колмогоров күрделігі деп аталады. Компьютер ғалымы Минг Ли осыны Мэтью эффектісінің мысалы деп санайды: «Кімде бар, оған көбірек беріледі». Колмогоров күрделігінің немесе алгоритмдік ақпараттың тағы бірнеше нұсқалары бар. Ең көп қолданылатыны – өзін-өзі шектеуге ұшырататын бағдарламаларға негізделген, және бұл негізінен Леонид Левинге (1974) байланысты. Блум аксиомаларына (Блум 1967) негізделген Колмогоров күрделігіне аксиомалық тәсілді Марк Бургин Андрей Колмогоровтың жариялану үшін ұсынған еңбегінде енгізді.

Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other data structures). The concept and theory of Kolmogorov Complexity is based on a crucial theorem first discovered by Ray Solomonoff, who published it in 1960, describing it in "A Preliminary Report on a General Theory of Inductive Inference" as part of his invention of algorithmic probability. He gave a more complete description in his 1964 publications, "A Formal Theory of Inductive Inference," Part 1 and Part 2 in Information and Control. Andrey Kolmogorov later independently published this theorem in Problems Inform. Transmission in 1965. Gregory Chaitin also presents this theorem in J. ACM – Chaitin's paper was submitted October 1966 and revised in December 1968, and cites both Solomonoff's and Kolmogorov's papers. The theorem says that, among algorithms that decode strings from their descriptions (codes), there exists an optimal one. This algorithm, for all strings, allows codes as short as allowed by any other algorithm up to an additive constant that depends on the algorithms, but not on the strings themselves. Solomonoff used this algorithm and the code lengths it allows to define a "universal probability" of a string on which inductive inference of the subsequent digits of the string can be based. Kolmogorov used this theorem to define several functions of strings, including complexity, randomness, and information. When Kolmogorov became aware of Solomonoff's work, he acknowledged Solomonoff's priority. For several years, Solomonoff's work was better known in the Soviet Union than in the Western World. The general consensus in the scientific community, however, was to associate this type of complexity with Kolmogorov, who was concerned with randomness of a sequence, while Algorithmic Probability became associated with Solomonoff, who focused on prediction using his invention of the universal prior probability distribution. The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity. The computer scientist Ming Li considers this an example of the Matthew effect: " to everyone who has, more will be given "

There are several other variants of Kolmogorov complexity or algorithmic information. The most widely used one is based on self delimiting programs, and is mainly due to Leonid Levin (1974). An axiomatic approach to Kolmogorov complexity based on Blum axioms (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov.

Негізгі нәтижелер

Біз be деп жазамыз, мұндағы be – x және y жолдарының жұбын кодтаудың белгілі бір тәсілін білдіреді.

Теңсіздіктер

Біз қосымша факторларды жіберілді. (Бұл бөлімде негізделген.) Теорема. (ақпараттың өспеуі) Кез келген есептеуге болатын функция үшін, мынаны білеміз:
Дәлелдеме. Тьюринг машинасына екі кезекті бағдарламаны оқуға бағдарлама қойыңыз, біреуі функцияны, екіншісі жолдың сипаттамасын береді. Содан кейін екі бағдарламаны жұмыс таспасында іске қосып, нәтижені шығарыңыз.