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


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

310 Р. Е. Стирнз, Дж Хартманис, П. М. Льюис II
как последовательность двоичных чисел, разделенных маркерами, и проверяем, совпадает ли первое число с bQ. Если это так, начинаем проверять, верно ли, что каждое следующее число больше предыдущего на единицу. Если это не так, то обрываем вычисление и отвергаем эту последовательность. Чтобы проверить любую пару последовательных чисел с целью убедиться в том, что правое число на единицу больше левого, достаточно поразрядно сравнивать эти числа, запоминая при необходимости переносы в конечном управляющем устройстве машины. На двусторонней машине Тьюринга цифры можно сравнивать, двигаясь вперед и назад между числами и используя рабочую ленту, чтобы записывать позицию (т. е. первая, вторая и т. д.) сравниваемых цифр. Если левое число длины /, то это потребует log/ рабочих квадратов. С другой стороны, легко проверить, что /-5 log /г, где п — длина вводного слова. Следовательно, наша схема требует log log n на двусторонней машине Тьюринга, и нижняя граница следствия 2.3 точна для двусторонней машины Тьюринга.
Чтобы получить пример для двусторонней магазинной машины, сначала рассмотрим, как последовательность wh можно распознать на двусторонней магазинной машине, используя L(n) = = log п. Цифры каждого 6г- запоминаются на магазинной ленте и сравниваются затем цифра за цифрой с bi+\. Теперь усовершенствуем Wh следующим образом: добавим два новых символа z и и (для нуля и единицы) к алфавиту ввода {0, 1} и используем их для обозначения положения цифры. Итак, мы полагаем
что bf — двоичная запись i в {0, 1} с цифрами, разряды которых последовательно пронумерованы числами, записанными в (г, и}. Например,
Положим
? = bSsbfs . . .
и посмотрим, с лентой какой длины мы можем распознавать
\Wk}- Применяя рассуждение о магазинных машинах из предыдущего раздела, легко видеть, что можно сначала проверить совпадения адресов (используя log / квадратов) и затем использовать эти адреса для сравнения знак за знаком, как в предыдущем случае; при этом весь процесс требует log log n квадратов ленты.
МАКСИМАЛЬНЫЙ РОСТ ЛЕНТОЧНОЙ ФУНКЦИИ
Так как машины Тьюринга могут разрешить все рекурсивные множества, то нельзя найти для этих машин максимальное CL. С другой стороны, из теоремы 4 видно, что Сп содержит все

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 311 312 313 314 315 316 317 318 319 320 330 340 350 360 370 380 390 400 410 420 430


Математика