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


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


Теорема 2.6. Любая машина RASPM с ABS может быть проэмулирована машиной RASPM, и затраты на операции будут отличаться не более чем на постоянный множитель

Доказательство. По аналогии с доказательством предыдущей теоремы можно скомбинировать содержимое памяти и вспомогательного хранилища эмулируемой машины в памяти эмулирующей машины и получить RASPM - машину без вспомогательного хранилища. Основная разница при комбинировании будет заключаться в том, что смешиваться будут не отдельные ячейки, а их блоки, поскольку отрывать значение операнда от кода инструкции нельзя. Также следует учитывать, что для сохранения связности программы потребуется добавить после каждой команды оригинальной программы команду JUMP, чтобы пропустить ячейки памяти относящиеся к виртуальной вспомогательной ленте. В остальном принципы комбинирования остаются теми же, за тем исключением, что нет необходимости использовать несколько регистров для нескольких лент и отдельный регистр для номера ленты - достаточно будет ограничиться только регистром для хранения номера позиции на ленте. На этом неформальное доказательство можно считать законченным. Приводить формальное доказательство смысла нет из-за его относительной громоздкости.

Прямым следствием из теоремы будет следующая теорема:

Теорема 2.7. Вычислительная способность Машины Тьюринга и RASPM с ABS эквивалентны, а их затраты на вычисления находятся в полиномиальной зависимости

Доказательство. Этот результат получается из сопоставления результатов теорем 2.1, 2.2, 2.3 и 2.6.




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