Т. А. Сливина математическая логика и теория алгоритмов

§ 3. Интерпретация языка теории 55
§ 4. Проблемы непротиворечивости, полноты, разрешимости теории 57
Глава 5. Алгоритмы 59
§ 1. Понятие алгоритма и его характерные черты 59
§ 2. Разрешимые и перечислимые множества 63
§ 3. Уточнение понятия алгоритма 64
§ 4. Вычислимые функции. Частично рекурсивные
и общерекурсивные функции 66
§ 5. Машины Тьюринга 70
§ 6. Нормальные алгоритмы Маркова 79
§ 7. Неразрешимые алгоритмические проблемы 81
Задачи и упражнения 86
Заключение 86
Библиографический список 87
ПРЕДИСЛОВИЕ

Дисциплина «Математическая логика и теория алгоритмов» относится к дискретной математике, читается студентам Института информатики и телекоммуникаций Сибирского государственного аэрокосмического университета на 2-ом курсе. Ее целями являются ознакомление студентов с максимально широким кругом понятий математической логики, используемых в дискретной математике; формирование терминологического запаса, необходимого для самостоятельного изучения специальной математической и теоретико-программистской литературы; овладение способами решения прикладных задач, на основе разбора доказательств, выполнения теоретических упражнений и решения типовых примеров.

Математика делится на дискретную и континуальную. К континуальной математике относится все, что явно или неявно содержит идеи теории пределов и непрерывности. Все остальное – дискретная математика.
Дискретная математика, частью которой является математическая логика и теория алгоритмов, – это бурно развивающаяся ветвь математики. Ее роль и место определяются в основном тремя факторами:
1) дискретную математику можно рассматривать как теоретические основы компьютерной математики;
2) модели и методы дискретной математики являются хорошим средством и языком для построения и анализа моделей в различных науках;
3) язык дискретной математики очень удобен и стал фактически метаязыком всей современной математики.
Дискретная математика включает в себя такие разделы как арифметика, алгебра, теория множеств, математическая логика, комбинаторный анализ, теория графов, теория алгоритмов, теория автоматов. Некоторые из перечисленных разделов, такие как теория алгоритмов и теория автоматов, студенты изучают более глубоко в специальных курсах.
Математическая логика является необходимым элементом каждой формальной дисциплины и состоит из правил получения обоснованного вывода. Одной из задач математической логики является анализ оснований математики. Аппарат математической логики нашел приложение в технике, в частности в релейно-контактных схемах, которые широко используются в электронно-вычислительной технике и в технике автоматического управления.
С появлением ЭВМ стала актуальной теория алгоритмов. Теорию алгоритмов можно понимать как науку пограничную между математикой и информатикой. Под алгоритмом понимают общее правило, с помощью которого можно решать некоторый класс однотипных задач. Данное определение не является строгим, поэтому для каждого задания алгоритм решения должен быть доказан. Отсутствие доказательства правильности алгоритма может означать, что предлагаемый алгоритм решает какую-либо другую задачу или является частным случаем поставленной. Рассмотренные в данном учебном пособии определения алгоритма и рассмотренные примеры позволят студентам и всем интересующимся лицам овладеть теоретическими знаниями и приобрести навыки в решении прикладных задач.
Глава 1