Выдержка из книги
Сборник N.N.
Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
Общее число хвостовых блоков в члене из Ah есть 2й, или приблизительно ra / logra. Теорема 1 устанавливает, что общее время вычисления в худшем случае должно быть пропорционально произведению числа хвостовых блоков, подлежащих сравнению, и максимального числа квадратов на ленте, нужных для записи всей существенной информации о базовом сегменте. Таким образом, невозможно улучшить вполне очевидный способ записи всех наборов, которые присутствуют в базовом сегменте, а потом просмотреть эту запись для каждого вновь поступившего хвостового блока.