LOGO Необходимость уточнения понятия алгоритм

Длительное время интуитивного понятия алгоритма было достаточно

Пусть имеется массовая задача Если найден алгоритм (в интуитивном смысле) для ее решения, то не требуется другого определения алгоритма

Если после длительных попыток нахождения алгоритма возникает гипотеза, что такого алгоритма не существует, то доказать эту гипотезу на основе интуитивного определения алгоритма нельзя

Для доказательства несуществования алгоритма необходимо располагать точным определением понятия алгоритм

В 1900 году Давид Гильберт на 2-м Международном математическом конгрессе в Париже огласил 23 трудных математических проблемы Пример Давид Гильберт ( ) – выдающийся немецкий математик-универсал. В е годы (после смерти Анри Пуанкаре) был признанным мировым лидером математиков

Десятая проблема Гильберта Найти алгоритм, применение которого к алгебраическому уравнению с целыми коэффициентами (с произвольным числом неизвестных) приводило бы к результату «да», если уравнение имеет целые решения и к результату «нет» – в противном случае

Десятая проблема Гильберта Для частного случая (уравнения с одним неизвестным) такой алгоритм есть Если уравнение с целыми коэффициентами имеет целый корень, то он обязательно является делителем свободного члена a n

Десятая проблема Гильберта Можно предложить такой алгоритм: 1)Найти все делители a n : d 1, d 2, …, d k 2)Вычислить P n (x) для каждого d i, i = 1..k 3)Если P n (d i ) = 0, то d i – корень уравнения

В 1970 году ленинградский ученый Ю.В. Матиясевич успешно завершил работу ряда математиков над доказательством того, что требуемый алгоритм невозможен Юрий Владимирович Матиясевич (род ) – советский и российский математик, исследователь Санкт-Петербургского отделения Математического института им. В.А. Стеклова РАН, академик РАН, доктор физико-математических наук. Внес существенный вклад в теорию вычислимости, завершив решение десятой проблемы Гильберта Десятая проблема Гильберта

Направления формализации понятия алгоритм

Алонзо Чёрч ( ) – американский математик и логик. Разработал теорию лямбда- исчислений, которая позволила показать существование т.н. «неразрешимых задач» Вместе с Тьюрингом показал, что лямбда-исчисления и машина Тьюринга имеют одинаковые свойства – тезис Чёрча-Тьюринга 1. Рекурсивные функции Стивен Коул Клини ( ) – американский математик. Участвовал в разработке теории вычислимости, известен изобретением регулярных выражений, внес важный вклад в теорию конечных автоматов

Курт Фридрих Гёдель ( ) – австрийский логик, математик и философ математики. Наиболее известный по сформулированной и доказанной им теоремой о неполноте (1931 г.) Теорема о неполноте: Любая эффективно аксиоматизируемая теория, в достаточно богатом языке, достаточном для определения натуральных чисел и операций сложения и умножения является неполной либо противоречивой. Неполнота означает наличие высказываний, которые нельзя ни доказать, ни опровергнуть, исходя из аксиом этой теории. Противоречивость возможность доказать любое высказывание: как истинное так и ложное. 1. Рекурсивные функции

Курт Фридрих Гёдель ( ) – австрийский логик, математик и философ математики. Кроме того, Гёдель написал работу по общей теории относительности, в которой предложил вариант решения уравнений Эйнштейна, из которого следует, что строение вселенной может иметь такое устройство, в котором течение времени является закольцованным (метрика Гёделя), что теоретически допускает путешествия во времени. Большинство современных физиков считают это решение верным лишь математически и не имеющим физического смысла. 1. Рекурсивные функции

В алгоритмическом процессе вычисляется значение некоторой функции f(x 1, x 2, …, x n ), определенной на множестве натуральных чисел Понятие алгоритма отождествляется со строгим математическим понятием «частично рекурсивная функция»

Алан Тьюринг ( ) – английский математик, логик и криптограф. Предложенная им в 1936 году абстрактная вычислительная машина Тьюринга позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследованиях 2. Машина Тьюринга Теорема Гёделя о неполноте побудила Тьюринга доказать, что нет общего метода определения истинности и, таким образом, математика всегда будет содержать недоказуемые высказывания

Алан Тьюринг ( ) – английский математик, логик и криптограф. 2. Машина Тьюринга Во время Второй мировой войны Тьюринг работал криптографом для раскрытия кода немецкой военной шифровальной машины «Энигма». Немцы пребывали в уверенности, что их система неуязвима. Но опираясь на работы польских математиков, А.Тьюринг совместно с У.Уэлчманом раскрыл шифры, создав дешифровочную машину «Бомба».

Эмиль Леон Пост ( (Польша) ) – американский математик и логик. Предложил абстрактную машину Поста 2. Машина Тьюринга Машина Поста отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

2. Машина Тьюринга Алгоритмический процесс – работа некоторой «абстрактной вычислительной машины». Каждая отдельная машина Тьюринга выполняет только один алгоритм Лучше подходит термин «программа машины Тьюринга» – набор инструкций, упрощенных до однотипной схемы Все машины Тьюринга отличаются программами, а общим является описание исполнителя (человек- вычислитель, действующий бездумно и неукоснительно, как машина)

3. Нормальные алгорифмы Маркова Алгоритмический процесс – переработка слов некоторого алфавита с помощью точно описанных правил переработки Андрей Андреевич Марков (младший) ( ) – советский математик, сын известного русского математика А.А.Маркова, основоположник советской школы конструктивной математики, автор понятия нормального алгоритма (1947 г.)

В последствии оказалось, что эти три варианта определения понятия алгоритма равносильны

Литература 1.Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, с. 2.Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, с. 3.Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, с. 4.ВикипедиЯ. Свободная энциклопедия.

Многие готовы скорее умереть, чем подумать. Часто, кстати, так и бывает. Бертран Рассел