Доказано, что класс функций, строго вычислимых на регистровых машинах со счетчиками, совпадает с классом общерекурсивных функций. <...> К таким устройствам можно отнести машины со стековой и магазинной памятью, нестирающие машины и некоторые другие. <...> В [2] А. П. Бельтюков ввел понятие стековой регистровой машины (машина SRM), которая тоже относится к ряду устройств со счетчиками. <...> В принципе машины SRM можно использовать как универсальные вычислительные устройства, однако наиболее интересные результаты с применением машин SRM получаются при исследовании «малых» классов рекурсивных функций—классов, подобных классам En иерархии Гжегорчика [1–3]. <...> М.В. Ломоносова, e-mail: savvvig@gmail.com 95 96 И. В. Савицкий Несколько лет назад С. С. Марченков ввел (результаты не публиковались) понятие регистровой машины со счетчиками—RC-машина. <...> Отличительные особенности RC-машин состоят в том, что, во-первых, RC-машины не имеют внутренней памяти, а во-вторых, счетчики RC-машины работают «автономно» по принципу позиционной системы с достаточно большим значением основания. <...> Программа RC-машины может лишь изменять содержимое единственного рабочего регистра, проверяя соотношения больше/равно/меньше между значениями входных переменных, счетчиков и самого рабочего регистра. <...> В машинах SRM [2] возможности по записи информации в счетчики сужены: содержимое счетчиков можно только увеличивать на единицу, при этом содержимое всех «младших» счетчиков становится равным нулю. <...> Кроме того, в машинах SRM фактически отсутствует внутренняя память. <...> У RC-машин имеются рабочий и входные регистры и еще более усилены возможности считывания данных со счетчиков: можно не только сравнивать содержимое счетчиков на равенство/неравенство, но и различать, какое из этих чисел больше. <...> Таким образом, программа RC-машины может лишь «следить» за изменением значений счетчиков, на каждом такте сравнивая их с регистрами и друг с другом, и в нужные моменты пересылать значение какого-либо <...>