Математическая логика и теория алгоритмов

Содержание математической логики

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

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

В качестве предпосылок выступают некоторые положения, принятые для целей осуществления доказательства. Установление посылок может производиться по-разному:

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

Чтобы перейти от предпосылок к выводам, используют рассуждения. Точность предпосылок и корректность применяемых к ним операций определяют надежность доказательства.

Определяющую роль в возникновении логики как науки традиционно отводят Аристотелю (384-322 гг. до н. э.). Математическая логика получила развитие в XX веке. Она унаследовала задачи формальной логики, но стала применять для их решения аппарат математики. База этого направления была заложена в XIX веке, когда ученые:

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

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

Математическая логика решает следующие основные задачи:

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

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

Теория алгоритмов

Типичный алгоритм ориентирован на решение не частной задачи, а класса задач. Чтобы решить частную задачу с помощью обобщенного алгоритма, задают конкретные значения параметров (который для алгоритма играют роль исходных данных).

Ключевые особенности алгоритма:

• определенность. В алгоритме выделяют этапы (отдельные шаги), каждый из которых является локальным и простым;
• ввод. У алгоритма есть некоторое (в вырожденном случае – нулевое) количество входных данных (величин, которые задаются до начала работы);
• вывод. У алгоритма есть одна или несколько выходных величин (которые имеют связь со входными данными);
• детерминированность. После того, как выполнен очередной шаг алгоритма, должно быть однозначно определено, что делать дальше (на следующем шаге).

Отправной точкой в развитии теории алгоритмов стало доказательство теорем о неполноте формальных систем Куртом Геделем. В связи с этим возникло предположение, что многие математические проблемы невозможно разрешить алгоритмически – например, проблему выводимости в исчислении предикатов. Возникла потребность стандартизировать понятие алгоритма. Независимо друг от друга несколько ученых получили эквивалентные варианты:

• машина Тьюринга (Алан Тьюринг). Она представляет собой абстрактного исполнителя (абстрактную вычислительную машину), являющегося расширением конечного автомата. В соответствии с тезисом Черча-Тьюринга, машина Тьюринга на основании задания правил перехода может имитировать всех других исполнителей, каким-то образом реализующих пошаговые вычисления с достаточно элементарными отдельными шагами;
• машина Поста (Эмиль Пост);
• лямбда-исчисление (Алонзо Черч), в рамках которого рассматривается пара из лямбда-выражения и его аргумента. Вычислением при этом считают апплицирование (применение) первого члена из пары ко второму. Благодаря этому производится разделение функции и того, к чему ее применяют. В более общем случае вычисление определяют как цепочку, начинающуюся с исходного лямбда-выражения и включающую конечную последовательность лямбда-выражений, где каждое следующее получают из предыдущего с помощью правила подстановки (бета-редукции);
• рекурсивная функция (Стивен Клини).

Ценность для теории представляет понятие нормального алгоритма, введенное Андреем Марковым. Его разработка была связана с доказательством неразрешимости алгоритмическими методами некоторых алгебраических проблем.