Главная > Энциклопедия кибернетики. Т.1
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

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

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

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

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

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

М. И. Кратко.

1
Оглавление
email@scask.ru