Вирусы и средства борьбы с ними


RASPM с присоединенным вспомогательным хранилищем - часть 4


STORE [1] ; сохранить значение аккумулятора в 1-м регистре LOAD a ; загрузить операнд ADD 3 ; вычислить настоящий адрес STORE [2] ; сохранить его, как адрес активной ленты LOAD [1] ; восстановить значение аккумулятора

  • если оригинальная программа должна произвести чтение или запись на вспомогательном хранилище (например, PUT a), эмулирующей программе потребуется вычислить соответствующий номер ячейки на реальной ленте и произвести запись в нее путем выполнения следующей последовательности команд:

    STORE [1] ; сохранить значение аккумулятора SEEK [[2]] ; переместить головку в нужную позицию PUT a ; записать операнд на ленту LOAD [[2]] ; загрузить позицию на реальной ленте в аккумулятор ADD N ; изменить позицию (соответствует сдвигу вправо) STORE [[2]] ; сохранить позицию LOAD [1] ; восстановить значение аккумулятора

  • если оригинальная программа перемещает головку чтения/записи при помощи команды SEEK a, эмулирующая программа выполняет такую последовательность команд:

    STORE [1] ; сохранить значение аккумулятора LOAD a ; загрузить операнд MULT N ; вычислить по операнду ADD [2] ; номер позиции SUB 3 ; на реальной ленте STORE [[2]] ; сохранить новую позицию LOAD [1] ; восстановить значение аккумулятора

  • в процессе копирования программы из памяти эмулируемой машины в память эмулирующей, при замене описанных команд на последовательности команд, остальные команды сдвигаются на необходимое число позиций и все ссылки на ячейки памяти пересчитываются соответственно сдвигу
  • Построенная таким образом симулирующая машина требует не более 7 операций на каждую операцию исходной программы, а значит сложность эмулирующей программы будет не больше 7T(n), где T(n) - сложность эмулируемой программы. Теорема доказана.

    Следовательно увеличение количества вспомогательных хранилищ не увеличивает вычислительной способности машины RASPM с ABS. Осознавая этот факт, несложно понять, что вычислительная способность RASPM с ABS не превышает вычислительной способности RASPM, что и утверждается соответствующей теоремой.




    - Начало -  - Назад -  - Вперед -