Теория на алгоритмичната информация

от Уикипедия, свободната енциклопедия

Теория на алгоритмичната информация е раздел от теорията на информацията и информатиката, който се занимава с взаимоотношенията между изчисленията и информацията.

Според Гегъри Чайтин, това е резултат от съчетаването на теорията на информацията на Клод Шанън с изчислителната теория на Алън Тюринг.[1]

Преглед[редактиране | редактиране на кода]

Теорията на алгоритмичната информация основно изучава Теорията на изчислителната сложност, измервайки низове (или други структури от данни). Тъй като повечето математически обекти могат да бъдат описани чрез низове, или като сходяща редица от низове, теорията може да се използва за проучване на голямо разнообразие от математически обекти, включително цели числа.

Неформално, от гледна точка на теорията на алгоритмичната информация, съдържанието на информация в един низ е равен на дължината на възможно най-сгъстената, самостоятелна презентация на низа. Това по същество е компютърна програма – написана с фиксиран, но в същото време различен програмен език, който показва оригиналния низ когато програмата бъде стартирана.

Погледнато по този начин, енциклопедия от 3000 страници действително съдържа по-малко информация от 3000 страници, пълни с напълно произволни букви, въпреки факта, че енциклопедията е по-образователна. Това е така, защото за да се реконструира цялата последователност от случайни букви, човек трябва да знае, повече или по-малко, това, което представлява всяка една буква. От друга страна обаче, ако всяка гласна буква се извади от енциклопедията, някой с добри познания по английски език, би могъл да я реконструира и само със съгласни според контекста, така както би реконструирал изречението „Тв зрчн м нск сдржн н глсн“.

За разлика от класическата теория за информацията, теорията на алгоритмичната информация дава формални, строги дефиниции за произволен низ и произволна безкрайна редица, които не зависят от физическа или философска интуиция за безкрайността или вероятностите (Множеството на случайни низове зависи от избора на универсалната машина на Тюринг, използвана да дефинира сложност на Колмогоров, но всеки избор дава идентични асимптоматични резултати, защото „сложността на Колмогоров“ за низовете е инвариантна спрямо добавена константа, като зависи само от избора на универсалната машина на Тюринг. По тази причина множеството на случайни безкрайни редици зависи от избора на универсалната машина.).

История[редактиране | редактиране на кода]

Теорията на алгоритмична информация е създадена от Рей Соломонов[2], който публикува основните идеи на изобретението си – алгоритмична вероятност – начин да преодолееш сериозни проблеми свързани с прилагане на правилата на Бей в статистиката. Първо описал резултатите си на конференцията в Калифорнийския технологичен институт през 1960 г.[3] и в доклад през февруари 1960-а наречен „Предварителен доклад по Обща теория на индуктивен извод“[4]. Теорията на алгоритмичната информация впоследствие била независимо развита от Андрей Колмогоров и през 1965 и Грегъри Чайтин около 1966 година.

Има няколко варианта на „сложността на Колмогоров“ или алгоритмичната информация; най-широко използваният е базиран на самостоятелно определящи границите си програми и основно заради Леонид Левин. (1974). Пер-Мартин Льов също допринася значително към теорията на информацията на безкрайните редици. Аксиоматичен подход към теорията на алгоритмична информация базирана на аксиомата на Блум (1967 г.) е представена от Марк Бъргин в презентация за публикация на Андрей Колмогоров през 1982 г. Аксиоматичният подход обхваща други подходи към теорията за алгоритмична информация. Възможно е да се изследват различни измервания на алгоритмичната информация като частни случаи на аксиоматично дефинирани измервания на алгоритмичната информация. Вместо да доказва подобни теореми, като основната теорема за инвариантност, за всяко специфично измерване, е възможно лесно да заключим, че всички подобни резултати от кореспондираща теорема доказват аксиоматичното условие.

Точни дефиниции[редактиране | редактиране на кода]

Един двоичен низ е случайно подреден, ако Колмогоровата сложност на низа е поне дължината на низа. Едно просто преброяване показва, че някои низове с произволна дължина са изцяло случайно подредени, а почти всички низове са близки до цялостна случайна подредба. Тъй като Колмогоровата сложност зависи от фиксирания избор на универсалната Тюринг машина, колекция от случайно подредени низове зависи от този избор! Въпреки всичко, една колекция от случайно подредени низове, като цяло, има сходни свойства независимо от избора на Тюринг машината, за това често се говори за свойствата на случайно подредени низове, без предварително да е уточнен този избор.

Една безкрайна двоична поредица е случайно подредена, ако константата – c – за всички n Колмогоровата сложност на първоначалния сегмент/парче-n- е поне „n-c“. Лесно може да се покаже, че всяка поредица е случайно подредена. Също така може да се покаже, че, тъй като Колмогоровата сложност, отнасяща се до две различни универсални машини на Тюринг е най-много с константна сложност, то колекция от безкрайни поредици не зависи от този избор (противоположното на крайните поредици). Дефиницията за случайност често е наричана Мартин Люф случайност, която да я отличава от сходни дефиниции за случайности. Често е наричана и 1-randomness целяща да се отличава от по-силни понятия за случайност (2-randomness, 3-randomess…). В допълнение към концепцията на Мартин Люф за случайност, има рекурсивна случайност, случайност на Шнор, случайност на Къртз и т.н.

Специфична последователност[редактиране | редактиране на кода]

Теорията на алгоритмичната информация е теория за индивидуални обекти, използваща компютърната наука, и занимаваща се с отношенията между изчисления, информация и случайност. Информационното съдържание или сложността на един обект може да се измери с дължината на най-краткото му описание. Например низа:

„0101010101010101010101010101010101010101010101010101010101010101“

най-краткото му описание е 32 пъти „01“, докато низът:

„1100100001100001110111101110110011111010010000100101011110010110“

няма достатъчно кратко описание, освен да се изпише целият низ.

По-формално, алгоритмичната сложност (АС) на низ –х- се определя като дължината на най-кратка програма която може да изчисли или изпише низа Х, където програмата оперира върху универсален компютър с фиксиран размер. Алгоритмичната Соломонова възможност (АВ) е ключова, отнасяйки се за „старият философски“ проблем за индукция по формален начин.

Основният недостатък на АС и АВ е тяхната неизчислимост. Време свързаната „Левин“ сложност, наказва една такава бавна програма/изчисление като прибавя към нея и логаритъм от „работното“ и време към дължината. Това води до изчислимите варианти на АС и АВ, и решението което решава инверсионните проблеми за оптимално време – Универсално „Левин“ търсене (УТ).

АС и АВ също така позволяват официална и стриктна дефиниция за случайна подредба на индивидуален низ, да не зависи от физически или философски интуиции за не-определеност и вероятност. Грубо казано, един низ е алгоритмично подреден на случаен принцип по концепцията на Мартин Люф, ако е несвиваем, в смисъла на това че неговата алгоритмична сложност е равна на дължината му.

АС, АВ са основни под-дисциплини на алгоритмичната информационна теория (АИТ), но тя се разпростира в много други области. Тя служи за основа на принципа на минимална описателна дължина (МОД), може да опростява доказателства в изчислително-сложностните теории, решава Максуел-Даемон проблема и намира много други приложения.

Приложения на алгоритмичната теория[редактиране | редактиране на кода]

Въпреки несъвместимостта на нейните основни концепции, алгоритмичната теория има много, но често неочаквани приложения.

Философия[редактиране | редактиране на кода]

Алгоритмичната теория (АТ) помага при разрешаването на много философски проблеми. Тя позволява формализиране на много интуитивни, но неясни понятия, имащи голямо значение, и следователно позволява да се говори за тях в един смислен и точен начин, което води до по-дълбокото им разбиране.

Най-важното е, че алгоритмичната сложност на „Колмогоров“ (АС) формализира количествено концепциите за простота и сложност по уникален начин. Основната научна парадигма се нарича бръсначът на „Окам“ и обикновено се тълкува като: „сред два модела, които описват данните еднакво добре, трябва да се предпочете по-простият“. Използване на алгоритмичната сложност на „Колмогоров“ за количествено определяне на „обикновеност" позволява на Соломонов и други, да развият своите универсални теории за индукция и действие, в областта на изкуствен интелект.

АТ е също така била полезна в изграждането на основите на термодинамиката и втората и теорема за увеличаване на ентропията, и по-специално за решаване на проблема с демонът на Максуел.

Практиката[редактиране | редактиране на кода]

Със сближаването (често грубо) на „идеални“ понятия, АТ се прилага за различни проблеми, свързани с практически интерес, например, в лингвистиката и генетиката. Идеята е да се замени универсална машина Тюринг U от по-ограничени машини „Тюринг“, често адаптирани към конкретната причина за дадения проблем. Основният проблем е, че точността на приближение може трудно да се оцени и повечето теореми се провалят.

Универсалната сходствена метрика, е може би най-големият практически успех на АТ: разумна дефиниция за сходството между два обекта е, това колко трудно е да бъдат превърнати един в друг. По-официално: единият обект ще дефинира приликата между два низа х и у, като дължина на най-късата програма, изчисляваща х от y – (К (х | Y)).

Наука[редактиране | редактиране на кода]

Изявления в информационната теория на „Шанън“ и класическата теория на вероятностите се дължат до голяма степен на вероятностите или високите очаквания. Теоремите са обикновено в следната форма: „съществува набор от мерки X, за които Y притежава...", т.е. те са полезни за големи шаблони. Алгоритмичната случайност на „Martin-Löf“ от друга страна може да изгради множествата, а резултатите да съдържат отделните наблюдения / низове.

Понятията от АТ също са били експлоатирани в математиката и теоретичните компютърни науки: АТ, чрез метода за несвиваемост, е разрешила много отворени проблеми в компютърната теория и математиката, спомага за опростяването на много доказателства, и е важна в разбирането на обратимата изчислителност. Намира приложение в Статистиката, Когнитивните науки, Биология, Физика и Икономика.

Области[редактиране | редактиране на кода]

Областта на алгоритмичната теория може да бъде разделена на 4 отделни подобласти:

Алгоритмична сложност на „Колмогоров“ (АС)[редактиране | редактиране на кода]

  • Философски съображения
  • Свойства на Алгоритмичната сложност
  • Сложност на Колмогоров
  • Сложност на префиксите
  • Сложност ограничена от ресурси
  • Други варианти на сложност

Алгоритмична вероятност на „Соломонов“ (АВ)[редактиране | редактиране на кода]

  • Бръснач на Окам
  • Дискретна алгоритмична вероятност
  • Непрекъсната алгоритмична вероятност
  • Универсална последователност на прогнозите
  • Колеблива вероятност

Универсално търсене на „Левин“ (УТ)[редактиране | редактиране на кода]

  • Търсене на Левин
  • Сложност на Левин
  • Адаптивно търсене на Левин
  • Най-бързите алгоритни на общи проблеми
  • Оптимално подредено разрешаване на проблеми
  • Машини на Гьодел

Алгоритмична случайност на „Martin-Löf“ (АСМ)[редактиране | редактиране на кода]

Източници[редактиране | редактиране на кода]

  1. ↑ Теория на алгоритмичната информация // Архивиран от оригинала на 2016-01-23. Посетен на 2016-04-27.
  2. ↑ Vitanyi, P. "Obituary: Ray Solomonoff, Founding Father of Algorithmic Information Theory"
  3. ↑ Paper from conference on „Cerebral Systems and Computers“, California Institute of Technology, February 8 – 11, 1960, cited in "A Formal Theory of Inductive Inference, Part 1, 1964, p. 1
  4. ↑ Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma., (November Revision of February 4, 1960 report.)
  Тази страница частично или изцяло представлява превод на страницата Algorithmic_information_theory в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​

Взето от „https://bg.wikipedia.org/w/index.php?title=Теория_на_алгоритмичната_информация&oldid=11992757“.