Алгоритмически неразрешимые проблемы реферат
Обновлено: 17.05.2024
Теперь задумаемся вот о чём. Каждый раз, когда мы строили программу для новой Машины Тьюринга, даже если мы при этом использовали программы для других машин, не явно предполагалось, что как-то, где-то, кем-то строилась каретка, обладающая заданным набором состояний, способная распознавать и записывать символы из заданного алфавита и т.п. Построение такой каретки - сама по себе задача не из простых. Для каждого нового алгоритма мы вынуждены строить новый исполнитель. Это выглядит примерно так, как если бы для каждой новой программы нам надо было строить новый компьютер.
А нельзя ли построить такой исполнитель, который был бы способен выполнить любой алгоритм, заданный в виде программы для Машины Тьюринга? Положительный ответ на этот вопрос являлся бы математическим обоснованием существования универсального вычислителя, т.е. способного выполнить любой должным образом записанный алгоритм, вычислить любую вычислимую функцию.
Итак, пусть нам надо построить Универсальную Машину Тьюринга, назовём её УМТ, для которой:
исходными данными являются программа другой машины, назовём её МТ, с исходными данными Д последней;
результат применения УМТ к этим исходным данным должен быть таким же, как применение МТ к её исходным данным, то есть
Из-за чисто технической громоздкости мы не будем давать полного доказательства существования УМТ, а дадим лишь обоснование её существования. В этом обосновании мы покажем основную идею доказательства.
Представим себя в качестве такой УМТ и опишем в интуитивной форме алгоритм своей работы. Состояние воображаемой каретки будем записывать под обозреваемой ячейкой ленты. Программу имитируемой МТ считаем пока заданной в виде таблицы.
Интерпретирующий алгоритм для УМТ:
Обозревай ячейку, под которой написана буква (состояние);
Отыщи в таблице строку, обозначенную этой буквой;
В найденной строке обозревай тройку символов, которая стоит на пересечении со столбцом, обозначенным буквой, вписанной в обозреваемую ячейку;
Замени букву в обозреваемой ячейке на первую букву тройки;
Если второй буквой тройки является “!”, то стоп;
Если в обозреваемой ячейке третья буква “Н”, то сотри букву под обозреваемой ячейкой и запиши туда вторую букву тройки (смена состояния);
Если в обозреваемой тройке третья буква “Л”, то сотри букву под обозреваемой ячейкой, сдвинься влево и запиши под этой ячейкой вторую букву тройки;
Если в обозреваемой тройке третья буква “П”, то сотри букву под обозреваемой ячейкой, сдвинься вправо и запиши под этой ячейкой вторую букву тройки;
Перейди к шагу 1.
Для того, чтобы преобразовать это описание в программу Машины Тьюринга, надо решить две основные проблемы:
Как задавать программу и конфигурацию имитируемой МТ на ленте?
Так как произвольная МТ может иметь произвольный алфавит, то какой алфавит должен быть у УМТ?
Первая проблема разбивается на две:
как задать программу на ленте?
как задать конфигурацию, чтобы отмечать текущее положение каретки имитируемой МТ (решение в виде символа под текущей ячейкой не годится).
Программу МТ будем записывать пятерками
aqbp*, где a,bÎD; p,qÎQ; *Î,
здесь a- символ , соответствующий строке таблицы;
q - столбцу таблицы.
На рисунке 4.1. показана линейная запись функциональной схемы для U1 (n).
Рис. 4.1. Линейная запись функциональной схемы МТ, вычисляющей U1 (n).
Такое представление программы обеспечивает взаимнооднозначное соответствие с табличной формой записи, а стало быть ничего из таблицы при этом не теряется и ничего не добавляется.
Как задать на ленте конфигурацию имитируемой машины? Напомним, что под конфигурацией Машины Тьюринга мы понимаем слово на ленте и положение каретки по отношению к слову. Здесь основная трудность: где записывать символ текущего состояния каретки.
Будем записывать символы исходного слова на ленте через ячейку. В образовавшиеся пустые ячейки ленты будем записывать справа от обозреваемого символа текущее состояние каретки.
Теперь рассмотрим проблему алфавита. Напомним, эта проблема состоит в том, что УМТ должна иметь определенный алфавит, который не может изменяться. В то же время мы не можем знать заранее, с какими алфавитами будут работать МТ, которые будет интерпретировать наша УМТ. Решение этой проблемы - кодирование символов из алфавита МТ символами алфавита УМТ. При этом важно позаботиться о том, чтобы:
один и тот же символ из алфавита МТ всегда изображался одной и той же последовательностью символов из алфавита УМТ;
разные символы из алфавита МТ всегда изображались разными последовательностями символов из алфавита УМТ.
В качестве алфавита УМТ выберем алфавит , расширенный небольшим количеством вспомогательных символов. Пусть нам надо закодировать символы МТ, у которой |DМТ |=k; |QМТ |=m.
Возьмем 3+k+m слов вида 1000……01, т.е. последовательность нулей между единицами. Эти слова мы будем называть кодовыми группами (КП). На рисунке 4.2 показаны кодовые КП для символов из D, Q, и
100001 Здесь число нулей всегда четно.
1000001 Здесь всегда нечетное число нулей
Рис. 4.2 Кодовые КП для символов из D, Q, и
Теперь для доказательства теоремы надо интерпретирующий алгоритм записать в терминах кодовых групп, шифра программы и шифра конфигурации. Например, шаг 1 будет звучать теперь так:
Обозревай в шифре конфигурации КП, расположенную левее КП, с нечётным числом нулей, т.е. код текущего состояния каретки (заметим, что такая КП в шифре конфигурации всегда одна. Убедитесь в этом).
Шаги 2 и 3 примут следующий вид:
Отыщем в шифре функциональной схемы пару соседних КП, совпадающих с парой КП в шифре конфигурации, в которой первая КП - обозреваемая и т. д.
Для каждого шага интерпретирующего алгоритма надо построить МТ с алфавитом , после чего объединить их должным образом, с помощью операций o, ||, if-then-else, while-do.
Разрешимость алгоритмических проблем.
В этом разделе мы дадим примеры доказательства неразрешимости конкретной алгоритмической проблемы - проблемы самоприменимости.
Определение 4.1: Алгоритмической проблемой называется проблема построения алгоритма для решения класса задач.
Естественно возникает вопрос: Всякая ли алгоритмическая проблема разрешима? Вплоть до начала ХХ века среди математиков существовала уверенность в разрешимости любой математической проблемы. Как уже отмечалось во введении, Лейбниц был один из первых, кто пришёл к идее исчисления. Он считал, что решение математической проблемы сводится к манипуляции с символами с помощью специальным образом подобранными правилами вывода (замены одних комбинаций символов на другие). Проблема, по мнению Лейбница, состояла лишь в том, чтобы построить надлежащим образом систему этих правил. Более того - он считал, что можно построить универсальный набор правил для решения любой математической проблемы. Джонатан Свифт в своей книге “Приключения Гулливера” подшутил над этой идеей Лейбница в образе мудреца, вращающего колёса с табличками в поисках нужного решения.
Английский математик Чёрч первым дал пример неразрешимой поблемы, известной как проблема выводимости.
Дана система правил подстановки R и два слова W и S. Можно ли определить выводимо W из S с помощью R?
Чёрч доказал, что не существует алгоритма, который бы для любой системы правил подстановки и любых двух слов давал ответ на этот вопрос.
Другой известный нам пример неразрешимой алгоритмической проблемы - 10-я проблема Гильберта.
Определение 4.2. Алгоритм А называется самоприменимым, если он применим к слову, которое является его описанием.
Дано описание алгоритма А. Требуется построить такой алгоритм, который бы для описания любого алгоритма А определял , является ли алгоритм А самоприменимым или нет.
Теорема 4.1. Распознавание самоприменимости алгоритмически неразрешимо.
Доказательство: Доказывать эту теорему будем методом от противного. Пусть алгоритм А, распознающий самоприменимость, существует. Тогда откорректируем его так, чтобы
s - если А - самоприменим
t - если А - не самоприменим, где А - некоторый алгоритм
Построим, имея А, алгоритм В, который
не останавливается, если А самоприменим
t - если А - не самоприменим
Таким образом, В применим к самонеприменимым алгоритмам и не применим к самоприменимым.
Рассмотрим В(В), т. е. Применение В к самому себе. Если В(В) даёт t, следовательно, В - самоприменим, но по построению В даёт t только на не самоприменимых авлгоритмах. Если В(В) не останавливается, то это означает, что В - не самоприменим, но по построению в этом случае он должен дать t. Пришли к противоречию. Следовательно, такой алгоритм В не существует. Следовательно, не может существовать и алгоритм А. Отсюда - предположение о существовании алгоритма А, распознающего самоприменимость, неверно!
Замечание: обычно доказательство неразрешимости алгоритмической проблемы строится методом сведения. Идея этого метода состоит в том, что для исследуемой проблемы П доказывается, что она сводится к другой проблеме П ¢ , о которой известно, что она неразрешима.
Взаимосвязь алгоритмических систем.
В связи с существованием неразрешимых алгоритмических проблем возникает вопрос:
А не может ли оказаться так, что алгоритмическая проблема, неразрешимая в одной алгоритмической системе, окажется разрешимой в другой? Например, какая-то проблема, не разрешимая в терминах машины Тьюринга, окажется разрешимой в терминах НАМ.
Определение 4.3. Две алгоритмические системы называются эквивалентными, если множество алгоритмов, которые можно описать в первой системе, эквивалентно множеству алгоритмов, которое можно описать с помощью второй.
В следствии тезисов Тьюринга и Маркова, машины Тьюринга и нормальные алгоритмы Маркова - эквивалентные алгоритмические системы, т. к. они описывают одно и то же множество алгоритмов, соответствующих вычислимым функциям.
В этом разделе на примере МТ и НАМ мы покажем, что для эквивалентных алгоритмических систем, не может оказаться так, что какая-то алгоритмическая проблема, неразрешимая в МТ, окажется разрешимой в НАМ. Мы докажем, что для любой МТ U можно подобрать НАМ N такой, что
U(P)=N(P) и наоборот.
Отсюда и будет следовать, что если какая-то алгоритмическая проблема разрешима в МТ, то она автоматически разрешима в НАМ и наоборот.
Теорема 4.2 Для любой машины Тьюринга U существует НАМ N такой, что
Доказательство: Для доказательства этой теоремы мы покажем, как для каждого правила ap®bqw машины U построить правило подстановки для НАМ N. Тем самым мы, зная функциональную схему U, построим систему правил для N.
В функциональной схеме машины U могут встретиться команды следующих видов:
Рассмотрим сначала команды машины U вида (1), т. е. запись в текущую позицию вместо символа a символа b и сдвиг влево. В соответствующем НАМ N мы будем обрабатываемый символ в слове р метить слева символом состояния т. е. DN =DU UQU U. Тогда команде (1) сопоставим следующую группу правил подстановки:
Здесь символ Ñ “экранирует” q от следующего за ним символа в обрабатываемом слове.
Командам вида (2) сопоставим правила подстановки вида
Командам вида (4) - qj aab.
Самым последним в системе правил подстановки НАМ будет начальное правило
где qo - начальное состояние U.
Замечание: Если а=L, т. е. командам Lqj ®bqs w надо будет сопоставлять правило qj ®qs b либо qj ®bqs в зависимости от значения w. Все такие правила подстановки надо собрать в конце схемы, сразу перед начальным правилом.
Обратите внимание, что если на вход N подать слово, к которому U не применим, то N будет бесконечно долго подставлять qo в начало слова.
N применим к тем же словам, что и U.
Допустим существование слова Р, к которому U применим, а N - нет. Раз U применим, то пусть его заключительной командой является команда aq®b!H. Ей по построению N соответствует терминальное правило подстановки, которое должно выполняться, т. к. в схеме N нет двух правил с одинаковыми правыми частями..
Пришли к противоречию.
Доказательство теоремы 4.2 закончено.
Теорема 4.3. Для любого НАМ N существует машина Тьюринга U такая, что
U*(Р)=*Р, т. е. МТ , ставящую символ * перед обрабатываемым символом.
U! (P)=P осталось без изменения слова.
1 || Q*aR если QaR=P
0 || P* если a не входит в P
Надеемся, что читателю будет не сложно построить функциональную схему любой из этих машин.
Схема НАМ N состоит из правил либо вида a®b, либо aab, где
a,b Є (DUW) * .
Каждому правилу вида
сопоставим машину Ui c функциональной схемой вида
if then mb i (1||Q*ai R)o U * o U1
Каждому терминальному правилу вида
сопоставим машину Ui c функциональной схемой вида
if then mb i (1||Q*ai R) o U!
Последнему правилу подстановки в схеме НАМ N вида
сопоставим машину Uk с функциональной схемой
if then mb k (1||Q*ak R)o U*o U1
В части else появление машины U! связано с тем, что по определению НАМ завершается, если не применимо ни одно из правил подстановки.
Функциональная схема искомой машины U будет иметь вид
где k - число правил подстановки в схеме НАМ N.
Доказательство теоремы 4.3 закончено.
Из теорем 4.2 и 4.3 следует, что если какая-то алгоритмическая проблема разрешима в одной алгоритмической системе, то она автоматически разрешима и в другой. Если предположить, что какая-то алгоритмическая проблема неразрешимая в одной алгоритмической системе, но разрешима в другой, то придём к противоречию. Действительно, согласно теоремам 4.2 и 4.3 если эта проблема разрешима хотя бы в одной системе, то она разрешима и в другой.
Для любой алгоритмической системы существует универсальный исполнитель, который есть интерпретатор множества действий заданной алгоритмической системы.;
В силу тезиса Тьюринга, любой алгоритм реализуем в терминах действий последовательной, параллельной композиций, выбора и цикла и базового набора действий;
Проблема самоприменимости алгоритмической системы алгоритмически не разрешима;
Если алгоритмическая проблема не разрешима, то она не разрешима в любой другой эквивалентной алгоритмической системы;
Алгоритмические системы МТ и НАМ эквивалентны.
Что такое интерпретация?
Что такое кодирование?
В чем проблема линеаризации Ф.с. для МТ?
Что такое универсальный исполнитель:
- он может исполнять заданный А в любой А.с.?
- он может исполнять любой А, выразимый в данной А.с.?
Как решается проблема произвольности алфавита в УМТ?
Самоприменимость - что это такое?
А.п. самоприменимости разрешима?
В МТ А не закончен если нет применимого правила, в НАМ в этом случае А - закончен. Как это несоответствие решается при доказательстве сводимости МТ к НАМ и наоборот?
Введение
1. Описание машины Тьюринга
1.1 Свойства машины Тьюринга как алгоритма
2. Сложность алгоритмов
2.1 Сложность проблем
3. Машина Тьюринга и алгоритмически неразрешимые проблемы
4. Реализация машины Тьюринга
5. Практическая часть
Заключение
Список литературы
Вложенные файлы: 1 файл
курсач по мат логике Машина Тьуринга.doc
Министерство образования и науки Российской Федерации
Чебоксарский политехнический институт (филиал)
Кафедра высшей и прикладной математики
студент 2 курса (в/в)
Майоров Александр Геннадьевич
учебный шифр 612256
ст. преподаватель Павлова Н.А
1. Описание машины Тьюринга
1.1 Свойства машины Тьюринга как алгоритма
2. Сложность алгоритмов
2.1 Сложность проблем
3. Машина Тьюринга и алгоритмически неразрешимые проблемы
4. Реализация машины Тьюринга
5. Практическая часть
Машина Тьюринга – это очень простое вычислительное устройство. Она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещается вдоль ленты и способна читать и записывать символы. Также у машины Тьюринга есть такая характеристика, как состояние, которое может выражаться целым числом от нуля до некоторой максимальной величины. В зависимости от состояния машина Тьюринга может выполнить одно из трех действий: записать символ в ячейку, передвинуться на одну ячейку вправо или влево и установить внутреннее состояние.
Устройство машины Тьюринга чрезвычайно просто, однако на ней можно выполнить практически любую программу. Для выполнения всех этих действий предусмотрена специальная таблица правил, в которой прописано, что нужно делать при различных комбинациях текущих состояний и символов, прочитанных с ленты.
В 1937 г. Алан Тьюринг расширил определение, описав "универсальную машину Тьюринга". Позже для решения определенных классов задач была введена ее разновидность, которая позволяла выполнять не одну задачу, а несколько.
Целью данной работы было дать описание реализации машины Тьюринга и выполнить соответствующую практическую часть работы.
1. Описание машины Тьюринга
Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью "О вычислимых числах в приложении к проблеме разрешения", которая наравне с работами Поста и Черча лежит в основе современной теории алгоритмов.
Предыстория создания этой работы связана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача доказательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как "проблему разрешимости" – нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики.
Статья Тьюринга как раз и давала ответ на эту проблему – вторая проблема Гильберта оказалась неразрешимой. Но значение статьи Тьюринга выходило далеко за рамки той задачи, по поводу которой она была написана.
Приведем характеристику этой работы, принадлежащую Джону Хопкрофту: "Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т.е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга".
Машина Тьюринга является расширением модели конечного автомата, расширением, включающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу.
Формально машина Тьюринга может быть описана следующим образом. Пусть заданы:
конечное множество состояний – Q, в которых может находиться машина Тьюринга;
конечное множество символов ленты – Г;
функция δ (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии qi и обозревает символ gi) в тройку декартова произведения Q х Г х (машина переходит в состояние qi, заменяет символ gi на символ gj и передвигается влево или вправо на один символ ленты) – Q x Г-->Q х Г х
один символ из Г-->е (пустой);
подмножество Σ є Г – -> определяется как подмножество входных символов ленты, причем е є (Г – Σ);
одно из состояний – q0 є Q является начальным состоянием машины.
Решаемая проблема задается путем записи конечного количества символов из множества Σ є Г – Si є Σ на ленту:
после чего машина переводится в начальное состояние и головка устанавливается у самого левого непустого символа (q0,w) –, после чего в соответствии с указанной функцией переходов (qi,Si) – ->(qj,Sk, L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.
Остановка машины происходит в том случае, если для пары (qi,Si) функция перехода не определена.
Алан Тьюринг высказал предположение, что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Это предположение известно как тезис Черча–Тьюринга. Каждый компьютер может моделировать машину Тьюринга (операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения состояния машины). Следовательно, он может моделировать алгоритмы в любом формализме, и из этого тезиса следует, что все компьютеры (независимо от мощности, архитектуры и т.д.) эквивалентны с точки зрения принципиальной возможности решения алгоритмических задач.
1.1 Свойства машины Тьюринга как алгоритма
На примере машины Тьюринга хорошо прослеживаются свойства алгоритмов. Попросите учащихся показать, что машина Тьюринга обладает всеми свойствами алгоритма.
Дискретность. Машина Тьюринга может перейти к (к + 1) – му шагу только после выполнения каждого шага, т.к именно каждый шаг определяет, каким будет (к + 1) – й шаг.
Понятность. На каждом шаге в ячейку пишется символ из алфавита, автомат делает одно движение (Л, П, Н), и машина Тьюринга переходит в одно из описанных состояний.
Детерминированность. В каждой клетке таблицы машины Тьюринга записан лишь один вариант действия. На каждом шаге результат определен однозначно, следовательно, последовательность шагов решения задачи определена однозначно, т.е. если машине Тьюринга на вход подают одно и то же входное слово, то выходное слово каждый раз будет одним и тем же.
Результативность. Содержательно результаты каждого шага и всей последовательности шагов определены однозначно, следовательно, правильно написанная машина Тьюринга за конечное число шагов перейдет в состояние q0, т.е. за конечное число шагов будет получен ответ на вопрос задачи.
Массовость. Каждая машина Тьюринга определена над всеми допустимыми словами из алфавита, в этом и состоит свойство массовости. Каждая машина Тьюринга предназначена для решения одного класса задач, т.е. для каждой задачи пишется своя (новая) машина Тьюринга.
2. Сложность алгоритмов
Сложность алгоритма определяется вычислительными мощностями, необходимыми для его выполнения. Вычислительная сложность алгоритма часто измеряется двумя параметрами: Т (временная сложность) и S (пространственная сложность, или требования к памяти). И Т, и S обычно представляются в виде функций от n, где n – это размер входных данных. (Существую и другие способы измерения сложности: количество случайных бит, ширина канала связи, объем данных и т.п.)
Временная сложность измеренная таким образом не зависит от реализации. Не нужно знать ни точное время выполнения различных инструкций, ни число битов, используемых для представления различных переменных, ни даже скорость процессора. Один компьютер может быть на 50 процентов быстрее другого, а у третьего шина данных может быть в два раза шире, но сложность алгоритма, оцененная по прядку величины, не изменится. Это не жульничество, при работе с алгоритмами настолько сложными, как описанные в этой книге, всем прочим можно пренебречь (с точностью до постоянного множителя) в сравнении со сложностью по порядку величины.
Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему памяти. Например, если Т= О(n), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т=О(2n), то добавление одного бита к входным данным удвоит время выполнения алгоритма.
Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от n: 0(1). Алгоритм является линейным, если его временная сложность О(n). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы – полиноминальны, их сложность – О(m), где m – константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем
Алгоритмы, сложность которых равна О(tf(n)), где t – константа, большая, чем 1, a f(n) – некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна О(сf(n)), где с – константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиноминальным.
В идеале, криптограф хотел бы утверждать, что алгоритм, лучший для взлома спроектированного алгоритма шифрования, обладает экспоненциальной временной сложностью. На практике, самые сильные утверждения, которые могут быть сделаны при текущем состоянии теории вычислительной сложности, имеют форму "все известные алгоритмы вскрытия данной криптосистемы обладают суперполиномиальной временной сложностью". То есть, известные нам алгоритмы вскрытия обладают суперполиномиальной временной сложностью, но пока невозможно доказать, что не может быть открыт алгоритм вскрытия с полиномиальной временной сложностью. Развитие теории вычислительной сложности возможно когда-нибудь позволит создать алгоритмы, для которых существование алгоритмов с полиномиальным временем вскрытия может быть исключено с математической точностью.
С ростом n временная сложность алгоритмов может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма.
При условии, что единицей времени для нашего компьютера является микросекунда, компьютер может выполнить постоянный алгоритм за микросекунду, линейный – за секунду, а квадратичный – за 11.6 дня. Выполнение кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция которого позволила бы ему противостоять следующему ледниковому периоду, в конце концов получил бы решение. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста мощи компьютеров, параллельной обработки или контактов с инопланетным суперразумом.
Взглянем на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность такого вскрытия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если n – длина ключа, то сложность вскрытия грубой силой равна 0(2n). Сложность вскрытия грубой силой при 56-битовом ключе составляет 256, а при 112-битовом ключе – 2112. В первом случае вскрытие возможно, а во втором – нет.
2.1 Сложность проблем
Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. Теория рассматривает минимальное время и объем памяти, необходимые для решения самого трудного варианта проблемы на теоретическом компьютере, известном как машина Тьюринга. Машина Тьюринга представляет собой конечный автомат с бесконечной лентой памяти для чтения записи и является реалистичной моделью вычислений.
Проблемы, которые можно решить с помощью алгоритмов с полиномиальным временем, называются решаемыми, потому что для разумных входных данных обычно могут быть решены за разумное время. (Точное определение "разумности" зависит от конкретных обстоятельств) Проблемы, которые невозможно решить за полиномиальное время, называются нерешаемыми, потому что вычисление их решений быстро становится невозможным. Нерешаемые проблемы иногда называют трудными. Проблемы, которые могут быть решены только с помощью суперполиномиальных алгоритмов, вычислительно нерешаемы, даже при относительно малых значениях n.
Что еще хуже, Алан Тьюринг доказал, что некоторые проблемы принципиально неразрешимы. Даже отвлекаясь от временной сложности алгоритма, невозможно создать алгоритм решения этих проблем.
Задачи можно разбить на классы в соответствии со сложностью их решения. Вот важнейшие из них и предполагаемые соотношения между ними: P
За время своего существования человечество придумало множество алгоритмов для решения разнообразных практических и научных проблем. Зададимся вопросом – а существуют ли какие-нибудь проблемы, для которых невозможно придумать алгоритмы их решения?
Утверждение о существовании алгоритмически неразрешимых проблем является весьма сильным – мы констатируем, что мы не только сейчас на знаем соответствующего алгоритма, но мы не можем принципиально никогда его найти.
Успехи математики к концу XIX века привели к формированию мнения, которое выразил Д. Гильберт – "в математике не может быть неразрешимых проблем", в связи с этим формулировка проблем Гильбертом на конгрессе 1900 года в Париже была руководством к действию, констатацией отсутствия решений в данный момент.
Первой фундаментальной теоретической работой, связанной с доказательством алгоритмической неразрешимости, была работа Курта Геделя – его известная теорема о неполноте символических логик. Это была строго формулированная математическая проблема, для которой не существует решающего ее алгоритма. Усилиями различных исследователей список алгоритмически неразрешимых проблем был значительно расширен. Сегодня принято при доказательстве алгоритмической неразрешимости некоторой задачи сводить ее к ставшей классической задаче – "задаче останова".
Имеет место быть следующая теорема: не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.
Таким образом, фундаментально алгоритмическая неразрешимость связана с бесконечностью выполняемых алгоритмом действий, т.е. невозможностью предсказать, что для любых исходных данных решение будет получено за конечное количество шагов.
Тем не менее, можно попытаться сформулировать причины, ведущие к алгоритмической неразрешимости, эти причины достаточно условны, так как все они сводимы к проблеме останова, однако такой подход позволяет более глубоко понять природу алгоритмической неразрешимости:
а) Отсутствие общего метода решения задачи
Проблема 1: Распределение девяток в записи числа;
Определим функцию f(n) = i, где n – количество девяток подряд в десятичной записи числа, а i – номер самой левой девятки из n девяток подряд: =3,141592… f(1) = 5.
Задача состоит в вычислении функции f(n) для произвольно заданного n.
Поскольку число является иррациональным и трансцендентным, то мы не знаем никакой информации о распределении девяток (равно как и любых других цифр) в десятичной записи числа. Вычисление f(n) связано с вычислением последующих цифр в разложении, до тех пор, пока мы не обнаружим n девяток подряд, однако у нас нет общего метода вычисления f(n), поэтому для некоторых n вычисления могут продолжаться бесконечно – мы даже не знаем в принципе (по природе числа) существует ли решение для всех n.
Проблема 2: Вычисление совершенных чисел;
Определим функцию S(n) = n-ое по счету совершенное число и поставим задачу вычисления S(n) по произвольно заданному n. Нет общего метода вычисления совершенных чисел, мы даже не знаем, множество совершенных чисел конечно или счетно, поэтому наш алгоритм должен перебирать все числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос о останове алгоритма. Если мы проверили М чисел при поиске n-ого совершенного числа – означает ли это, что его вообще не существует?
Проблема 3: Десятая проблема Гильберта;
Пусть задан многочлен n-ой степени с целыми коэффициентами – P, существует ли алгоритм, который определяет, имеет ли уравнение P=0 решение в целых числах?
Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий метод определения целых корней уравнения P=0 по его целочисленным коэффициентам.
б) Информационная неопределенность задачи
Проблема 4: Позиционирование машины Поста на последний помеченный ящик;
Пусть на ленте машины Поста заданы наборы помеченных ящиков (кортежи) произвольной длины с произвольными расстояниями между кортежами и головка находится у самого левого помеченного ящика. Задача состоит установке головки на самый правый помеченный ящик последнего кортежа.
Попытка построения алгоритма, решающего эту задачу приводит к необходимости ответа на вопрос – когда после обнаружения конца кортежа мы сдвинулись вправо по пустым ящикам на М позиций и не обнаружили начало следующего кортежа – больше на ленте кортежей нет или они есть где-то правее? Информационная неопределенность задачи состоит в отсутствии информации либо о количестве кортежей на ленте, либо о максимальном расстоянии между кортежами – при наличии такой информации (при разрешении информационной неопределенности) задача становится алгоритмически разрешимой.
в) Логическая неразрешимость (в смысле теоремы Геделя о неполноте)
Проблема 5: Проблема "останова" (см. теорема);
Проблема 6: Проблема эквивалентности алгоритмов;
По двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
Основные этапы развития астрономии. Гипотеза Лапласа: С точки зрения гипотезы Лапласа, это совершенно непонятно.
Что входит в перечень работ по подготовке дома к зиме: При подготовке дома к зиме проводят следующие мероприятия.
Основные научные достижения Средневековья: Ситуация в средневековой науке стала меняться к лучшему с.
Одним из свойств алгоритма является его массовость. Это означает, что алгоритм представляет собой способ решения некоторой массовой проблемы, формулируемой в виде проблемы отображения не одного, а целого множества входных слов в соответствующие им выходные слова. Таким образом, всякий алгоритм можно рассматривать как некоторое универсальное средство для решения целого класса задач.
Оказывается, что существуют такие классы задач, для решения которых нет и не может быть единого универсального приема. Проблемы решения такого рода задач называют алгоритмически неразрешимыми проблемами. Однако алгоритмическая неразрешимость проблемы решения задач того или иного класса вовсе не означает невозможность решения любой конкретной задачи из этого класса. Речь идет о невозможности решения всех задач данного класса одним и тем же приемом.
Таким образом, задачи (проблемы) можно разделить на алгоритмически разрешимые и алгоритмически неразрешимые. Примером алгоритмически разрешимой проблемы является проблема доказательства тождеств в обычной алгебре. Существует единый конструктивный прием (раскрытие скобок, приведение подобных членов), позволяющий за конечное число шагов решить, является ли любое заданное соотношение тождественным.
Переход от интуитивного понятия алгоритма к точному понятию рекурсивной функции (машины Тьюринга, нормального алгоритма) позволил доказать алгоритмическую неразрешимость ряда проблем.
Одним из первых результатов такого типа является доказательство неразрешимости проблемы распознавания выводимости в математической логике, выполненной Черчем в 1936 г. Результат этого доказательства формулируется как теорема Черча (5). Проблема распознавания выводимости алгоритмически неразрешима.
Тем самым не только выясняется причина безуспешности всех прошлых попыток создания соответствующего алгоритма, но и обнаруживается полная бессмысленность таких попыток. . Доказательство данной теоремы Черча рассматривать не будем ввиду его сложности. Отметим лишь, что суть его сводится к доказательству нерекурсивности функции, решающей данную задачу.
В качестве примера доказательства алгоритмической неразрешимости рассмотрим проблему распознавания самоприменимости. Существуют как самоприменимые, так и несамоприменимые алгоритмы. Примером самоприменимого алгоритма является так называемый тождественный алгоритм в любом алфавите А, содержащем две или более двух букв. Этот алгоритм применим к любому слову р в алфавите А и перерабатывает любое входное слово в себя.
Примером несамоприменимого алгоритма является так называемый нулевой алгоритм в любом конечном алфавите В. Этот алгоритм задается схемой, содержащей единственную подстановку ® у (где у—любая буква алфавита В). По своему определению он не применим ни к какому входному слову, а значит, и к своему изображению.
Проблема распознавания самоприменимости алгоритмов состоит в том, чтобы найти единый конструктивный прием, позволяющий за конечное число шагов по схеме любого данного алгоритма узнать, является алгоритм самоприменимым или несамоприменимым.
Доказательство алгоритмической неразрешимости данной проблемы будем проводить, используя алгоритмические системы Тьюринга.Для этого сформулируем проблему самоприменимости в терминах машины Тьюринга. Пусть в машине Тьюринга зафиксирована какая-нибудь конфигурация. Возможны два случая:
1) машина применима к этой конфигурации, т. е. после конечного числа тактов она останавливается в заключительной конфигурации;
2) машина не применима к этой конфигурации. Это означает, что машина никогда не переходит в заключительную конфигурацию, она впадает в бесконечный процесс.
Предположим теперь, что на ленте машины Тьюринга изображен ее собственный шифр (т. е. шифр таблицы соответствия и исходной конфигурации), записанный в алфавите машины. Если машина применима к такой конфигурации, то будем называть ее самоприменимой, в противном случае—несамоприменимой.
Тогда проблема распознавания самоприменимости состоит в следующем: по любому заданному шифру установить, к какому классу относится машина, зашифрованная им, — к классу самоприменимых или несамоприменимых?
Оказывается, можно доказать следующую теорему (6). Проблема распознавания самоприменимости алгоритмически неразрешима.
Доказательство. Предположим, напротив, что такая машина М существует. Тогда в М всякий самоприменимый шифр перерабатывается в какой-то символ v (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости), а всякий несамоприменимый шифр — в символ т (имеющий смысл отрицательного ответа на поставленный вопрос).
В таком случае можно было бы построить и такую машину М1, которая по-прежнему перерабатывает несамоприменймые шифры в t , в то время как к самоприменимым шифрам М1 уже не применима. Этого можно добиться путем такого изменения схемы машины (таблицы соответствия) M, чтобы после появления символа v вместо остановки машина стала бы неограниченно повторять этот же символ.
Итак, М1 применима ко всякому несамоприменимому шифру (вырабатывая при этом символ t ) и не применима к самоприменимым шифрам. Однако это приводит к противоречию.
1) пусть машина М1 самоприменима, тогда она применима к своему шифру M1' и перерабатывает его в символ t , но появление этого символа как раз и должно означать, что машина несамоприменима;
2) пусть M1 несамоприменима, тогда она применима к M1', что должно означать, что М1 самоприменима.
Полученное противоречие доказывает теорему, т. е. наше предположение о машине М неверно.
Поскольку различных слов в любом исчислении может быть бесчисленное множество, то фактически здесь имеется бесконечная серия однотипных задач. Требуется найти алгоритм, распознающий эквивалентность или неэквивалентность любой пары слов.
Проблема эквивалентности слов для ассоциативных исчислений была сформулирована еще в 1914 г. норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления
и для любой пары слов в нем позволил установить, эквивалентны эти слова или нет.
В 1946 и 1947 гг. А. А. Марков и Э. Пост, независимо один от другого, построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически неразрешима. Тем более не существует алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении.
В 1955 г. советский математик П. С. Новиков доказал алгоритмическую неразрешимость проблемы распознаваемости слов для ассоциативных исчислений специального вида называемых теорией групп.
Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы.
На этот вопрос теория алгоритмов в ряде случаев дает отрицательный ответ. Один из первых результатов такого типа, установленный американским математиком Чёрчем в 1936 году, относится к проблеме распознавания выводимости в математической логике (см. § 7).
Теорема Чёрча. Проблема распознавания выводимости алгоритмически неразрешима.
Тем самым не только выясняется причина безуспешности всех прошлых попыток создания соответствующих алгоритмов, но и обнаруживается полная бессмысленность таких попыток.
Доказательствам невозможности, приводимым в теории алгоритмов, присуща та же математическая строгость, что и доказательствам невозможности, приводимым в других областях математики (например, невозможность трисекции угла с помощью циркуля и линейки, или невозможность определения общей меры для
стороны квадрата и его диагонали) Эскиз такого доказательства мы приведем ниже для проблемы распознавания самоприменимости.
Пусть в машине Тьюринга зафиксирована какая-нибудь конфигурация. Возможны два случая: 1) машина применима к этой конфигурации, т. е. срабатывая в этой конфигурации машина после конечного числа тактов останавливается в заключительной конфигурации, подавая сигнал об остановке; 2) машина не применима к этой конфигурации, т. е. сигнал об остановке никогда не наступает и машина впадает в бесконечный процесс. Возникает следующая массовая проблема:
Проблема распознавания применимости. Заданы функциональная схема какой-нибудь машины и конфигурация в ней; узнать, применима машина к этой конфигурации или нет. Это — типичная задача на построение алгоритма, ибо для ее решения надо найти общий метод (алгоритм или машину), позволяющий автоматически решать вопрос о применимости любой заданной машины к любой заданной конфигурации.
Предположим теперь, что на ленте машины Тьюринга изображен ее же собственный шифр (т. е. шифр функциональной схемы), записанный в алфавите машины. Если машина применима к такой конфигурации, то будем называть ее самоприменимой, в противном случае — несамоприменимой. Тогда можно сформулировать следующую массовую проблему:
Проблема распознавания самоприменимости. По любому заданному шифру установить, к какому классу относится машина, зашифрованная им: к классу самоприменимых или несамоприменимых?
Теорема. Проблема распознавания самоприменимости алгоритмически неразрешима.
Очевидно, из этой теоремы немедленно вытекает и алгоритмическая неразрешимость более общей проблемы применимости.
Доказательство. Предположим, напротив, что такая машина А существует. Тогда в А всякий самоприменимый шифр перерабатывается в какой-то символ а (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости), а всякий несамоприменимый шифр — в другой символ (имеющий
смысл отрицательного ответа на поставленный вопрос). В таком случае можно было бы построить и такую машину В, которая по-прежнему перерабатывает несамоприменимые шифры в -с, в то время как к самоприменимым шифрам В уже не применима. Этого можно было бы добиться путем такого изменения схемы машины А, чтобы после появления символа о вместо сигнала об остановке машина стала бы неограниченно повторять этот же символ.
Итак, В применима ко всякому несамоприменимому шифру (вырабатывая при этом символ и не применима к самоприменимым шифрам. Однако это приводит к противоречию. Действительно,
1) пусть эта машина В самоприменима, тогда она применима к своему шифру В и перерабатывает его в символ но ведь появление этого символа как раз и должно означать, что В несамоприменима;
2) пусть В несамоприменима, тогда она применима к В, что должно означать как раз, что самоприменима.
Полученное противоречие доказывает теорему.
На основании доказанной теоремы удается установить алгоритмическую неразрешимость и некоторых других массовых проблем, возникающих в теории машин Тьюринга. При этом широко применяется метод сводимости, заключающийся в следующем.
Пусть для каждой единичной задачи входящей в серию задач эффективно указана единичная задача входящая в серию и такая, что коль скоро известно решение задачи то из него извлекается, и решение задачи В таком случае естественно говорить, что массовая проблема сведена к массовой проблеме При этих условиях ясно также, что если имеется алгоритм для решения задач то его можно перестроить в алгоритм, решающий серию задач Если же ранее было установлено, что серия задач алгоритмически неразрешима, то отсюда вытекает и алгоритмическая неразрешимость серии Такая ситуация как раз и используется часто для установления алгоритмической неразрешимости; именно для исследуемой проблемы отыскивают проблему которая заведомо алгоритмически неразрешима, но вместе С тем сводится к проблеме ,
Приведем пример сводимости проблем из теории машин Тьюринга.
Для произвольной машины Тьюринга можно построить другую машину которая связана с ней следующим образом. Пусть К — какая-нибудь конфигурация в тогда и в ей сопоставлена конфигурация К с соблюдением двух условий:
1) если не применима к К, то и не применима к К,
2) если применима к К, то тоже применима к К, причем перерабатывает ее в некоторую фиксированную заключительную конфигурацию (например, в обозреваемой ячейке вписана буква а все остальные ячейки пусты).
Проблема распознавания переводимости. Для любой заданной машины Тьюринга и любых двух конфигураций в ней требуется выяснить: если в качестве начальной конфигурации взята то перейдет ли машина (после конечного числа тактов) в конфигурацию или нет?
Пользуясь введенными выше терминами, можно сказать, что проблема применимости сводится к проблеме переводимости. Действительно, для распознавания применимости машины к конфигурации К достаточно выяснить, переводима ли в машине конфигурация К к стандартной конфигурации Отсюда вытекает, что проблема переводимости тоже алгоритмически неразрешима.
Более того, проблема переводимости остается алгоритмически неразрешимой, если в качестве брать только такие конфигурации, которые заведомо являются заключительными.
Впервые алгоритмическая неразрешимость была установлена для проблем, возникающих в самой математической логике (проблема выводимости) и в теории алгоритмов (например, проблемы применимости, переводимости и т. п.). Однако позднее выяснилось, что подобные явления имеют место и для некоторых, казалось бы, более узких проблем, возникающих в самых разнообразных специальных разделах математики. В первую
очередь здесь следует указать на ряд алгебраических проблем, приводящих к различным вариантам проблемы слов, которые исследовались советскими математиками.
Проблема эквивалентности слов для ассоциативных исчислений (см. § 4) была сформулирована еще в 1914 году норвежским математиком Туэ. Им же был предложен алгоритм для распознавания эквивалентности слов в некоторых ассоциативных исчислениях специального вида. С тех пор предпринимались многие попытки построить такой общий алгоритм, который для любого ассоциативного исчисления и для любой пары слов в нем позволили бы установить, эквивалентны эти слова или нет.
В 1946 и 1947 годах советский математик Андрей Андреевич Марков и американский математик Эмиль Пост, независимо один от другого, построили конкретные примеры ассоциативных исчислений, для каждого из которых проблема эквивалентности слов алгоритмически неразрешима. Тем более не существует алгоритма для распознавания эквивалентности слов в любом исчислении. Впоследствии на основе этого результата А. А. Марков и его ученики установили невозможность распознавания алгоритмов для широкого класса свойств ассоциативных исчислений.
В следующем параграфе приводится один из вариантов доказательства теоремы о невозможности алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении.
Большое впечатление произвел в математическом мире опубликованный в 1955 году результат Петра Сергеевича Новикова, доказавшего алгоритмическую неразрешимость проблемы тождества теории групп Эта проблема заключается в распознавании эквивалентности слов для ассоциативных исчислений специального вида: рассматриваются лишь такие ассоциативные исчисления, в которых для каждой буквы а алфавита в списке допустимых подстановок исчисления имеется подстановка вида
где а — какая-либо буква того же алфавита (возможно,
совпадающая с а). Содержательный смысл этого требования становится понятным, если, по аналогии с примером 4 из § 4, истолковать слова в любом ассоциативном исчислении как некоторые сложные преобразования, получаемые путем умножения элементарных преобразований, задаваемых соответствующими буквами, образующими это слово. В таком случае пустое слово задает тождественное преобразование, ничего не изменяющее (сравни с § 4), а наличие допустимых подстановок вида означает, что для каждого элементарного преобразования (задаваемого буквой а) существует элементарное преобразование (задаваемое буквой а) такое, что последовательное их осуществление дает тождественное преобразование. Не вдаваясь в дальнейшие подробности, отметим лишь, что рассмотрение таких множеств преобразований, называемых группами преобразований, представляет исключительно большой теоретический и практический интерес, а само понятие группы является одним из самых основных понятий современной математики.
Теперь нам нужно уяснить себе, что весьма важный результат Маркова — Поста, отмеченный выше, сам по себе не позволяет делать никаких выводов по существу проблемы тождества теории групп. Дело в том, что те индивидуальные ассоциативные исчисления, для которых А. А. Марков и Э. Пост установили алгоритмическую неразрешимость проблемы эквивалентности, как раз не удовлетворяют требованию, отмеченному выше, которое является существенным при постановке проблемы тождества теории групп. Поэтому возможность алгоритма для этой последней проблемы не исключается результатами Маркова — Поста. Надежда на создание этого алгоритма еще не была полностью утрачена, и поиски его еще продолжались, когда стал известен результат П. С. Новикова, согласно которому такого алгоритма не существует. П. С. Новиков построил индивидуальный пример ассоциативного исчисления, удовлетворяющего указанному требованию, для которого невозможен алгоритм, распознающий эквивалентность; тем более невозможен единый алгоритм для всех рассматриваемых групп.
Первые примеры, построенные А. А. Марковым и П. С. Новиковым для опровержения алгоритмической
разрешимости исследуемых проблей, оказались весьма громоздкими и насчитывали сотни допустимых подстановок. Была поставлена задача построения по возможности более простых примеров. В этом направлении блестящий успех был достигнут молодым ленинградским математиком Г. С. Цейтиным; для приведенного в § 4 исчисления, построенного Цейтиным и насчитывающего всего лишь семь допустимых подстановок, проблема эквивалентности слов также алгоритмически неразрешима.
Обнаружение алгоритмически неразрешимых проблем создало в науке такую ситуацию, когда математик, стремящийся к построению желаемого алгоритма, должен считаться с тем, что такого алгоритма может и не существовать. Поэтому параллельно с усилиями, направленными на поиски желаемого алгоритма, приходится прилагать усилия на доказательство невозможности такого алгоритма. В зависимости от того, на каком из этих направлений будет достигнут успех, и выяснится окончательно картина: либо будет найден разрешающий алгоритм, либо будет установлена алгоритмическая неразрешимость проблемы.
В § 1 была сформулирована проблема Гильберта о диофантовых уравнениях. В течение полувека велись односторонние, причем безуспешные, исследования с целью построить желаемый алгоритм. В последнее время проводятся исследования и в противоположном направлении, и хотя окончательного результата пока еще нет, но в свете частичных результатов, которые уже получены, кажется правдоподобным, что проблема Гильберта также является алгоритмически неразрешимой.
Читайте также: