Моделирование неветвящихся программ с условной остановкой на универсальной машине Тьюринга

Изучается время моделирования неветвящихся программ с условной остановкой на машине Тьюринга с тремя лентами, одна из которых используется для хранения программы, управляющей работой машины. Установлены неравенства, в которых среднее время моделирования оценивается через длину и среднее время работы моделируемых неветвящихся программ. Показано, что для некоторых программ полученные равенства являются точными с точностью до постоянного множителя.
Библ. 9.