Алгоритмдік ақпарат теориясы – есептеу және ақпаратты байланыстыратын ғылым. Қысқарту, күрделілік, және кездейсоқ бағдарламалар зерттеледі. Теориялық информатика.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Ақпарат теориясы мен компьютерлік ғылымның кіші саласы
Subfield of information theory and computer science
Алгоритмдік ақпарат теориясы (АИТ) – теориялық компьютерлік ғылымның бір саласы, ол есептеу және есептеу арқылы жасалған объектілердің (стохастикалық түрде жасалғаннан өзгеше) арасындағы қатынаспен айналысады, мысалы, тізбектер немесе кез келген басқа да дерек құрылымы. Басқаша айтқанда, алгоритмдік ақпарат теориясында есептеудің сығымдалмауы (таңдалған әмбебап бағдарламалау тіліне байланысты тұрақтыны ескермегенде) ақпарат теориясындағы қатынастар мен теңсіздіктерді "қайталайды" екені көрсетіледі. Грегори Чейтиннің айтуынша, ол "Шеннонның ақпарат теориясы мен Тьюрингтің есептеу теориясын коктейль шайқағышқа салып, мұқият шайқаудың нәтижесі". Есептеу арқылы жасалған объектілердің азайтылмайтын ақпараттық мазмұны үшін әмбебап өлшемді ресмилеуден басқа, АИТ-тің негізгі жетістіктерінің бірі – алгоритмдік күрделіліктің (өзін-өзі шектейтін жағдайда) классикалық ақпарат теориясындағы энтропия сияқты теңсіздіктерді (тұрақтыны ескермегенде) сақтауы және кездейсоқ жасалған бағдарламалық құралдар саласында кез келген дерек құрылымының пайда болу ықтималдығы оны әмбебап машинада іске қосқанда жасалатын ең қысқа бағдарламаның ретімен сәйкес келеді. АИТ негізінен тізбектердің (немесе басқа дерек құрылымдарының) азайтылмайтын ақпараттық мазмұнының өлшемдерін зерттейді. Көптеген математикалық объектілерді тізбектер түрінде немесе тізбектер тізбегінің лиміті ретінде сипаттауға болатындықтан, оны сандарды қоса алғанда, математикалық объектілердің кең ауқымын зерттеу үшін пайдалануға болады. АИТ-тің негізгі себептерінің бірі – математикалық объектілер тасымалдайтын ақпаратты зерттеу, мысалы, метаматематика саласында, төменде көрсетілгендей толық еместік нәтижелері арқылы. Басқа негізгі себептер – классикалық ақпарат теориясының жеке және бекітілген объектілерге қатысты шектеулерін жеңу, кездейсоқтық тұжырымын ресмилеу және ықтималдық үлестірімі туралы алдын ала білімсіз мағыналы ықтималдық тұжырымдамасын табу (мысалы, тәуелсіз және бірдей бөлінген, Марковтық немесе тіпті стационарлық болса да). Осылайша, АИТ негізінен үш негізгі математикалық түсінік және олардың арасындағы қатынастарға негізделгені белгілі: алгоритмдік күрделілік, алгоритмдік кездейсоқтық және алгоритмдік ықтималдық. Ол осы саланың негізін құрайтын негізгі идеяларды жариялаған, алгоритмдік ықтималдықты ойлап тапқан. Бұл – статистикада Байес ережелерін қолданумен байланысты күрделі мәселелерді шешудің жолы. Ол алғашқы нәтижелерін 1960 жылы Калтехте өткен конференцияда және 1960 жылдың ақпан айында "Индуктивті қорытындының жалпы теориясы туралы алдын ала есеп" деген баяндамада сипаттады. Алгоритмдік ақпарат теориясы кейіннен Андрей Колмогоров (1965) және Грегори Чейтин (шамамен 1966) тәуелсіз түрде дамытты. Колмогоров күрделілігінің немесе алгоритмдік ақпараттың бірнеше нұсқасы бар; ең көп қолданылатыны өзін-өзі шектейтін бағдарламаларға негізделген және негізінен Леонид Левинге (1974) тиесілі. Пер Мартин Лёф шексіз тізбектер туралы ақпарат теориясына да маңызды үлес қосты. Блум аксиомаларына (Blum 1967) негізделген алгоритмдік ақпарат теориясына аксиомалық тәсілді Марк Бургин Андрей Колмогоровтың (Бургин 1982) жариялануға ұсынған мақаласында таныстырды. Аксиомалық тәсіл алгоритмдік ақпарат теориясындағы басқа тәсілдерді қамтиды. Алгоритмдік ақпараттың әртүрлі өлшемдерін аксиоматикалық анықталған алгоритмдік ақпарат өлшемдерінің ерекше жағдайлары ретінде қарастыруға болады. Әрбір нақты өлшем үшін негізгі инварианттық теорема сияқты ұқсас теоремаларды дәлелдеудің орнына, аксиоматикалық жағдайда дәлелденген бір сәйкес теоремадан барлық осындай нәтижелерді оңай шығаруға болады. Бұл математикадағы аксиоматикалық тәсілдің жалпы артықшылығы. Алгоритмдік ақпарат теориясының аксиоматикалық тәсілі кітапта (Burgin 2005) одан әрі дамытылды және бағдарламалық қамтамасыз ету метрикасына қолданылды (Burgin and Debnath, 2003; Debnath and Burgin, 2003).
Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" (except for a constant that only depends on the chosen universal programming language) the relations or inequalities found in information theory. According to Gregory Chaitin, it is "the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously." Besides the formalization of a universal measure for irreducible information content of computably generated objects, some main achievements of AIT were to show that: in fact algorithmic complexity follows (in the self delimited case) the same inequalities (except for a constant) that entropy does, as in classical information theory; and, within the realm of randomly generated software, the probability of occurrence of any data structure is of the order of the shortest program that generates it when running on a universal machine. AIT principally studies measures of irreducible information content of strings (or other data structures). Because most mathematical objects can be described in terms of strings, or as the limit of a sequence of strings, it can be used to study a wide variety of mathematical objects, including integers. One of the main motivations behind AIT is the very study of the information carried by mathematical objects as in the field of metamathematics, e. g., as shown by the incompleteness results mentioned below. Other main motivations came from surpassing the limitations of classical information theory for single and fixed objects, formalizing the concept of randomness, and finding a meaningful probabilistic inference without prior knowledge of the probability distribution (e. g., whether it is independent and identically distributed, Markovian, or even stationary). In this way, AIT is known to be basically founded upon three main mathematical concepts and the relations between them: algorithmic complexity, algorithmic randomness, and algorithmic probability. who published the basic ideas on which the field is based as part of his invention of algorithmic probability—a way to overcome serious problems associated with the application of Bayes' rules in statistics. He first described his results at a Conference at Caltech in 1960, and in a report, February 1960, "A Preliminary Report on a General Theory of Inductive Inference." Algorithmic information theory was later developed independently by Andrey Kolmogorov, in 1965 and Gregory Chaitin, around 1966. There are several 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). Per Martin Löf also contributed significantly to the information theory of infinite sequences. An axiomatic approach to algorithmic information theory based on the Blum axioms (Blum 1967) was introduced by Mark Burgin in a paper presented for publication by Andrey Kolmogorov (Burgin 1982). The axiomatic approach encompasses other approaches in the algorithmic information theory. It is possible to treat different measures of algorithmic information as particular cases of axiomatically defined measures of algorithmic information. Instead of proving similar theorems, such as the basic invariance theorem, for each particular measure, it is possible to easily deduce all such results from one corresponding theorem proved in the axiomatic setting. This is a general advantage of the axiomatic approach in mathematics. The axiomatic approach to algorithmic information theory was further developed in the book (Burgin 2005) and applied to software metrics (Burgin and Debnath, 2003; Debnath and Burgin, 2003).
Нақты анықтамалар
Егер тізбектің Колмогоровтық күрделілігі тізбектің ұзындығынан кем болмаса, онда екілік тізбек кездейсоқ деп аталады. Қарапайым санау арқылы кез келген ұзындықтағы кейбір тізбектер кездейсоқ екені, ал көбінесе тізбектер кездейсоқтыққа өте жақын екені көрсетіледі. Колмогоровтық күрделілік әмбебап Тьюринг машинасының белгілі бір таңдауына байланысты болғандықтан (бұл «сипаттамалар» берілген белгілі бір «сипаттау тілі»), кездейсоқ тізбектер жинағы да осы таңдауға тәуелді болады. Дегенмен, кездейсоқ тізбектер жинағы тұтастай алғанда, қандай да бір белгілі машинаға тәуелді болмай, ұқсас қасиеттерге ие, сондықтан әмбебап машинаны алдымен анықтамай, кездейсоқ тізбектердің қасиеттері туралы топ ретінде сөйлеуге болады (және көбінесе солай істеледі). Егер кейбір тұрақты c үшін, кез келген n үшін, тізбектің n ұзындығындағы бастапқы бөлігінің Колмогоровтық күрделілігі n – c-ден кем болмаса, онда шексіз екілік тізбек кездейсоқ деп аталады. Стандартты өлшем бойынша (яғни «әділ монета» немесе Лебег өлшемі) шексіз екілік тізбектердің көбінесе кездейсоқ екенін көрсетуге болады. Сонымен қатар, екі әртүрлі әмбебап машинаға қатысты Колмогоровтық күрделілік арасындағы айырмашылық тұрақты шамадан аспайтынын көрсетуге болады, сондықтан кездейсоқ шексіз тізбектер жинағы әмбебап машинаның таңдауына тәуелді емес (шекті тізбектерге керісінше). Кездейсоқтықтың бұл анықтамасы әдетте Пер Мартин Лёфтың атымен аталады, оны басқа ұқсас кездейсоқтық түсініктерінен ажырату үшін. Оны кейде 1-кездейсоқтық деп те атайды, осыны басқа күштірек кездейсоқтық түсініктерінен (2-кездейсоқтық, 3-кездейсоқтық және т.б.) ажырату үшін. Мартин Лёфтың кездейсоқтық тұжырымдарынан басқа, рекурсивті кездейсоқтық, Шнорр кездейсоқтық және Куртц кездейсоқтық сияқты түсініктер де бар. Юнг Ванг осы кездейсоқтық түсініктерінің барлығы әртүрлі екенін көрсетті. (Басқа әліпбилер үшін де ұқсас анықтамалар жасауға болады.)
A binary string is said to be random if the Kolmogorov complexity of the string is at least the length of the string. A simple counting argument shows that some strings of any given length are random, and almost all strings are very close to being random. Since Kolmogorov complexity depends on a fixed choice of universal Turing machine (informally, a fixed "description language" in which the "descriptions" are given), the collection of random strings does depend on the choice of fixed universal machine. Nevertheless, the collection of random strings, as a whole, has similar properties regardless of the fixed machine, so one can (and often does) talk about the properties of random strings as a group without having to first specify a universal machine. An infinite binary sequence is said to be random if, for some constant c, for all n, the Kolmogorov complexity of the initial segment of length n of the sequence is at least n − c. It can be shown that almost every sequence (from the point of view of the standard measure—"fair coin" or Lebesgue measure—on the space of infinite binary sequences) is random. Also, since it can be shown that the Kolmogorov complexity relative to two different universal machines differs by at most a constant, the collection of random infinite sequences does not depend on the choice of universal machine (in contrast to finite strings). This definition of randomness is usually called Martin Löf randomness, after Per Martin Löf, to distinguish it from other similar notions of randomness. It is also sometimes called 1 randomness to distinguish it from other stronger notions of randomness (2 randomness, 3 randomness, etc.). In addition to Martin Löf randomness concepts, there are also recursive randomness, Schnorr randomness, and Kurtz randomness etc. Yongge Wang showed that all of these randomness concepts are different. (Related definitions can be made for alphabets other than the set .)