1.1.1 Машина с неограниченными регистрами (МНР).

Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.

Допустимые команды:

Z(n) - обнуление регистра R_n.

S(n) - увеличение числа в регистре R_n на 1.

T(m,n) - копирует содержимое R_m в регистор R_n.

I(p,q,n) - если содержимое R_p = R_q то выполняется команда с номером n , если нет

следующая.

Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.

Тезис Черча (Churcha): Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.