Содержание
Введение. 2
1. Описание машины Тьюринга. 3
1.1 Свойства машины Тьюринга как алгоритма. 5
2. Сложность алгоритмов. 7
2.1 Сложность проблем… 9
3. Машина Тьюринга и алгоритмически неразрешимые проблемы… 12
Заключение. 16
Список литературы… 18
Введение
Машина Тьюринга — это оченьпростое вычислительное устройство. Она состоит из ленты бесконечной длины,разделенной на ячейки, и головки, которая перемещается вдоль ленты и способначитать и записывать символы. Также у машины Тьюринга есть такая характеристика,как состояние, которое может выражаться целым числом от нуля до некотороймаксимальной величины. В зависимости от состояния машина Тьюринга можетвыполнить одно из трех действий: записать символ в ячейку, передвинуться наодну ячейку вправо или влево и установить внутреннее состояние.
Устройство машины Тьюрингачрезвычайно просто, однако на ней можно выполнить практически любую программу. Длявыполнения всех этих действий предусмотрена специальная таблица правил, вкоторой прописано, что нужно делать при различных комбинациях текущих состоянийи символов, прочитанных с ленты.
В 1947 г. Алан Тьюринг расширилопределение, описав «универсальную машину Тьюринга». Позже длярешения определенных классов задач была введена ее разновидность, котораяпозволяла выполнять не одну задачу, а несколько.
1. Описание машины Тьюринга
Алан Тьюринг (Turing) в 1936году опубликовал в трудах Лондонского математического общества статью «Овычислимых числах в приложении к проблеме разрешения», которая наравне сработами Поста и Черча лежит в основе современной теории алгоритмов.
Предыстория создания этой работысвязана с формулировкой Давидом Гильбертом на Международном математическомконгрессе в Париже в 1900 году неразрешенных математических проблем. Одной изних была задача доказательства непротиворечивости системы аксиом обычнойарифметики, которую Гильберт в дальнейшем уточнил как «проблемуразрешимости» — нахождение общего метода, для определения выполнимостиданного высказывания на языке формальной логики.
Статья Тьюринга как раз и давалаответ на эту проблему — вторая проблема Гильберта оказалась неразрешимой. Нозначение статьи Тьюринга выходило далеко за рамки той задачи, по поводу которойона была написана.
Приведем характеристику этой работы,принадлежащую Джону Хопкрофту: «Работая над проблемой Гильберта, Тьюрингупришлось дать четкое определение самого понятия метода. Отталкиваясь отинтуитивного представления о методе как о некоем алгоритме, т.е. процедуре,которая может быть выполнена механически, без творческого вмешательства, онпоказал, как эту идею можно воплотить в виде подробной модели вычислительногопроцесса. Полученная модель вычислений, в которой каждый алгоритм разбивался напоследовательность простых, элементарных шагов, и была логической конструкцией,названной впоследствии машиной Тьюринга».
Машина Тьюринга являетсярасширением модели конечного автомата, расширением, включающим потенциальнобесконечную память с возможностью перехода (движения) от обозреваемой в данныймомент ячейки к ее левому или правому соседу.
Формально машина Тьюринга можетбыть описана следующим образом. Пусть заданы:
конечное множество состояний –Q, в которых может находиться машина Тьюринга;
конечное множество символовленты – Г;
функция δ (функцияпереходов или программа), которая задается отображением пары из декартовапроизведения Q x Г (машина находится в состоянии qi иобозревает символ gi)в тройку декартова произведения Q х Г х {L,R} (машина переходит в состояние qi, заменяет символ gi на символ gj и передвигается влево или вправо на один символ ленты) – Qx Г-->Q х Г х {L,R}
один символ из Г-->е (пустой);
подмножество Σ є Г — ->определяется как подмножество входных символов ленты, причем е є (Г — Σ);
одно из состояний – q0 є Q является начальным состоянием машины.
Решаемая проблема задается путемзаписи конечного количества символов из множества Σ є Г – Si є Σ наленту:
eS1S2S3S4……… Sne
после чего машина переводится вначальное состояние и головка устанавливается у самого левого непустого символа(q0,w) –, после чего в соответствии с указанной функциейпереходов (qi,Si) — ->(qj,Sk, L или R) машина начинаетзаменять обозреваемые символы, передвигать головку вправо или влево ипереходить в другие состояния, предписанные функций переходов.
Остановка машины происходит втом случае, если для пары (qi,Si)функция перехода не определена.
Алан Тьюринг высказалпредположение, что любой алгоритм в интуитивном смысле этого слова может бытьпредставлен эквивалентной машиной Тьюринга. Это предположение известно кактезис Черча–Тьюринга. Каждый компьютер может моделировать машину Тьюринга(операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке сучетом изменения состояния машины). Следовательно, он может моделироватьалгоритмы в любом формализме, и из этого тезиса следует, что все компьютеры(независимо от мощности, архитектуры и т.д.) эквивалентны с точки зренияпринципиальной возможности решения алгоритмических задач. 1.1 Свойства машины Тьюринга как алгоритма
На примере машины Тьюрингахорошо прослеживаются свойства алгоритмов. Попросите учащихся показать, чтомашина Тьюринга обладает всеми свойствами алгоритма.
Дискретность. Машина Тьюрингаможет перейти к (к + 1) — му шагу только после выполнения каждого шага, т.к именнокаждый шаг определяет, каким будет (к + 1) — й шаг.
Понятность. На каждом шаге вячейку пишется символ из алфавита, автомат делает одно движение (Л, П, Н), имашина Тьюринга переходит в одно из описанных состояний.
Детерминированность. В каждойклетке таблицы машины Тьюринга записан лишь один вариант действия. На каждомшаге результат определен однозначно, следовательно, последовательность шаговрешения задачи определена однозначно, т.е. если машине Тьюринга на вход подаютодно и то же входное слово, то выходное слово каждый раз будет одним и тем же.
Результативность. Содержательнорезультаты каждого шага и всей последовательности шагов определены однозначно,следовательно, правильно написанная машина Тьюринга за конечное число шаговперейдет в состояние q0, т.е. за конечное число шаговбудет получен ответ на вопрос задачи.
Массовость. Каждая машинаТьюринга определена над всеми допустимыми словами из алфавита, в этом и состоитсвойство массовости. Каждая машина Тьюринга предназначена для решения одногокласса задач, т.е. для каждой задачи пишется своя (новая) машина Тьюринга.
2. Сложность алгоритмов
Сложность алгоритма определяетсявычислительными мощностями, необходимыми для его выполнения. Вычислительнаясложность алгоритма часто измеряется двумя параметрами: Т (временная сложность)и S (пространственная сложность, или требования к памяти). И Т, и S обычнопредставляются в виде функций от n, где n — это размер входных данных. (Существую и другие способыизмерения сложности: количество случайных бит, ширина канала связи, объемданных и т.п.)
Обычно вычислительная сложностьалгоритма выражается с помощью нотации «О большого», т. е описываетсяпорядком величины вычислительной сложности. Это просто член разложения функциисложности, быстрее всего растущий с ростом n, все членынизшего порядка игнорируются. Например, если временная сложность данногоалгоритма равна 4n2+7n+12, товычислительная сложность порядка n2, записываемая какО(n2).
Временная сложность измеренная такимобразом не зависит от реализации. Не нужно знать ни точное время выполненияразличных инструкций, ни число битов, используемых для представления различныхпеременных, ни даже скорость процессора. Один компьютер может быть на 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
Находящийся слева класс Pвключает все задачи, которые можно решить за полиномиальное время. В класс NPвходят все задачи, которые можно решить за полиномиальное время только нанедетерминированной машине Тьюринга (это вариант обычной машины Тьюринга,которая может делать предположения). Такая машина предполагает решение задачи –либо “удачно угадывая”, либо перебирая все предположения параллельно – ипроверяет свое предположение за полиномиальное время.
Класс NP включает в себя классP, поскольку любую задачу, решаемую за полиномиальное время надетерминированной (обычной) машине Тьюринга, можно решить и нанедетерминированной за полиномиальное время, просто этап предположенияопускается.
Если все задачи класса NPрешаются за полиномиальное время и на детерминированной машине, то P=NP. Тем неменее, никем не доказано, что PNP (или P=NP). Однако, большинствоспециалистов, занимающихся теорией сложности, убеждены, что это классы неравны.
Как ни странно, можно доказать,что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такиезадачи называются NP-полными. То есть, если такая задача решается заполиномиальное время, то P=NP.
Таким образом, для программистаNP-полнота означает полный перебор, причем сложность этого перебора будетэкспоненциальной или факториальной. Но следует понимать, что не всякий полныйперебор имеет такую сложность. Например, если решать задачи из предыдущеговыпуска полным перебором, то сложность полученных алгоритмов будетполиномиальной — O(n2) для задачи про подпоследовательности и O(n6) для задачипро подматрицы.
Наконец, существует класс задачEXPTIME. Эти задачи решаются за экспоненциальное время. В настоящее время можнодоказать, что EXPTIME-полные задачи невозможно решить за детерминированноеполиномиальное время. Кроме того, доказано, что PEXPTIME.
3. Машина Тьюринга и алгоритмически неразрешимыепроблемы
За время своего существованиячеловечество придумало множество алгоритмов для решения разнообразныхпрактических и научных проблем. Зададимся вопросом – а существуют ликакие-нибудь проблемы, для которых невозможно придумать алгоритмы их решения?
Утверждение о существованииалгоритмически неразрешимых проблем является весьма сильным – мы констатируем,что мы не только сейчас на знаем соответствующего алгоритма, но мы не можемпринципиально никогда его найти.
Успехи математики к концу 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: Вычисление совершенныхчисел;
Совершенные числа – это числа,которые равны сумме своих делителей, например: 28 = 1+2+4+7+14.
Определим функцию S(n) = n-ое посчёту совершенное число и поставим задачу вычисления S(n) по произвольнозаданному n. Нет общего метода вычисления совершенных чисел, мы даже не знаем,множество совершенных чисел конечно или счетно, поэтому наш алгоритм долженперебирать все числа подряд, проверяя их на совершенность. Отсутствие общегометода решения не позволяет ответить на вопрос о останове алгоритма. Если мыпроверили М чисел при поиске n-ого совершенного числа – означает ли это, чтоего вообще не существует?
Проблема 3: Десятая проблемаГильберта;
Пусть задан многочлен n-ойстепени с целыми коэффициентами – P, существует ли алгоритм, который определяет,имеет ли уравнение P=0 решение в целых числах?
Ю.В. Матиясевич показал, чтотакого алгоритма не существует, т.е. отсутствует общий метод определения целыхкорней уравнения P=0 по его целочисленным коэффициентам.
б) Информационнаянеопределенность задачи
Проблема 4: Позиционированиемашины Поста на последний помеченный ящик;
Пусть на ленте машины Постазаданы наборы помеченных ящиков (кортежи) произвольной длины с произвольнымирасстояниями между кортежами и головка находится у самого левого помеченногоящика. Задача состоит установке головки на самый правый помеченный ящикпоследнего кортежа.
Попытка построения алгоритма,решающего эту задачу приводит к необходимости ответа на вопрос – когда послеобнаружения конца кортежа мы сдвинулись вправо по пустым ящикам на М позиций ине обнаружили начало следующего кортежа – больше на ленте кортежей нет или ониесть где-то правее? Информационная неопределенность задачи состоит в отсутствииинформации либо о количестве кортежей на ленте, либо о максимальном расстояниимежду кортежами – при наличии такой информации (при разрешении информационнойнеопределенности) задача становится алгоритмически разрешимой.
в) Логическая неразрешимость (всмысле теоремы Гёделя о неполноте)
Проблема 5: Проблема «останова»(см. теорема);
Проблема 6: Проблемаэквивалентности алгоритмов;
По двум произвольным заданнымалгоритмам (например, по двум машинам Тьюринга) определить, будут ли онивыдавать одинаковые выходные результаты на любых исходных данных.
Проблема 7: Проблема тотальности;
По произвольному заданномуалгоритму определить, будет ли он останавливаться на всех возможных наборахисходных данных. Другая формулировка этой задачи – является ли частичныйалгоритм Р всюду определённым?
Заключение
Теория сложности такжеклассифицирует и сложность самих проблем, а не только сложность конкретныхалгоритмов решения проблемы. Теория рассматривает минимальное время и объемпамяти, необходимые для решения самого трудного варианта проблемы на теоретическомкомпьютере, известном как машина Тьюринга. Машина Тьюринга представляет собойконечный автомат с бесконечной лентой памяти для чтения записи и являетсяреалистичной моделью вычислений.
Задачи можно разбить на классы всоответствии со сложностью их решения. Вот важнейшие из них и предполагаемыесоотношения между ними:
P
Находящийся слева класс Pвключает все задачи, которые можно решить за полиномиальное время. В класс NPвходят все задачи, которые можно решить за полиномиальное время только нанедетерминированной машине Тьюринга (это вариант обычной машины Тьюринга,которая может делать предположения). Такая машина предполагает решение задачи –либо “удачно угадывая”, либо перебирая все предположения параллельно – ипроверяет свое предположение за полиномиальное время.
Класс NP включает в себя классP, поскольку любую задачу, решаемую за полиномиальное время надетерминированной (обычной) машине Тьюринга, можно решить и нанедетерминированной за полиномиальное время, просто этап предположенияопускается.
Если все задачи класса NPрешаются за полиномиальное время и на детерминированной машине, то P=NP. Тем неменее, никем не доказано, что PNP (или P=NP). Однако, большинствоспециалистов, занимающихся теорией сложности, убеждены, что это классы неравны.
Как ни странно, можно доказать,что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такиезадачи называются NP-полными. То есть, если такая задача решается заполиномиальное время, то P=NP.
Список литературы
1. Рощин А.Г., ПолововР.М. Теория автоматов. Часть I. Тексты лекций — Москва: МГТУ ГА, 2001. — 76 с.
2. Фалевич Б.Я. Теорияалгоритмов. – М.: ИНФРА-М, 2006. – с.324.
3. Фалина Н.М. МашинаТьюринга // Информатика. — №26. – 2005. – с.12-15