|
Математические заметки, 1972, том 11, выпуск 6, страницы 687–697
(Mi mzm9837)
|
|
|
|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
Об алгоритмической неразрешимости распознавания $A$-полноты для ограниченно-детерминированных
функций
В. А. Буевич Вычислительный центр АН СССР
Аннотация:
Рассматривается функциональная система $P$, элементами которой являются отображения, осуществляемые так называемыми конечными автоматами, ограниченно-детерминированные функции (о.-д. функции), а операциями — операции суперпозиции. Система $\mathfrak{M}$ о.-д. функций называется $A$-полной, если для любой о.-д. функции и для всякого натурального $\tau>0$ из о.-д. функции системы $\mathfrak{M}$ с помощью операций суперпозиции можно получить о.-д. функцию, совпадающую с заданной на словах длины $\tau$. Возникает вопрос: существует ли алгоритм для распознавания $A$-полноты произвольной конечной системы о.-д. функции? Показывается, что такого алгоритма не существует. Библ. 4 назв.
Поступило: 17.03.1971
Образец цитирования:
В. А. Буевич, “Об алгоритмической неразрешимости распознавания $A$-полноты для ограниченно-детерминированных
функций”, Матем. заметки, 11:6 (1972), 687–697; Math. Notes, 11:6 (1972), 417–421
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm9837 https://www.mathnet.ru/rus/mzm/v11/i6/p687
|
Статистика просмотров: |
Страница аннотации: | 198 | PDF полного текста: | 91 | Первая страница: | 1 |
|