Конспект установочных лекций по комплексному курсу Информатика, Теория информации

       

Дерево вычислений


Далее ki à(i) К2,

если конфигурация К^ исходя из ki, может быть достигнута не более чем за 2^ (При ^= i ) шагов. Для i ³ 1

K1®^K2

можно вычислить тем, что мы k1®(Ù-1)k и К®(Ù-1)К2 перепробуем для всех К. Справедливо высказывание:

если вывод Ki ®^ К2 происходит в точности за 2^ шагов, то вывод может быть реализован с затратами памяти, необходимыми для хранения i конфигураций между k1 и К2.

Доказательство этого утверждения можно провести по индукции. При i == 0 справедливость утверждения очевидна. Для (i + 1) вначале реализуется вывод k1 ®^ К с затратами памяти для (i - 1) + 1 = i конфигураций. Затем реализуется вывод К ®^ К^ с теми же затратами на той же памяти.

Таким образом, общие затраты памяти равны 1+(i-1) == i, что и требовалось доказать.

Итак, для доказательства теоремы следует построить Т-машину, которая выполняет приведенную выше стратегию затрат памяти, т. е. надо промоделировать выполнение алгоритма со следующей спецификацией для каждой заключительной конфигурации Kf:

ifTEST(Ko, Kf, [log2(c^)] then принять fi (при ^=S(n))

где

TEST(Ki, К2, i) ==    if i = 0   then

(k1=k2) v (k1 ® К2)

else

$ K: TEST(K1, K, i-l) Ù test(k, K2, i-l),

где К - конфигурация из с^ возможных конфигураций fi

Для задания параметров TEST достаточно памяти O(S(n)). Действительно, для третьего параметра, числа [S(n)*log2(c)]+1 достаточно объема памяти 0(log2S(n)). Для конфигураций (их две) - поскольку входная лента не учитывается, т. е. в конфигурацию вносится только положение головки на входной ленте, - достаточно памяти

m*(S(n)+l) + Log(n) £ (m+1)S(n)+m, где m - число рабочих лент. Глубина стека равна [log2(c^]+2,=[S(n)log2(c)]+2, а поскольку каждый заносимый в стек элемент (параметр для TEST) занимает объем памяти O(S(n)), то общая потребность в памяти имеет порядок 0(S(n)^2).



Содержание раздела