Основные работы Геделя, Клини, Черча, Поста, Тьюринга по теории алгоритмов
Теория алгоритмов
Теория алгоритмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п.
Тезис Чёрча — Тьюринга и алгоритмически неразрешимые массовые проблемы
Алан Тьюринг высказал предположение (известное как Тезис Чёрча — Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.
В течение первого десятилетия истории теории алгоритмов неразрешимые массовые проблемы были обнаружены лишь внутри самой этой теории (сюда относится описанная выше проблема применимости), а также внутри математической логики (проблема выводимости в классическом исчислении предикатов). Поэтому считалось, что теория алгоритмов представляет собой обочину математики, не имеющую значения для таких её классических разделов, как алгебра или анализ. Положение изменилось после того, как А. А. Марков и Э. Л. Пост в 1947 году установили алгоритмическую неразрешимость известной в алгебре проблемы равенства для конечнопорождённых и конечноопределённых полугрупп (т. н. проблемы Туэ). Впоследствии была установлена алгоритмическая неразрешимость и многих других «чисто математических» массовых проблем. Одним из наиболее известных результатов в этой области является доказанная Ю. В. Матиясевичем алгоритмическая неразрешимость десятой проблемы Гильберта.
Теорема Гёделя
С тех пор прошло три четверти века, но споры о том, что же всё-таки доказал Гёдель, не утихают. Особенно жаркие прения идут в околонаучных кругах. «Теорема Гёделя о неполноте является поистине уникальной. На нее ссылаются всякий раз, когда хотят доказать «всё на свете» — от наличия богов до отсутствия разума», — пишет выдающийся современный математик В. А. Успенский.
Если оставить в стороне многочисленные подобные спекуляции, то нужно отметить, что ученые разделились в вопросе оценки роли Гёделя на две группы. Одни вслед за Расселом считают, что знаменитая теорема, которая легла в основу современной математической логики, тем не менее, оказала весьма незначительное влияние на дальнейшую работу за пределами данной дисциплины — математики как доказывали свои теоремы в «догёделевскую» эпоху, так и продолжают доказывать их и по сей день.
Что же касается фантасмагорического видения компьютеров, непрерывно доказывающих всё новые теоремы, то смысл подобной деятельности у многих специалистов вызывает большое сомнение. Ведь для математики важна не только формулировка доказанной теоремы, но и ее понимание, поскольку именно оно позволяет выявить связь между различными объектами и понять, в каком направлении можно двигаться дальше. Без такого понимания теоремы, генерируемые на основе правил формализованного вывода, представляют собой лишь своего рода «математический спам», — таково мнение сотрудника кафедры математической логики и теории алгоритмов мехмата МГУ Александра Шеня.
Похожим образом рассуждал и сам Гёдель. Тем, кто упрекал его в разрушении целостности фундамента математики, он отвечал, что по сути ничего не изменилось, основы остались по-прежнему незыблемыми, а его теорема привела лишь к переоценке роли интуиции и личной инициативы в той области науки, которой управляют железные законы логики, оставляющие, казалось бы, мало места для подобных достоинств. Однако некоторые ученые придерживаются другого мнения. Действительно, если считать умение логически рассуждать основной характеристикой человеческого разума или, по крайней мере, главным его инструментом, то теорема Гёделя прямо указывает на ограниченность возможностей нашего мозга. Согласитесь, что человеку, воспитанному на вере в бесконечное могущество мысли, очень трудно принять тезис о пределах ее власти.
Скорее уж речь может идти об ограниченности наших представлений о собственных ментальных возможностях. Многие специалисты полагают, что формально-вычислительные, «аристотелевские» процессы, лежащие в основе логического мышления, составляют лишь часть человеческого сознания. Другая же его область, принципиально «невычислительная», отвечает за такие проявления, как интуиция, творческие озарения и понимание. И если первая половина разума подпадает под гёделевские ограничения, то вторая от подобных рамок свободна.
Наиболее последовательный сторонник подобной точки зрения — крупнейший специалист в области математики и теоретической физики Роджер Пенроуз — пошел еще дальше. Он предположил существование некоторых квантовых эффектов невычислительного характера, обеспечивающих реализацию творческих актов сознания. И хотя многие его коллеги критически относятся к идее наделить человеческий мозг гипотетическими квантовыми механизмами, Пенроуз со своими сотрудниками уже разработал схему эксперимента, который должен, по их мнению, подтвердить их наличие.
Одним их многочисленных следствий гипотезы Пенроуза может стать, в частности, вывод о принципиальной невозможности создания искусственного интеллекта на основе современных вычислительных устройств, даже в том случае, если появление квантовых компьютеров приведет к грандиозному прорыву в области вычислительной техники. Дело в том, что любой компьютер может лишь всё более детально моделировать работу формально-логической, «вычислительной» деятельности человеческого сознания, но «невычислительные» способности интеллекта ему недоступны.
Такова лишь небольшая часть естественнонаучных и философских споров, вызванных опубликованной 75 лет назад математической теоремой молодого Гёделя. Вместе с другими великими современниками он заставил человека иначе взглянуть на окружающий мир и на самого себя. Величайшие открытия первой трети ХХ века, в том числе теорема Гёделя, а также создание теории относительности и квантовой теории, показали ограниченность механистически-детерминистской картины природы, созданной на основе научных исследований двух предшествующих столетий. Оказалось, что и пути развития мироздания, и нравственные императивы подчиняются принципиально другим закономерностям, где имеют место и неустранимая сложность, и неопределенность, и случайность, и необратимость.
Однако последствия великого научного переворота не исчерпываются уже упомянутыми. К началу ХХ века идеи лапласовско-ньютоновского детерминизма оказывали огромное влияние на развитие общественных наук. Вслед за корифеями классического естествознания, представлявшими природу в виде жесткой механической конструкции, где все элементы подчиняются строгим законам, а будущее может быть однозначно предсказано, если известно текущее состояние, жрецы деятели общественных наук рисовали человеческое общество, подчиненное непреложным закономерностям и развивающееся в заранее заданном направлении. Одной из последних попыток сохранить подобную картину мира был, по-видимому, марксизм-ленинизм, приверженный концепции «единственно верного научного учения», составной частью которого было «материалистическое понимание истории». Достаточно вспомнить ленинскую идею построения социалистического общества по типу «большой фабрики». Постепенно с огромным трудом идеи о сложности, случайности, неопределенности, утвердившиеся в естественнонаучной картине мироздания, стали проникать и в социальные и гуманитарные науки. В обществе непредрешенность реализуется через феномен личной свободы индивидуума. Именно присутствие в природе человека в качестве субъекта, осуществляющего вольный и непредсказуемый выбор, делает исторический процесс сложным и не подчиняющимся никаким непреложным законам вселенского развития.
Однако нельзя не заметить, что обретение новой картины сложного мира в нашей стране происходило с огромным трудом. Господствовавшая семь десятилетий идеология тяготела к детерминизму лапласовского типа как философии всеобщего авторитарного порядка. Именно такой принцип предопределенности лежал в основе мечты, никогда не покидавшей правящую советскую бюрократию, об обществе-фабрике, управляемой жесткими законами иерархии. И поэтому всякий раз, как речь заходила о сложности, плюрализме, разнообразии, будь то теория относительности, квантовая механика, генетика, кибернетика, социологические исследования, психоанализ и т. д., — сразу включался механизм идеологической цензуры, который имел своей целью изгнать все упоминания о свободе и из природы, и из общества. Увы, косное наследие до сих пор мрачной тенью довлеет над умами многих наших соотечественников и современников. Свидетельством тому — инициируемые властью мучительные поиски новой «национальной идеологии», которая могла бы занять место, освободившееся в связи с кончиной коммунистической доктрины.
Так Курт Гёдель и его великие современники заставили нас по-новому взглянуть и на «звездное небо над головой, и на нравственный закон внутри нас», и на общество, в котором мы живем
машина Поста
История конечных автоматов: машина Поста и машина Тьюринга. Машина Поста – абстрактная вычислительная машина, предложенная Постом (Emil L.Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
В 1935 американский математик Пост опубликовал в «Журнале символической логики» статью Финитные комбинаторные процессы, формулировка 1. В этой статье и появившейся одновременно в Трудах Лондонского математического общества статье английского математика Тьюринга О вычислимых числах с приложением к проблеме решения были даны первые уточнения понятия «алгоритм». Важность идей Поста состоит в том, что был предложен простейший способ преобразования информации, именно он построил алгоритмическую систему (алгоритмическая система Поста). Пост доказал, что его система обладает алгоритмической полнотой. В 1967 профессор В.Успенский пересказал эти статьи с новых позиций. Он ввел термин «машина Поста». Машина Поста – абстрактная машина, которая работает по алгоритмам, разработанным человеком, она решает следующую проблему: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима. В 1970 машина Поста была разработана в металле в Симферопольском университете. Машина Тьюринга была построена в металле в 1973 в Малой Крымской Академии Наук.
Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V». У машины есть головка, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, либо проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста. Работа машины Поста заключается в том, что головка передвигается вдоль ленты (на одну клетку за один шаг) влево или вправо, наносит или стирает метки, а также распознает, есть ли метка в клетке в соответствии с заданной программой, состоящей из отдельных команд.
Машина Тьюринга состоит из счетной ленты (разделенной на ячейки и ограниченной слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного исполнительного устройства, которое может находиться в одном из дискретных состояний q0, q1, …, qs , принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний), при этом q0 называется начальным состоянием. Читающая и пишущая головка может читать буквы рабочего алфавита A = {a0, a1, …, at }, стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множества А. Чаще всего встречается буква а0 – «пробел». Головка находится в каждый момент времени над некоторой ячейкой ленты – текущей рабочей ячейкой. Лентопротяжный механизм может перемещать ленту так, что головка оказывается над соседней ячейкой ленты, при этом возможна ситуация выхода за левый край ленты, которая является аварийной (недопустимой), или машинного останова, когда машина выполняет предписание об остановке
Клини
Стивен Коул Клини (р.5.1.1909, Хартфорд, штат Коннектикут), американский логик и математик. В 1934 получил степень доктора философии в Принстонском университете. Профессор Висконсинского университета (Мадисон) с 1948. Основные работы посвящены теории алгоритмов и рекурсивных функций, а также проблемам интуиционистской логики и математики. В частности, им доказана эквивалентность введённого А. Чёрчем понятия l-определимости функций с общерекурсивностью. Введённое К. понятие (рекурсивной) реализуемости формул лежит в основе интуиционистской интерпретации арифметических суждений. Клини — автор ряда широко известных монографий по математической логике, основаниям математики и теории рекурсивных функций
План работы
- Поиск информаций(с 26января -9февраля)
- Структуриравание инфоромаций
- Создани и оформлений страницы на сайте
- Создание презентаций
