ЛАГ И ТАГ СИСТЕМЫ
— разновидности Поста исчислений, отличающиеся специфическими правилами вывода. ЛАГ системы имеют правила вида

которые применяются следующим образом: если первые (5 букв слова суть

то в нем стирается первая буква, т. е. и справа к этому слову дописывается слово

может быть и пустым)

ТАГ системы имеют правила вида

и для нее указано, кроме этих правил, еще некоторое целое положительное число

. Применевие правил вывода в ТАГ системах заключается в следующем: если слово начинается буквой

, то в нем стираются первые р букв и справа приписывается слово

Если исходное слово имеет длину Р, то правила вывода к нему не применимы.
С каждой системой правил вывода связываются следующие две основные проблемы: 1) проблема остановки: рекурсивна или нет совокупность всех тех слов, начиная с которых процесс применения правил вывода обрывается; 2) проблема выводимости: для каждого ли слова является рекурсивной совокупность всех тех слов, которые получаются за конечное число применений правил вывода.
Существуют такие ЛАГ и ТАГ системы, что проблема выводимости для них алгоритмически неразрешима. Пусть s — максимальная длина правых частей правил вывода,
— минимальная длина их. Показано, что при
существует ТАГ система с неразрешимой проблемой остановки и при
— такая же ЛАГ система.
Лит.: Wang Н. Tag systems and Lag systems. «Mathematische annalen», 1963, B. 152. H. 1.
М. И. Кратко.