Автоматы и машины — что значит «вычислить»

Когда пишут программу, легко забыть, что внизу всегда находится некий абстрактный исполнитель, который умеет делать конечное число простых шагов.

Теория автоматов возвращает этот факт на первый план и предлагает честно разобраться: какие именно классы задач можно решить такими исполнителями и каковы пределы их возможностей.

Детерминированные и недетерминированные конечные автоматы кажутся сначала игрушкой: несколько состояний, стрелочки переходов, входная строка.

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

Стековые автоматы добавляют ещё один измеритель — память в виде стека.

С их помощью описываются контекстно?свободные языки, а значит, синтаксис большинства языков программирования.

В этот момент студент вдруг видит, что парсер, который он вызывал из готовой библиотеки, живёт в том же мире, что и знакомый ему автомат, только с дополнительной структурой.

Связка «автомат + грамматика» превращается из абстрактной схемы в опорную модель: любой язык, который вы хотите обрабатывать, так или иначе вписывается в эту рамку — или сознательно выходит за неё.

Машина Тьюринга делает следующий шаг: она отбрасывает все детали реализации и оставляет только сущность вычисления — ленту, каретку для чтения и записи, конечное число состояний и правила перехода.

В этой предельно простой модели оказывается возможным описать любой алгоритм, реализуемый на реальном компьютере.

А когда к разговору подключаются бесконечные процессы и такие экзотические конструкции, как машина Зенона, становится видно, где проходит граница между тем, что математически вообразимо, и тем, что физически осуществимо.

Обратимые вычислительные модели и клеточные автоматы добавляют к этому разговор о том, насколько тесно вычисление связано с устройством мира: можно ли повернуть время вспять, можно ли сделать вычисление строго обратимым, и что из этого следует для квантовых и классических систем.

Для будущего специалиста по искусственному интеллекту третий семестр — это точка, когда слово «алгоритм» перестаёт быть синонимом «программа, которую я написал» и становится объектом строго определённого мира: с классами языков, типами автоматов, границами вычислимости и сложностью.

После этого разговора невозможно всерьёз обсуждать устройства больших языковых моделей, не задаваясь вопросом: а как их поведение соотносится с тем, что вообще считается вычислением, и где кончается просто сложный автомат и начинается что?то большее.

AML.

Телеграм: t.me/ainewsline

Источник: vk.com

Комментарии: