Моделирование на забывающих RAM машинах

Моделирование на забывающих RAM машинах

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

Пусть RAM(m) означает RAMмашину с m ячейками памяти и доступом к случайному оракулу [13]. Тогда t шагов независимой RAM(m)программы может моделироваться за менее чем O(t(log2 t)3) шагов на забывающей RAM(m(log2 m)2).

Таким образом, можно увидеть, как провести моделирование независимой RAMпрограммы на забывающей RAMмашине с полилогарифмическим (от размера памяти) замедлением времени выполнения. В то же время, простой комбинаторный аргумент показывает, что любое забывающее моделирование независимой RAMмашины должно иметь среднее число Ω(lоgt) затрат. В связи с эти приводится следующий аргумент.

Пусть машина RAM(m) определена как показано выше. Тогда каждое забывающее моделирование RAM(m)машины должно содержать не менее max{m,(t1)log m} операций доступа, чтобы смоделировать t шагов оригинальной программы.

Далее рассмотрим сценария наихудшего случая, в котором наблюдатель (или в данном случае противник) активно пытается получить информацию, вмешиваясь в процесс вычислений. Вопрос заключается в том, можно ли гарантировать, что воздействие противника является забывающим по входу. Неформально говоря, моделирование RAMмашины на забывающей RAMмашине является доказуемо защищенным от вмешательства, если моделирование остается забывающим (т.е. не вскрывает какойлибо информации о входе за исключением его длины) даже в случае, когда независимый "мощный" противник исследует и изменяет содержимое памяти. В связи с этим приводится следующий аргумент.

В условиях определения RAM(m)машины t шагов независимой RAM(m)программы могут быть промоделированы (доказуемо защищенным от вмешательства способом) менее чем за O(t(log2t)3) шагов на забывающей машине RAM(m(log2m)2).

Необходимо отметить, что вышеприведенные результаты относятся к RAMмашинам с доступом к случайному оракулу. Чтобы получить результаты для более реалистичных моделей вероятностных RAMмашин, необходимо заменить случайный оракул, используемый выше, псевдослучайной функцией. Такие функции существуют в предположении существования односторонних функций с использованием короткого действительно случайно выбранного начального значения.

Модели и определения

Далее рассматривается модель RAM как пара интерактивных машин с ограниченными ресурсами, и даются два базовых понятия: понятие защиты программ и понятие моделирования на забывающей RAMмашине.

RAMмашина как пара интерактивных машин. В данном разделе RAMмашина представляется как две интерактивные машины: центральный процессор (ЦП) и модуль памяти (МП). Задача исследований сводится изучению взаимодействия между этими машинами. Для лучшего понимания необходимо начать с определения интерактивной машины Тьюринга.

Интерактивная машина Тьюринга многоленточная машина Тьюринга, имеющая следующие ленты:

  • входная лента "только для чтения";
  • выходная лента "только для записи";
  • рабочая лента "для записи и для чтения";
  • коммуникационная лента "только для чтения";
  • коммуникационная лента "только для записи"
  • .

Под ITM(c,w) обозначается машина Тьюринга с рабочей лентой длины w и коммуникационными лентами, разделенными на блоки cбитной длины, которая функционирует следующим образом. Работа ITM(c,w) на входе у начинается с копирования у в первые |y| ячеек ее рабочей ленты. В случае если |y|>w, выполнение приостанавливается немедленно. В начале каждого раунда, машина читает следующий cбитный блок с коммуникационной ленты "толькодлячтения". После некоторого внутреннего вычисления, использующего рабочую ленту, раунд завершен с записью с битов на коммуникационную ленту "толькодлязаписи". Работа машины может завершиться в некоторой точке с копированием префикса ее рабочей ленты на выходную ленту машины. Теперь можно определить ЦП и МП как интерактивные машины Тьюринга, которые взаимодействуют друг с другом, а также можно ассоциировать коммуникационную ленту "толькодлячтения" ЦП с коммуникационной лентой "толькодлязаписи" МП и наоборот. Кроме того, и ЦП, и МП будут иметь ту же самую длину сообщений, то есть, параметр с, определенный выше. МП будет иметь рабочую ленту размером, экспоненциальным от длины сообщений, в то время как ЦП будет иметь рабочую ленту размером, линейным от длины сообщений. Каждое сообщение может содержать "адрес" на рабочей ленте МП и/или содержимое регистров ЦП.

Далее используем k как параметр, определяющий и длину сообщений, и размер рабочих лент ЦП и МП. Кроме того, длина сообщений будет равна k+2+k', а размер рабочей ленты будет равен 2kk', где k'=O(k).

Для каждого kN определим MEMk как машину IТМ(k+2+O(k),2kO(k)), работающую точно так, как определено выше. Рабочая лента разбивается на 2k слов, каждое размером O(k). После копирования входа на рабочую ленту машина MEMk является машиной, управляемой сообщениями. После получения сообщения (i,a,v), где i{0,1}2{"запомнить","выборка","стоп"}, a {0,1}k и v{0,1}O(k), машина MEMk работает следующим образом.

Если i="запоминание", тогда машина MEMk копирует значение v из текущего сообщения в число а рабочей ленты.

Если i="выборка", тогда машина MEMk посылает сообщение, состоящее из текущего числа а (рабочей ленты).

Если i="стоп", тогда машину MEMk копирует префикс рабочей ленты (как специальный символ) на выходную ленту и останавливается.

Далее, пусть для каждого kN определим CPUk как машину IТМ(k+2+O(k),O(k)), работающую точно так, как определено выше. После копирования входа на свою рабочую ленту, машина CPUk выполняет вычисления за время, ограниченное poly(k), используя рабочую ленту, и посылает сообщение, определенное в этих вычислениях. В следующих раундах CPUk является машиной, управляемой сообщениями. После получения нового сообщения машина CPUk копирует сообщение на рабочую ленту и, основываясь на вычислениях на рабочей ленте, посылает свое сообщение. Число шагов каждого вычисления на рабочей ленте ограничено фиксированным полиномом от k.

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

Для каждого kN определим машину 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П(х) объясняет начальное пространство, взятое по входу.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок