Том 14, серия 1, номер 1, 2007 г., Стр. 94-109
УДК 519.95
А. В. Чашкин
Моделирование неветвящихся программ с условной остановкой на универсальной машине Тьюринга
Аннотация:
Изучается время моделирования неветвящихся программ с условной остановкой на машине Тьюринга с тремя лентами, одна из которых используется для хранения программы, управляющей работой машины. Установлены неравенства, в которых среднее время моделирования оценивается через длину и среднее время работы моделируемых неветвящихся программ. Показано, что для некоторых программ полученные равенства являются точными с точностью до постоянного множителя.
Чашкин А. В. 1
1. МГУ, мех.-мат. факультет,
Воробьевы горы, 119992 Москва, Россия
е-mail: chash@online.ru
Статья поступила 26 октября 2006 г.
|