Моделирование RAM на машинах Тыоринга

Отображение входов в результаты работы, задаваемое данной RAM, можно реализовать на машине Тьюринга. Опишем кратко, как это делается.

Для моделирования RAM на машине Тьюринга нужно кодировать состояние RAM и менять его в соответствии с работой R AM. Для этого удобно использовать многоленточные машины Тыоринга.

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

Состояние группы ячеек RAM мы будем представлять в виде слова.

#ai#vi##a2#V2# … #a_n#v_n#,.

где сц — номер ячейки памяти, — её содержимое. При этом предполагается, что в остальных ячейках записаны нули. Каждое из таких слов (коды входной и выходной ленты, а также памяти) будем записывать на отдельную ленту моделирующей МТ.

Так как R AM начинает работу, имея ненулевые значения лишь в конечном числе ячеек, то после любого числа шагов ненулевые значения будут лишь в конечном числе ячеек. Поэтому описанный выше способ позволяет корректно кодировать состояние RAM.

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

Задача 4.11. Постройте машины Тьюринга, реализующие описанные операции.