Аннотация:
Исчисление Ламбека аксиоматизирует операции умножения (поэлементного
приписывания слов), левого и правого делений на формальных языках.
Рассматривается естественное расширение исчисления Ламбека операцией
итерации (звёздочки) Клини, где звёздочка Клини аксиоматизируется
с помощью омега-правила. Доказано, что проблема выводимости в этом
исчислении $\Pi_1^0$-полна (в частности, не является алгоритмически
разрешимой и даже рекурсивно перечислимой). Результат усиливает ранее
известную нижнюю $\Pi_1^0$-оценку для более широкой системы, включающей
также операции объединения и пересечения [Бушковский 2007].
