В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 8

Если за Т(х) тактов машина остановится и результатом будет код числа О, то выдаем ответ 1, иначе выдаем ответ'О. Моделируя работу машины, мы можем работать только с той частью ленты, на которой записывается входное слово, а также которая посещается головкой во время работы. Тогда на каждом шаге нам достаточно хранить лишь конечный кусок ленты, что позволяет определить содержимое ленты и после оставова машины.

Следовательно, весь процесс вычисления Дх) алгоритмичен. В соответствии с тезисом Тьюринга существует машина Тьюринга, которая вычисляет 1(х). Мы примем здесь это утверждение, хотя для зв одисавиой фуккпии 1(х) можно и явно построить въгчисляющую ее машину Тьюринга (правда, долго и громоздко). Пусть машина М, вычисляет 1(х), то есть 1(х) = уц(х). В часгкости дгг(т) = 1(д) и значит опрепелеко Попустим, что гг(д) < Т(4). Тогда ло определению 1(х) получаем: если рг(т) = О, то 1(д) = 1, а если ~рг(т) ф О, то 1(г) = О. В любом случае 1(г) ф уг(т) — противоречие. Следовательно (от противного) гг(т) > Т(т). Теорема доказана. Теорема 4.3.

Длл любой обтцерекурсивной функции Т(х) ' пу щестеуетп общерекурсивнае функция 1(х), принимаютцая' ого высо 8 значение 0 и 1 и тпакая, чтпо для любой машины Тьюринеа М;, вычисляющей г(х), сдгцестпвуетп бесконечное число значений х, для котпормх вьгполняетсг нераеснстпво Гг(х) > Т(х). Доказательство. Пусть д(х) = х — (~/х)) . Тогда фуикпия д(х) вычислима и всюду определева (то есть обшерекурсввка). При х = О, 1, 2, 3,... функция д(х) принимает значения О, О, 1, 2, О, 1, 2, 3, 4, О, 1,....

Легко доказать, что фушспия д(х) прииимает каждое значение из Г+ бесконечное число раз. Определим фуиюппо 1'(х) следуюпгям образом. 1(х) = 1, если Гдг г(х) ~ (Т(х) и дддгбй(х) = О, О, иначе. Тогда фуикцяя 1(х) обпгерекурсивиа (доказываетсе так же, кал в предыдущей теореме). Пусть машина М; вычисляет 1(х), то.есть 1(х) = дц(х). Пусть 1 - любое число, такое, что д(1) =' т (талия 1 бесксвечло много). Полустим, что Ц(1) < Т(1). Тогда по определеиию Г(х) получаем: если двг(1) = О, то 1(1) = 1, а если Гог(1) ф О ', то У(1) = О.

В шобом случае У(1) Ф Ьдг(1) - противоречие. Слеповательио, Гг(1) > Т(Я. Теорема доказана. Справедливо еше более сильное утверждение, которое мы приведем без доказательства. Теорема 4.4. Длл любой общсренурсивной функции Т(х) сущестееуетп общерекурсивная фующия 1'(х), принимаютцае шдлько Я зна сенце 0 и 1 и тпакая, чтпо для любой машины Тьторинеа Мг, еьдчисигющей 1(х), множестпео тпех х, для котпорьгх й(х) < Т(х), конечно.

Теоремы 4.2-4.4 показывают, что существуют сколь утодио споило вычислимые обшерекурслввые фувкшеи с двумя значениями (или, что эквивелевтио, сколь угодно сложно распознаваемые языки). Возпикает вопрос: а какой вообще может быть сложность задач (языкпв)2 Супгественный ответ иа этот вопрос дает следующая теорема, которую мы приводим без доказательства. 37 Теорема 4.5. Пусть общерекурсивные функции й(п) и Т(п) сивковы, чпсо,, > -+ оо при и -+ оо. Тоеда существует язьск ТЪ! сп ссп) .о, коспорыб распознается некоторой лашиной Тьюринзо с числом сиоеое не более Т(п) (для всех входньсх слов любой длины и) и не расаозноепсся никакой маисиной Тьюринеа с наглом шизов с(п). Эта теорема похазывает, что возможные функпии сложности языков образуют довольно плотное множество.

Можно ли получить результат о большей плотности, в общем случае неизвестно. Однако для одного важного интервала мы получим отрсщательный ответ в л. 4.4. А именно, мы покажем, что не существует языков со сложностью расгюзнавания (на машине Тьюринга) во порядку между и н п 1ояп. 4.3. Метод следов. Распознавание симметрии Хотя в предыдущем параграфе показано, что существуют сколь утпдно сложные задачи, получить высохую нижнюю оленку сложности для конкретной задачи очень тяжело. Один вз методов для получении нвжних опенох сложности решения задач на машинах Тьюринга, называемый методом следов, предложил Я.

М. Барздинь, который впервые применил этот метод ддя опенки сложности распознавания симметрии иа машине Тьсорвлга [5]. Онрвделение. Рассмотрим точку на ленте машины Тьюринга ввиду ячевками с номерами с и с+ 1. Следом в этой точке лрн работе мвлгввы ва некотором входном слове будем называть последователь- 'вость всех состояний, в которые перехсдит машина, когда ее головка смеппается из ячейки с в ячейку с + 1 или наоборот (то есть проходит над этой точкой). Пусть а = асаз — входное слово.

Тогда через ~м(аг(аз) будем обозначать след машины М прн работе ва слове осао в точке, разделяющей бс и аз (считаем, что начальная конфигурьл;ия стандартная) . Основная идея Барздиня состоит в иглользовании следующего ухвержденвя. Лемма 4.1. Пусспь ~м(аг~ао) = ~м(Ьс~Ц), Тоеда при рпботпе на входном слове бсЬз машина М слепо осп точки, раздевяинцей ас и Ьз, рабовнсепз тпк все, как на сооспвеспствуюисей частпи при входном слове азаз, о справа так все, «ак на сооспеетствуюиСей части при входном слове ЬгЬз, прочен см(51~Ьз) = см(бцаз) = см(ЬцЬз) ,Покозаспельство.

Пусть ~м(аг)бз) = См(Щ) = ус,дй...Ь„, а ьмЩЬз) = дйщс...ус„. Заметим, что работа машины М на слове бгЬз слава от разделяющей точки однозначно определяется словом бс и состояниями Обдирай..., в которых головка переходит черз разделяющие точки влево, а работа справа от разделяющей точки однозначно опредедяется словом 6г и состояниями дйдйод..., в которык головка переходит через разделяющие точки вправо. Переход головки машины М через соответствующие разделяющие точки делит работу М на каждом из слов а1(6з, а~)аг и 61)6г на этапы. Машина М на первом этапе на слове а1 6г работает так же, как на первом этапе на слове а1 аз.

Поэтому дй = о;, и машина М на втором этапе на слове а16х работает так же, как на втором этапе на слове 6гбэ Отсюда д,, = щ, и машина М на третьем этапе на слове ас6з работает так же, как на третьем этапе на слове а1аз. Продолжая зто рассуждение, мы получаем утверждение леммы. Определение. Пусть А = ?0,1) и слово а = а1аз...о б А'. Будем говорить, что слово а симметрично, если ав — — о„, ах — — о 1 н т.д. Пусть машина Тьюринга М имеет ленточный алфавит С и множество состояний Я, причем А С С н о' б О, о" б Я.

Будем говорить, что М распознает симметрию, если для любого входного слова а б А' машина М всегда останавливается н при этом находится в состоянии д', если а симметрично, или д", если а не симметрично. з'тверждение. Существует машина Тьюринга М, которая распознает симметрию и делает при любом входном слове длины и не более сп шагов, где с — некоторая константа. 2 2?оказательство. Постаточно построить машину М, которая запоминает н стирает первый символ, перегоняет головку в конец слова и сравнивает символ в памяти с последним символом слова.

Если оюв не совпадают, то М переходит в состояние д" и останавливается. Если совпадают, то она стирает последний символ, возвращается в начало слова и повторяет процесс. Если слово полностью стерто, то М переходит в состояние д' и останавливается. При этом головка не более и ргз пробегает по слову длины не более и. Поэтому общее число шагов есть 0(п~). Определение. Пусть 5(п) — число всех симметричных двоичных слов длины и, а Е(п) — число всех симметричных двоичных слов длины п, удовлетворяющих некоторому заданному свойству Е. Будем говорить, что свойство Е выполняется дпя почти всех симметричных +Ел слов, если 1пп„, з?„-л = 1.

Лемма 4.2. Число различных двоичных симме|причных слов длины п равно Я(п) = 2П). Это утверждение следует из того, что симметричное слово одно- значно определяется своей первой половиной. Теорема 4.6 (Я. М. Варздинь). Ппя любой машины Тьюринга М, распознающей симметрию, существует константа см > О, такая, что дпя почти всех симметричных слов Х время 1м(Х) работы машины М на слове Х удовлетворяет неравенству Фм(Х) > см(Х)~, где )Х( — длина слова Х. Доказательство. Пусть М вЂ” далее некоторая фиксированная машина Тьюринга, распознающая симметрию двоичных слов. Лемма 4.3.