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

摘要

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