ЛАГ И ТАГ СИСТЕМЫ

— разновидности Поста исчислений, отличающиеся специфическими правилами вывода. ЛАГ системы имеют правила вида которые применяются следующим образом: если первые (5 букв слова суть то в нем стирается первая буква, т. е. и справа к этому слову дописывается слово может быть и пустым) ТАГ системы имеют правила вида и для нее указано, кроме этих правил, еще некоторое целое положительное число . Применевие правил вывода в ТАГ системах заключается в следующем: если слово начинается буквой , то в нем стираются первые р букв и справа приписывается слово Если исходное слово имеет длину Р, то правила вывода к нему не применимы.

С каждой системой правил вывода связываются следующие две основные проблемы: 1) проблема остановки: рекурсивна или нет совокупность всех тех слов, начиная с которых процесс применения правил вывода обрывается; 2) проблема выводимости: для каждого ли слова является рекурсивной совокупность всех тех слов, которые получаются за конечное число применений правил вывода.

Существуют такие ЛАГ и ТАГ системы, что проблема выводимости для них алгоритмически неразрешима. Пусть s — максимальная длина правых частей правил вывода, — минимальная длина их. Показано, что при существует ТАГ система с неразрешимой проблемой остановки и при — такая же ЛАГ система.

Лит.: Wang Н. Tag systems and Lag systems. «Mathematische annalen», 1963, B. 152. H. 1.

М. И. Кратко.