Равнодоступная адресная машина: различия между версиями

Каждая команда '''равнодоступной адресной машины''' имеет имя (код операции) и операнд. Операнд может быть одного из следующих типов: "<math>\,=i</math>" — означает само число <math>\,i</math> и называется литералом; "<math>\,i</math>" — содержимое ячейки <math>\,i</math>; "<math>\,*i</math>" — используется для косвенной адресации, т.е. значением операнда служит содержимое ячейки, адрес которой имеется в ячейке с номером <math>\,i</math>. Обозначая через <math>\,V(a)</math> значение операнда <math>\,a</math>, получаем: <math>\,V(=i)=i</math>; <math>\,V(i) =W(i)</math> и <math>\,V(*i)=W(W(i))</math>, где <math>\,W</math> — текущее состояние памяти. Набор команд '''равнодоступной адресной машины''' традиционен для реальных ЭВМ и состоит из команд считывания и запоминания, арифметических и логических команд, команд перехода, команд ввода и вывода и команды останова.

Как при равномерном, так и при логарифмическом весах команд для любой '''равнодоступной адресной машины''' (соответственно ''РАСП'') с временной сложностью <math>\,T(n)</math> существует такая постоянная <math>\,k</math>, что найдется эквивалентная ''РАСП'' (соответственно ''РАМ'' ), временная сложность которой не превосходит <math> \,kT(n)</math>.