Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

160 М. Рабин
(3—5) М всегда будет обозначать эту фиксированную однолен-точную машину, для которой Т2=Т(М).
Определение 3. Если w — входная последовательность машины М, то рабочей зоной t(w) машины М при последовательности w назовем последовательность квадратов ленты, на которых побывала машина М во время подачи входа w.
Если х — последовательность квадратов на ленте или последовательность символов, то 1(х) будет обозначать длину, т. е. число элементов я.
Пусть х — входная последовательность; кодом х мы будем считать последовательность символов на квадратах рабочей зоны t(x), состояние машины М и ее положение на ленте в конце подачи входной последовательности х.
Лемма 2. Существует числовая константа с>0, такая, что для любого и е Л и любого целого i>0 существует v е Z, такое, что l(v) = i и ci^.l(l(uv)).
Доказательство. Существует 2* последовательностей v е Z, таких, что l(v) =i. Поскольку после uv на входе может появиться р, то, если v\ =?= v, тогда uv\ и uv должны иметь разные коды. В противном случае и uvftv* и ии\$и* будут допускаться машиной М.
Пусть l(t(uv)) ^.k для всех v е Z, 1(и) ={. Тогда существует самое большее nh'k-m различных кодов для входов uv. Следовательно, 2г'^яй •&•/«. Если i велико, то и k велико, так что можно предполагать km^nh (мы предполагаем 2- 1 In 2 . ^ ,
т ч—t^k.
2 Inn ^
АД 1 In2 ~* *
Мы можем взять cl = -^--]—. Это с\ будет пригодно для
? 1П ?Ъ
всех i, больших, чем некоторое i0; для достаточно малого с лемма будет выполняться при всех i.
Лемма 3. Существует^ целое d>Q (зависящее только от машины М), такое, что для любого и е А и любого целого i^-l(u) существует последовательность v e Z, l(v)=i, такая, что a) ci^.l(t(uv)), б) не более чем 1/5 квадратов рабочей зоны t(uv) посещались машиной М более чем а раз.
Доказательство. Выберем последовательность v e Z, /(и)= i, для которой выполняется (а). Пусть d\ — число, такое, что больше чем 1/5 квадратов t(uv) посещались машиной М более чем d\ раз. Тогда общее число шагов работы машины превышает d\- (l/5)l(t(uv)) ^ (1/5)did. Но, поскольку М работает

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 161 162 163 164 165 166 167 168 169 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика