Машина с единственной лентой

Если интересоваться сложностью алгоритмов с точностью до полиномиально ограниченного множителя, миоголеиточные машины ничего не добавляют по сравнению с описанными выше машинами с единственной лентой. [c.27]

Пусть М — машина Тьюрннга с единственной лентой, которая копирует входное слово (приписывая его копию справа от самого слова). Пусть Т(п) — максимальное время её работы иа входах длины п. Докажите, что Т п) для некоторого н для всех п. Что можно сказать про Т (п), которое есть минимальное время её работы на входах длины п [c.28]

Пусть имеется двухлеиточная МТ М2, работающая за время Т п] п на входах длины п. Опишем неформально машину М с единственной лентой, моделирующую работу М2. Алфавит этой машины достаточно велик, чтобы кодировать в одной ячейке содержимое ячеек с тем же номером иа лентах М2 и информацию о положении головок [c.145]

Это единственный случай (из трех рассматриваемых программ), в котором проблема экономизации вычислительного алгоритма решена в пользу экономии оперативной памяти, а не времени вычислений. Такой выбор обусловлен тем, что вычислоние матричных элементов (в арифметике 8-байтных чисел) производится значительно быстрее, чем последующее умножение комплексных (16-байтных) чисел, и, проигрывая во времени выполнения программы примерно на 20 %, мы более чем в 9 раз уменьшаем объем оперативной памяти, используемый для хранения матричных элементов. (При L=K=2i экономия составляет 870 кб). Преимущество такого подхода к генерации матрицы состоит еще и в том, что он позволяет во всех практически интересных случаях использовать только оперативную память машины, не обращаясь к внешним носителям. При использовании же внешней памяти (магнитные диски й особенно магнитные ленты) преимущества быстрого алгоритма счета быстро утрачиваются при увеличении L и К. [c.230]

В процессе фирмы Бадише анилин-унд сода-фабрик на ленте (рис. 11) полная переработка первичного полимера в товарный продукт совершается в результате одной единственной операции — обработки первичного полимера в месильной машине (так называемом мастикаторе) [202]. При этом одновременно происходит удаление остатков катализатора, хладоагента и растворителя. Мономерный изобутилен в первичном полимеризате не содержится, [c.162]

Справочник химика 21

Химия и химическая технология