Cтраница 2
Для этого класса мы переносим внимание со структуры памяти, которая может быть произволь -; ной, на форму управления с конечным числом состояний или. Ячейка ( единственная) памяти, доступная на каждом шаге, определяет последовательность запоминания для любого вычисления, и это зависит, вообще говоря, от входа. Естественно, что состояние управляющего устройства и величины, хранящиеся в памяти, могут ( а в общем случае так и бывает) зависеть от входных символов; более точно - это движение головок, которое инвариантно. Во-первых, это ограничение позволяет получить очень простое доказательство улучшенной нижней оценки, и, во-вторых, оказывается, что почти все алгоритмы, предлагаемые или используемые для умножения, являются забывающими или могут быть сделаны забывающими только путем введения постоянного множителя в оценке времени вычисления. [16]