$\Pi_1^0$-полнота исчисления Ламбека с итерацией Клини

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