Читать онлайн «Лекции по математической логике»

М осковский Государственный Униворситет имени М# В# Ломоносова вычислительной математики и кибернетики 0# Б# ЛУПАНОВ ЛЕКЦИИ ПО МАТЕМАТИЧЕСКОЙ ЛОСИКЕ Чабть 2 Москва 1970 \ %5® МОСКОВСКИЙ ОРДШ ЛЕНИНА И ОВДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В*Д)МОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНО;! 7ДАТЕМАТИКИ И КИБЕРНЕТИКИ О. Б . ЛУ ПАНОВ ЛЕКЦИИ ГО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Часть П. *1&~ zi * I И" 3*?- Москва 1970 г. - A-XfV Ш-И-02, [1м *"9* АЛГОРИТМЫ Часто в математике возникают вопросы следующего вида. Имеется бесконечное множество однотипных задач. Требуется найти единый эффективный способ их решения. Приведем несколько примеров такого рода. 1. Нахождение всех простых делителей целого числа. 2. Извлечение квадратного корня из числа с определенной точностью. 3. Решение системы линейных уравнений. Имеется,например, метод Гаусса. 4. Выяснение тождественной истинности формул для функций алгебры логики. Зтот список можно было бы продолжить. Перечисленные и другие алгоритмы обладают рядом общих черт. Укажем важнейшие из них. 1) Элементарность шагов алгоритма: решение задачи должно распадаться на ряд этапов (их число может быть большим), каждый из которых является достаточно простым. 2) Детерминированность: после выполнения очередного этапа должно быть однозначно определено, что следует делать на следующем этапе. 3) Массовость; алгоритм должен быть пригоден для решения бесконечного множества задач. В тех случаях, когда алгоритм в каком-то виде удается найти, этим обычно ограничиваются. Однако для некоторых задач таких эффективных способов долго не удавалось найти. Примерами таких задач явились - установление тождественной истинности формуя " исчисления предикатов - разрешимость в целых числах диофантовых уравнений (алгебраических уравнений с целыми коэффициентами) и ряд других. Безуспешные попытки найти алгоритмы для решения этих задач дали основание допустить» что таких алгоритмов вообще не существует. I. I Пользуясь интуитивным понятием алгоритма, этот факт доказать вообще невозможно. Б связи с этим были предприняты попытка -уэреализовать понятие алгоритма. 3 середине 80 годов несколькими математиками были предложены различные формальные определения алгоритма ( А. Тьюринг , АоЧёрч, Э. Пост, А. А. Марков а др. ) впоследствии было установлено, что эти (и другие) понятия ъ определенном смысле эквивалентны. Этот факт говорит о том что, по-видимому, основные черты интуитивного понятия эффективной процедуры отражены в формальных определениях правильно. Ьткзсь в основном речь будет идти об одном из таких фор- мальььк определений алгоритма - о машинах Тьюринга. Некоторые другие будут описаны лишь в общих чертах. Кашина Тьюринга - это математическая модель вычислительного устройства. Каждая машина Тьюринга работает с некоторым конечным 'алфавитом A {c*»,gw,. •-, <**} j имеет (I) ленту и B) читающую и пишущую головку. Машина работает во времени, которое предполагается дискретным (моменте времени занумерованы: 1,2,... ). Будем предполагать, что среди букв алфавита имеется пустей символ dp (его будем обозначать также через О ) Лента бесконечна в обе стороны и разбита на клетки.