В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 14

это естьчисло шагов вычисления на начальной конфигурации x по программе Р , есливычисление заканчивается и неопределено в противном случае.Ясно, что для введенной функции t P ( x ) также выполнены условия 1) и 2).Дадим теперь определение абстрактной меры вычисления (дляодноместных) числовых функций. Пусть f 1 ( x ), f 2 ( x ),..., f n ( x ),... - нумерацияодноместных частично рекурсивных функций. Мерой вычислительнойсложности называется любое семейство функций Ф0 ( x), Ф1 ( x),...,Фn ( x),...

,обладающее свойствами1) D(Фi ) = D( f i ) ∀i ∈ N 0782) Предикат Pi ( x, y) = (Фi ( x) = y) разрешим ∀i ∈ N 0 .Примером меры вычислительной сложности будет, например, семействофункций Фi ( x ), i ∈ N 0 , где Фi ( x ) -максимальное число, содержащееся врегистре МПД за все время вычисления Pi ( x ) , если Pi ( x ) ↓ и неопределено впротивном случае.В дальнейшем основное внимание будет уделено сложности Тьюринговыхвычислений.2 0 ) Рассмотрим вопрос о верхней границе сложности вычислений, которыйформулируется так: существует ли такая общерекурсивная функция h( x ) , чтодля любой вычислимой функции f ( x ) найдется машина Тьюринга для которойtT ( x ) ≤ h( x ) соответственно sT ( x ) ≤ h( x ) там, 1*де значения tT ( x )определены.Если допустить, что значения f ( x ) могут быть сколь угодно большими, тоответ отрицателен т.к.

на запись ответа может понадобиться тактов больше, чемh( x ) . Поэтому предположим что значения f ( x ) могут быть только О,1. Еслидопустить, что f ( x ) может быть частичной, то ответ также отрицателен, т.к. изсуществования такой общерекурсивной функции h( x ) следует существованиерекурсивного доопределения для любой рекурсивной функции f ( x ) .Действительно, пусть машина Т вычисляет функцию f ( x ) ,для любого xотсчитываем h( x ) тактов и если за это время значение f (x) не определено. тополагаем f ( x ) = 0 . Эта алгоритмическая процедура дает рекурсивноедоопределение.

Но это противоречит теореме 6 из раздела 3 §9. Будем теперьрассматривать общерекурсивные (0,1-функции f ( x ) . Следующая теоремапоказывает, что ответ на поставленный вопрос также отрицательный.Теорема _2. Для всякой общерекурсивной функции h( x ) существуетобщерекурсивная 0,1-функция f ( x ) , такая, что для любой машины Тьюринга Т ,вычисляющей f ( x ) , существует значение аргумента x=n , при которомt T ( n) < h ( x ) .Док-во.Рассмотрим нумерацию машин Тьюринга T0 , T1 ,..., Tn ,...

исоответствующую нумерацию частично рекурсивных функцийf 0 ( x ), f1 ( x ),..., f n ( x ),... . Определим конкретную функциюsg f x ( x) , если tTx ( n) ≤ h( x)f ( x) = и f x ( x) оп ределено 0,elseФункция f ( x ) вычислима с помощью следующей процедуры: для любого xнаходится значение h( x ) , затем машина Тx применяется к конфигурации q1 {...и считаются такты работы машины Тх .Если в течение h( x ) тактов Тхx+179остановилась в заключительной конфигурации вида q 0 {... (это проверяетсяy+1просмотром активной зоны размера ≤ x + h( x ) ), то полагается f ( x ) = sg y .Впротивном случае величина f x ( x ) не определена и полагаем f ( x ) =0.

Еслимашина Tx не остановилась в течение h( x ) тактов, то полагаем f ( x ) =0. Итак,вычислимость f ( x ) доказана. Следовательно, существует машина Тьюринга Т ,вычисляющая f ( x ) . Пусть ее номер n. Докажем, что выполнено t T (n) > h( x) .Если это не так, т.е. t T (n) ≤ h( x ) , то поскольку f = f n общерекурсивна и f (n)определено, тогдаf ( n) = sg f n ( n) = sg f T ( n)Следовательно, f (n) ≠ f T ( n) и это противоречит тому, что fвычисляется машиной Т.ч.т.д.03 ) Рассмотрим вопрос о существовании сложно вычислимых функций,который формулируется так: существует ли общерекурсивная функция (0,1)функция f ( x ) и такая, что для любой машины Тьюринга для всех x выполняетсяза время, превышающее значение наперед заданной функции h( x ) . В такойпостановке ответ отрицательный т.к.

вычисление функций f ( x ) в любомконечном числе точек можно сделать тривиальным, предварительно занеся этизначения в программу машины. Поэтому в поставленном вопросе потребуем,чтобы нужная оценка выполнилась при всех х , кроме конечного числа значений.Теорема 3.Для всякой общерекурсивной функции h( x ) существует общерекурсивная(0,1)-функция f ( x ) и такая, что для любой машины Т , вычисляющей f ( x ) ,существует x0 , такое, что выполнено t T ( x ) > h( x ) при всех x ≥ x0 .Док-во.Нужную функцию f ( x ) и вспомогательную функцию π ( x ) будем строитьпоследовательно при x=0,1,...x=0 Если t T0 (0) ≤ h(0) и f 0 (0) определено, тополагаем f (0) = sg f 0 ( 0) , π (0) = 0 .В противном случае полагаем f ( 0) = 0 и π (0) не определено.x=n>0 Пусть значения f ( x ) определены при всех x<nи определены значения π (x ) .Для нахождения f (n) поступаем следующим образом: Проверяемвыполнимость неравенствt T0 (n) ≤ h(n) , tT1 ( n) ≤ h(n) ,..., t Tn ( n) ≤ h(n)Для всех k ∈0, n , для которых выполнены оба условия а) t Tk (n) ≤ h(n)б) f k (n) определено80находим наименьшее, которое не является значением функции π .

Если такоечисло есть (обозначим его k0 ), тогда полагаем π (n) = k 0 и f (n) = sg f k 0 ( n)Если таких чисел k нет, либо все k уже являются значениями функции π , тосчитаем, что значение π (n) неопределено и f (n) =0.Легко убедиться, что функция f вычислима, всюду определена ипринимает значения О,1.Функция π (x ) принимает различные значения иπ ( x) ≤ x .Пусть Т - произвольная машина, вычисляющая f и i - номер машины Т.Докажем, что выполнено t Ti ( x ) > h( x ) для всех x , начиная с некоторого x0 .Пусть это неравенство нарушается для бесконечного числа значений x.Пусть n1 , n2 , n3 ,.. .

такие значения x, что i ≥ n1 > n2 > n3 >... .Покажем, что покрайней мере в одном из чисел n1 , n2 , n3 ,..., ni , ni +1 функция π принимаетзначение i . Имеем в точках n1 , n2 , n3 ,.. ., ni , ni +1 , неравенства t Ti (nk ) ≤ h(nk )определено. Если значение i не принимается функций π в точкахn1 , n2 , n3 ,..., ni , то либо π (n) было ранее, что невозможно, т.к. n1 - первое,начиная с i , число, для которого t Ti (n1 ) ≤ h(n1 ) , либо функция π принималазначения, меньшие i .

Таких значений i штук и при n ≤ ni все они являютсязначениями π (т.к. значения π различны). Тогда в точке ni +1 функция πпринимает значение i . Это значит, согласно определения функции f , чтоf ≠ f i ,т.е. машина Т не вычисляет f i . Полученное противоречие доказываеттеорему.ч.т.д.4 0 ) Выше была определена сложность конкретного алгоритма, вычисляющегонекоторую функцию f . Рассмотрим вопрос: можно ли определить сложностьвычислимой функции как сложность наилучшего алгоритма, вычисляющего ее.Приведем без доказательства (ввиду его сложности) результат М.Блюма,показывающий, что, вообще говоря, этого сделать нельзя. Существуют функции,допускающие убыстрение всюду, за исключением конечного числа точек.Теорема 4.Для любой общерекурсивной функции r ( x ) существует общерекурсивная(О,1)-функция f ( x ) ,такая, что для любой машины M i , вычисляющей f ( x ) ,существует машина M j , также вычисляющая f ( x) , что для всех x , начиная снекоторого выполненоt Ti ( x ) > r (t T j ( x ))Обсудим некоторые следствия из данного результата.

1. Если взятьr ( x ) = 2 x , то существует функция f ( x ) со свойством: если она допускаетвычисление со сложностью t ( x ) , то она допускает вычисление со сложностьюt ′( x ) , причем t ( x ) > 2 t ′ ( x ) или t ′( x ) < log t ( x ) .Убыстренное вычисление сновадопускает убыстрение-вычисление со скоростью t ′′ ( x ) ,81t ′′( x ) < log t ′( x ) < log log t ( x ) и т.д. (Неравенства выполняются при всех х,начиная с некоторого).2. Пусть мы реализуем работы любой машины М со скоростью 1 шаг/сек. ипереходим к реализации со скоростью 1010 шаг/сек. Тогда вычисление намашине M i , требующее ti ( x ) секунд при старой реализации, требуетti ′ ( x ) =ti ( x )1010секунд при новой реализации.Рассмотрим функцию f , определяемую теоремой об ускорении приr ( x ) = 1010 x .Пусть f вычисляется M i .

Тогда существует M j , такая, что1010 t j ( x ) < ti ( x )начиная с некоторого x0 t j ( x ) <ti ( x )1010= ti ′ ( x )Значит, для всех x начиная с некоторого, старая реализация вычислениямашины M j лучше, чем новая реализации машины M i , т.е. более быстраяреализация вычислений не имеет преимуществ перед медленной реализациейдля почти всех входов (для некоторых функций).82§ 13.

Нижние оценки временной сложности вычислений намашинах Тьюринга10 ) В данном разделе излагается техника следов позволяющая получатьнетривиальные нижние оценки времени вычисления на машинах Тьюринга.Данная тахника иллюстрируется на задаче распознавания симметрии слов иприменяется к задачам распознавания некоторых свойств булевых функций и ихсистем.Рассмотрим следующий класс однотипных задач. Пусть дан алфавитE = 01, и для произвольного слова P = p1 p2 ... pn , где pi ∈ E , i ∈1, n требуетсяузнать симметрично оно или нет , т.е.

верно ли равенствоP = p1 p2 ... pn = pn pn −1... p1 = P ′Предполагаем, что соответстветствующая решающая машина Тьюринга наначальной конфигурации q1P , выдает 1, если слово Р симметрично, и 0, впротивном случае.Нетрудно составить программу машины Тьюринга для решения даннойзадачи, однако для экономии места ограничимся описанием ее работы. Работамашины Тьюринга осуществляется циклами, В течение цикла 1 машина доверяетверно ли p1 = pn . Для этого запоминается символ p1 , и считывающая головкасмещается вправо, находит символ pn , и сравнивает его с p1 . Если эти символыразличны, то машина стирает запись на ленте и печатает 0, если эти символысовпадают, то машина реализует цикл 2, в течение которого сравниваются[ 2]символы p2 и pn-1 и т.д. Если слово Р симметрично, то будет произведено nциклов сравнения символов, в течение которых будетсовершено число тактов, равноеn + ( n − 1) + ( n − 2 )+...

= O ( n 2 ) .Возможны усовершенствования данной машины, приводящие ксокращению времени вычисления, однако не удается уменьшить порядок n 2 . Всвязи с этим возникает проблема - как доказать , что порядок n 2 временивычисления неустраним для данной машины Тьюринга. Соответствующеедоказательство было предложено Барздинем Я.М.2 0 ) Рассмотрим последовательность конфигураций T[ P] , реализуемуюмашиной Тьюринга Т на слове Р.Пронумеруем границы между соседними ячейками ленты так, как это показанона рис.p10p21...2pjp j +1 ...jj+pnn-183С каждой границей j можно связать последовательность внутренних состояниймашины Т следующим образом: Если в процессе T[ P ] головка машины ни разуне пересекала границу j , то эта последовательность пуста.