Читать онлайн «Основы теории алгоритмов»

Основы теории алгоритмов Коротков М. А. Степанов Е. О. 14 сентября 2003 г. Оглавление 1 Основы теории алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Тезис Черча. Регистровые машины . . . . . . . . . . . . . . . . . . . . . . 9 3 Некоторые алгоритмические массовые проблемы . . . . . . . . . . . . . . 14 3. 1 Самоприменимые программы . . . . . . . . . . . . . . . . . . . . . 15 3. 2 Проблема останова . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. 3 Теорема Райса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4 Разрешимость и перечислимость множества тавтологий . . . . . . . . . . 20 5 Формальные теории . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5. 1 Теорема о неподвижной точке . . . . . . . . . . . . . . . . . . . . . 29 5. 2 Теорема Тарского . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5. 3 Вторая теорема Геделя . . . . . . . . . . . . . . . . . . . . . . . . . 31 6 Язык Пролог . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6. 1 Формальная Система Опровержения . . . . . . . . . . . . . . . . 35  3 1 Основы теории алгоритмов Ранее мы занимались изучением языков, предназначенных для описания рассуждений. Теперь мы “поменяем угол зрения” и будем рассматривать языки, предназначенные для записи конкретных действий. Языки логики предикатов относятся к классу де- кларативных (описательных): смысл элемента такого языка (формулы) заключается в описании чего-либо. Те же языки, к изучению которых мы приступаем, можно на- звать языками инструкций, так как их элементы, называемые часто инструкциями, являются предписаниями исполнителю (человеку, компьютеру, другому вычислитель- ному устройству) совершить определенный набор действий. Поскольку набор точных инструкций для выполнения конкретных действий принято называть алгоритмом или программой, такие языки инструкций часто называются алгоритмическими языками или языками программирования. Последние два термина часто употребляются в слегка разных контекстах: под языком программирования обычно понимают язык инструк- ций для реально существующего вычислительного устройства – компьютера (Fortran, Basic, Pascal, C++ и т. п. ), а термин алгоритмический язык употребляется в более широком смысле и включает в себя как языки программирования, так и другие языки инструкций, в частности псевдоязыки, предназначенные для описания алгоритмов. Смещение нашего внимания с логических языков на языки инструкций обусловлено желанием дать ответы на те вопросы, котроые остались открытыми в нашем иссле- довании возможностей логических языков, а именно, на вопросы о том, каким обра- зом проверять истинность различного рода семантических утверждений о формулах языков логики предикатов (например, как проверить, является ли заданная формула языка логики первого или второго порядка тавтологией).