Компьютерная лингвистика для всех: Мифы. Алгоритмы. Язык [Анатолий Васильевич Анисимов] (fb2) читать постранично, страница - 2

состояния, переходы, подструктуры и взаимодействия частей. Системный подход дает возможность анализировать многие сложные объекты с позиций единой общей методологии.

Наконец, в 30-е годы нашего столетия логики изобрели математическую теорию алгоритмов. Алгоритм — это сложная информационная система вместе с заданными правилами функционирования. В каждый момент, зная текущее состояние системы, ее правила и доступную ей информацию, можно предсказать множество ее возможных последующих изменений. Одно из важнейших понятий теории алгоритмов — рекурсия. Под рекурсией в общем смысле понимают такой способ организации системы, при котором она в отдельные моменты своего развития, определяемые ее правилами, может создавать (вызывать) собственные измененные копии, взаимодействовать с ними и включать их в свою структуру. Законы изменения копий при вызове также включаются в правила системы и могут зависеть от многих параметров: от состояния системы и других подсистем в момент вызова копии, от информационного наполнения заданных параметров, от правил самой системы. Возможно отсутствие изменения при вызове копии — чистая рекурсия (это частный случай). Существует многообразие вариантов поведения копий; они могут существовать и развиваться параллельно с главной системой, исчезать после окончания своего этапа функционирования, по-разному взаимодействовать между собой. Все определяется правилами системы. Рекурсия — важнейшее фундаментальное понятие теории алгоритмов. В этой теории было доказано, что, используя рекурсию, можно из ограниченного количества функциональных единиц получить все многообразие вычислимых функций.

Но не математики на самом деле открыли общий принцип рекурсии. Еще в древнейших религиях находим рекурсивные определения богов, а рекурсивные приемы для описания развития встречались во многих древних текстах. Объективный закон рекурсивного развития мира сначала выражался в текстах и только затем, много веков спустя, проявился в теории алгоритмов. С появлением в конце 40-х годов компьютеров и становлением программирования интерес к рекурсии только усилился. Рекурсивные процедуры и декларативные определения введены в большинство современных языков программирования. Это понятие хорошо известно программистам.

Обогатившись в теории алгоритмов и программировании, став привычным методом анализа и синтеза сложных алгоритмических систем, рекурсия возвращается в мнр, где она впервые была замечена и всегда существовала, даже неузнанная. Но теперь в ее багаже — мощные развитые алгоритмические методы, теперь она на виду. Оказалось, что язык рекурсивен. Из базового ограниченного набора схем, мифов и сказаний рекурсивным способом получаются все сложные сюжетные построения современных авторов. Анализ предложений показывает, что здесь рекурсия проявляется еще более убедительным способом. Она определяет вложенность комментирующих частей к различным частям предложения. Предложение, остававшееся до сих пор филологической загадкой, получает алгоритмическое определение, и сразу становятся ясными многие проблемные факты традиционного синтаксиса. Рекурсивные машины начинают учиться говорить и понимать язык.

Так закон рекурсивного развития мира сначала отразился в древних текстах, затем в литературе и только после этого получил математическое воплощение в теории алгоритмов и программировании. Потом снова произошло обратное отражение. Рекурсия определяет развитие литературы, дает возможность целенаправленно создавать сложные психологические тексты. Начинается игра усиливающихся отражений — любимая игра Вселенной. Когда-то и разум возник из такой игры.

АЛГОРИТМЫ

Любое целенаправленное действие сложной системы связано с понятием алгоритма. Он определяет последовательность действий объекта для достижения цели. Так первобытные охотники придумывали алгоритмы охоты на зверей и на соседние племена, а их жены изобретали первые кулинарные рецепты — тоже алгоритмы. Алгоритмы повседневной жизни человека отличаются неоднозначностью выбора ходов, расплывчатостью принятия решений, неоптимальностью исполнения. Это действие системы в ситуации с неполной информацией. Когда все ясно, человек целенаправленно действует наиболее рациональным образом — по кратчайшей прямой стремится пересечь местность, выбирает лучшее из возможного.

Познание всегда искало способы описания алгоритмов. Сохранились древние магические рецепты, математические тексты, книги боевого искусства, где описывались приемы действий в тех или иных ситуациях. В математической теории алгоритмов существует большое разнообразие определений алгоритма, ориентированных на различные способы вычислительной реализации: арифметическое исчисление предикатов (К. Гедель, 1931), λ — определимые (А. Черч, 1936) и частично-рекурсивные (С. Клини, 1936) функции, машины Поста и Тьюринга (Э. Пост, 1936, А. Тьюринг, 1937),