- •Математическая логика
- •Парадигмы формальной логики.
- •Предмет, цель, задачи и содержание читаемого курса лекций.
- •Место читаемого курса о законах и формах правильного мышления.
- •Концептуальный базис математической логики.
- •Построение математической логики.
- •Классическая логика высказываний.
- •Язык классической логики предикатов (я.Л.П.).
- •Примеры:
- •Алгебра логики предикатов.
- •Пояснения:
- •Квантификация предикатов.
- •Эквивалентные преобразования кванторных формул.
- •Классические логические исчисления.
- •Цель классических и.В. И и.П.
- •Метасимволика и.В. И и.П.
- •Построение логических исчислений.
- •Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.
- •Основные требования к алгоритмам.
- •Основная терминология теории алгоритмов.
- •Основные теоремы теории алгоритмов.
- •Параметры алгоритма.
- •Основная гипотеза теории алгоритмов.
- •Алгоритмические (формальные математические) модели.
- •Блок-схемы алгоритмов.
- •Машина Тьюринга. Машина Тьюринга т – название, закрепившееся за вычислительными абстрактными машинами некоторого точно охарактеризованного типа.
- •1) Пусть последовательность k0k2kzимеет видq0a2a1a4q1a1qza4a2(очевидно, что последовательность команд следующая:q0a2q1a4 dп,q1a1qza2dЛ).
- •Формальное определение машины Тьюринга.
- •Основной тезис Тьюринга.
- •Нормальные алгорифмы (алгоритмы).
- •Рекурсивные функции.
- •Примитивно-рекурсивные функции.
- •Оператор минимизации (- орератор).
- •Основной тезис Черча.
- •Алгоритмически неразрешимые проблемы.
Алгоритмически неразрешимые проблемы.
Массовые проблемы, для которых не существует эффективных методов разрешения, называются алгоритмически неразрешимыми проблемами.
В интуитивном смысле массовая (алгоритмическая) проблема – это бесконечный класс родственных единичных конкретных проблем, правильный ответ для каждой из которых получается применением алгоритма.
Фактически произвольную массовую проблему можно сформулировать как проблему распознавания некоторого свойства Р элементов бесконечного множества М; при этом единичные проблемы. составляющие массовую проблему, связываются с элементами множества М, и каждая из них состоит в том, что требует узнать, обладает или нет свойством Р соответствующий элемент множества М. Поэтому задача ставится так: найти алгоритм, применимый к любому элементу множества М и для каждого данного хМ дает «1» или «0» в зависимости от того, обладает или нет элемент х свойством Р. Массовая проблема называется неразрешимой, если такого алгоритма нет.
Очевидно, принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения проблем, из которых вытекало бы (если бы они были разрешимы) существование объектов.
Понятие алгоритмической неразрешимости уточняется с привлечением математических понятий машины Тьюринга, рекурсивных функций, нормальных алгоритмов и других.
Известны два способа доказательства неразрешимости: прямой и косвенный, использующий сводимость к данной проблеме другой массовой проблеме, неразрешимость которой была доказана раньше.
Напоминание:
В настоящее время алгоритмические проблемы формируются как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач и нахождения такого алгоритма в случае, если он существует.