Об элементарных словарных функциях, получаемых на основе ограниченной префиксной конкатенации

На множестве словарных функций в алфавите $\{1,2\}$ вводится операция ограниченной префиксной конкатенации. На основе этой операций и операции суперпозиции определяется класс BPC полиномиально вычислимых функций. Устанавливается принадлежность классу BPC ряда словарных функций, а также замкнутость класса BPC относительно некоторых известных операций. Вводится некоторый тип двуленточных нестирающих машин Тьюринга и доказывается, что функции из класса BPC можно вычислить на машинах этого типа за полиномиальное время. Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 13-01-00958.