Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Дерево вычислений
Далее 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).
