Машина Тьюринга и алгоритмически неразрешимые проблемы

Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно угадывая”, либо перебирая все предположения параллельно – и проверяет свое предположение за полиномиальное время.

Класс NP включает в себя класс P, поскольку любую задачу, решаемую за полиномиальное время на детерминированной (обычной) машине Тьюринга, можно решить и на недетерминированной за полиномиальное время, просто этап предположения опускается.

Если все задачи класса NP решаются за полиномиальное время и на детерминированной машине, то P=NP. Тем не менее, никем не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что это классы неравны.

Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такие задачи называются NP-полными. То есть, если такая задача решается за полиномиальное время, то P=NP.

Таким образом, для программиста NP-полнота означает полный перебор, причем сложность этого перебора будет экспоненциальной или факториальной. Но следует понимать, что не всякий полный перебор имеет такую сложность. Например, если решать задачи из предыдущего выпуска полным перебором, то сложность полученных алгоритмов будет полиномиальной – O(n2) для задачи про подпоследовательности и O(n6) для задачи про подматрицы.

Наконец, существует класс задач EXPTIME. Эти задачи решаются за экспоненциальное время. В настоящее время можно доказать, что EXPTIME-полные задачи невозможно решить за детерминированное полиномиальное время. Кроме того, доказано, что P<>EXPTIME.

 

 

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: Проблема тотальности;

По произвольному заданному алгоритму определить, будет ли он останавливаться на всех возможных наборах исходных данных. Другая формулировка этой задачи – является ли частичный алгоритм Р всюду определённым?

 

 

4. Реализация машины Тьюринга

 

Входные параметры и условия:

Дана строка «11111111», требуется определить количество единиц и если оно четное, то добавить к началу строки «i», в случае если количество нечетное, добавить «l»

Команды для выполнения задачи:

 

0101r

0@1@l

1121l

2111l

2@fls

1@fis

 

Программа считывает данные условия из файла, потом заполняет массив с командами. После чего машина встает на начало ленты и согласно командам выполняет действия над ней.

Условно программа состоит из двух частей: первая часть считывает данные из файла и заносит команды в массив, а вторая часть программы выполняет действия над исходной строкой.

Т.е. сама программа не может выполнять действий с лентой, она это делает на основании команд хранящихся в файле.

После выполнения каждой команды машина либо сдвигается влево, либо вправо, либо остается в текущем положении и переходит к выполнению следующей команды. И так до тех пор пока не получит выходной сигнал «f». После этого машина прекращает свою работу и выводит результат на экран.

Результат работы машины представлен на рисунке 1.

 

Рисунок 1. Результат работы машины Тьюринга

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Практическая часть

 

1 задание

Определите логическое значение последнего высказывания, исходя из логических значений всех предыдущих высказываний.

 

Решение:

Из первых двух высказываний делаем вывод, что или и или наоборот, по третьему высказыванию становится ясно, что и , значит ответ 1.

 

2 задание

Существует ли три таких высказывания  А, В, С, чтобы одновременно выполнялись для них следующие условия:

 

Решение:

Из первого условия, по определению дизъюнкции, следует, что и . Из второго условия, по определению дизъюнкции следует, что . По определению импликации , и , что противоречит третьему условию (0 0 1). Значит трех высказываний A, B и С, удовлетворяющих данным условиям не существует.

 

3 задание

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

 

                                                   *                                                                              **                           

P	Q	R
0	0	0	1	1	1	1	1	1
0	0	1	1	1	1	1	1	1
0	1	0	0	0	1	0	0	0
0	1	1	0	1	1	0	0	1
1	0	0	0	0	0	1	1	1
1	0	1	0	1	0	1	1	1
1	1	0	1	1	0	0	1	1
1	1	1	1	1	0	0	1	1

Из составленной таблицы истинности делаем вывод, что формула является логическим следованием формулы , так как вторая формула обращается в истинное высказывание на всех наборах значений переменных, для которых в истинное высказывание обращается первая формула.

 

 

 

4 задание

Приведите равносильными преобразованиями каждую из следующих формул к совершенно дизъюнктивной нормальной форме (СДНФ) и совершенно конъюнктивной нормальной форме (СКНФ).

Решение:

СДНФ

СКНФ

5 задание

Изобразите на координатной плоскости множества истинности следующих двухместных предикатов, заданных на множестве действительных чисел R.

1. ;

Решение:

множества истинности данного предиката на множестве R на координатной плоскости будет выглядеть следующим образом.

Рисунок a

6 задание

Изобразите на  координатной прямой или на координатной плоскости множества истинности следующих предикатов

Решение:

Множества истинности данных предикатов все точки плоскости, кроме точек первой четверти включая полуось Ox+, исключая полуось Oy+.

7 задание

Выясните, равносильны ли следующие предикаты, если их рассматривать над множеством действительных чисел R, над множеством рациональных чисел Q, над множеством целых чисел Z и над множеством натуральных чисел N:

 

Решение

Данные предикаты равносильны на всех множествах, на множестве натуральных чисел принимают значения [0,2), на всех остальных множествах (-∞, 2).

8 задание

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

 

Решение

 

Первый предикат превращается в истинное высказывание при х=0, второе высказывание тоже превращается в истинное высказывание при х = 0. Следовательно, первый предикат является следствием второго, а второй предикат - следствием первого.

 

 

 

9 задание

Дана машина Тьюринга с внешним алфавитом А={ a0, 1 }, алфавитом внутренних состояний Q={q1, q2, q3, q4, q5, q6, q7} и со следующей( программой) функциональной схемой