Матлог / Matematicheskaya_logika
.pdf
Тождественная истинность выводимых формул
Полнота и непротиворечивость исчисления предикатов
Понятие алгоритма и основные математические модели алгоритма
Машина Тьюринга и вычисляемая ею функция
Массовые распознавательные задачи
Массовые задачи – это задачи распознавания и оптимизации Примеры массовых задач:
ВЫП (SAT) – задача выполнимости формулы логики высказываний ТЕОРЕМА (THM) – задача доказуемости формулы логики предикатов
Сведение к задаче распознавания языка
Любая распознавательная задача с помощью кодировки сводится к задачам распознавания языка.
Разрешимые и полуразрешимые языки
Примеры разрешимых и полуразрешимых языков
(ПРИМЕРОВ ПОКА ЧТО НЕМА)
Распознаваемость языков машинами Тьюринга
Разрешимые и неразрешимые распознавательные проблемы
Временная и ленточная сложность машины Тьюринга
Классы языков P и NP
(ТО, ЧТО НИЖЕ, СКОРЕЕ ВСЕГО НЕ НУЖНО)
