RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Математического института имени В. А. Стеклова // Архив

Тр. МИАН СССР, 1967, том 93, страницы 3–42 (Mi tm2824)

Общая теория алгорифмов и исчислений

Понятие строгой представимости в общей теории исчислений

С. Ю. Маслов


Аннотация: Выявление общих черт предлагавшихся в литературе уточнений понятий порождаемого множества приводит к понятию исчисления в базисе порождения. Основным объектом изучения является понятие строгой представимости перечислимых множеств исчислениями в базисах порождения (т.е. представимости без помощи вспомогательных слов). Выясняется, что для любого базиса порождения, в котором алгорифмически проверяемо свойство “слово выводимо из списка слов за один шаг применения правила вывода”, осуществимо перечислимое множество, не являющееся строго представимым. Доказывается ряд теорем о свойствах различных способов порождения множеств в базисах порождения, выявляются возможности строгого представления множеств исчислениями. Вопросы, рассматриваемые в статье, ставятся и изучаются также и в более общей форме (в терминах понятия строгого представления множества исчислением при помощи алгорифма).
Библ. – 22 назв.

УДК: 51.01+518.5



Реферативные базы данных:


© МИАН, 2024