Аннотация:В данной работе изучаются одноместные частичные функции, вычислимые через автоматы с
двумя счётчиками. Уже давно известно, что при специальной кодировке автомат с двумя счётчи-
ками может моделировать автомат с тремя счётчиками и, как следствие, может вычислять любые
одноместные функции, вычислимые по Тьюрингу. В этой работе рассматривается вычислимость в
естественной кодировке.
Вводится понятие манёвра, как простой части поведения автомата с 2 счётчиками. И вводятся по-
нятия функции манёвра и функции манёвра с переключателем, которые можно вычислять за один
манёвр.
Вводятся операции обобщенной суперпозиции и специальной рекурсии над функциями с пере-
ключателями. И через эти операции будет введен класс функций, называемых обобщенными функ-
циями манёвра. Дальше вводится понятие вычислительного графа, который служит для доказательства равенства класса одноместных функций, вычислимых через автоматы с двумя счётчиками и класса обобщенных функций манёвра.
