Теория и практика защиты программ



         

RAM-машина как пара интерактивных машин - часть 3


Число шагов каждого вычисления на рабочей ленте ограничено фиксированным полиномом от k.

Единственная роль входа ЦП заключается в инициализации регистров ЦП, и этот вход в дальнейшем может игнорироваться. «Внутренние» вычисления ЦП в каждом раунде соответствует элементарным операциям над регистрами. Следовательно, число шагов, принимаемых в каждом таком вычислении, является фиксированным полиномом от длины регистра (которая равна O(k)). Теперь можно определить RAM-модель вычислений, как семейство RAMk-машин для каждого k.

Определение 5.1. Для каждого kÎN определим машину RAMk

как пару (CPUk, MEMk), где ленты «только-для-чтения» машины CPUk

совпадают с лентами «только для записи» машины MEMk, а ленты «только-для-записи» машины CPUk

совпадают с лентами «только-для-чтения» машины MEMk. Вход RAMk – это пара (s,y), где s - вход (инициализация) для CPUk и у – вход для MEMk. Выход машины RAMk по входу (s,у), обозначаемый как RAMk(s,у), определен как выход MEMk(y) при взаимодействии с CPUk(s).

Для того, чтобы рассматривать RAM-машину как универсальную машину, необходимо разделить вход у машины MEMk

на «программу» и «данные». То есть, вход у

памяти разделен (специальным символом) на две части, названные программой (обозначенной П) и данными (обозначаемыми x).

Пусть RAMk и s фиксированы и у=(П,х). Определим выход программы П на входных данных х, обозначаемый через П(x) как RAMk(s,у). Определим время выполнения П на данных х, обозначаемое через tП(x), как сумму величины (½у½+½П(x)½) и числа раундов вычисления RAMk(s,у). Определим также размер памяти программы П

для данных х, обозначаемый через sП(x) как сумму величины ½у½

и числа различных адресов, появляющихся в сообщениях, посланных CPUk к MEMk в течение работы RАМk(s,у).

Легко увидеть, что вышеупомянутая формализация непосредственно соответствует модели вычислений с произвольным доступом к памяти.Следовательно, «выполнение П на х» соответствует раундам обмена сообщениями при вычислении RAMk(×,(П,х)). Дополнительный член ½y½+½П(x)½ в tП(x) поясняет время, потраченное при чтении входа и записи выхода, в то время как каждый раунд обмена сообщениями представляет собой единственный цикл в традиционной RAM-модели. Член ½y½ в sП(х) объясняет начальное пространство, взятое по входу.




Содержание  Назад  Вперед