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

Равнодоступная адресная машина (РАМ) представляет собой усложнение МТ (см. [1]). Вместо одной ленты и головки имеются две: входная, с которой можно только читать, и выходная, предназначенная для записи.

Вычисления производятся в сумматоре. РАМ имеет также неограниченный объем памяти в виде последовательности перенумерованных ячеек.

Работой лент, сумматора, головок управляет программа, состоящая из перенумерованной последовательности команд. Наличие счетчика команд позволяет расставлять метки в программе.

Программа для РАМ не записывается в память, поэтому предполагается, что программа не изменяет сама себя.

Все вычисления происходят в первом регистре, называемом сумматором.

Команда состоит из кода операции и адреса. Это известно всем, кто программировал на языке ассемблера. Операнд команды может задаваться тремя способами.

1.  В виде целого числа (литерала) i, что соответствует команде присвоения в программе. Это записывается как =i .

2. Либо в адресе команды содержится адрес регистра, в котором лежит значение операнда. Здесь  i – содержимое регистра,

3. Либо в адресе команды содержится адрес регистра (указатель), в котором содержится адрес регистра, содержащего значение операнда. Здесь *I означает косвенную адресацию. В случае отрицательного адреса программа останавливается.

Счетчик команд вначале установлен на первую команду в программе P, выходная лента пустая, содержимое c(i)=0 для любого регистра i. После выполнения k-й команды  P счетчик команд переходит на (k+1)-ю команду, если это не была команда условного перехода. (См. пример ниже).

Чтобы описать действия команды, задаются значения v( a) операнда a.

1. v(=i)=i.

2. v(i)=c(i).

3. v(*i)=c(c(i)).

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

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

В [1] исследуется РАМ, имеющая 12 типов команд. Приведем ее в качестве примера. Это команды начала работы и останова, команды чтения и письма, четыре арифметические операции, команда хранения, команда перехода на метку и две команды условного перехода в зависимости от содержимого сумматора.

Создание РАМ для приведенных выше примеров в разделах, описывающих НАМ и МТ, выглядит очень просто. В качестве менее очевидных примеров приведем следующие.

Пример 1. Написать программу для РАМ, которая для натуральных чисел вычисляет функцию nⁿ.

Пример 2. Дан алфавит {1,2}. Написать программу для РАМ, которая распознает слова в этом алфавите, содержащие одинаковое число вхождений 1 и 2.

Заметим, что программа РАМ не хранится в памяти, поэтому она себя изменять не может.

Равноадресная доступная машина с хранимой программой (РАСП) отличается от РАМ тем, что ее программа хранится в памяти. Каждая команда занимает два регистра памяти, в первом хранится код команды, во втором - адрес.

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

Мы рассмотрели достаточное количество примеров. Перейдем к их сравнительному анализу.