RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1990, том 2, выпуск 2, страницы 112–120 (Mi dm855)

Эта публикация цитируется в 1 статье

Полнота по модулю идеала в функциональных системах программного типа

Ю. В. Голунков


Аннотация: В функциональной системе программного типа основное множество $R$ состоит из функций и предикатов, а операции задаются схемами программ из некоторого класса или эквивалентными им программными операциями. Изучаются системы с одноместными частично рекурсивными функциями и предикатами. Для идеала $J$ в решетке рекурсивно перечислимых множеств определяются $J$-полными такие множества $M\subseteq R$, в замыкании которых для всякого элемента $t\in R$ и множества $X\in J$ найдется элемент $t'$, совпадающий с $t$ на $X$. Устанавливается, что проблема $J$-полноты не проще проблемы обычной полноты, если идеал $J$ содержит бесконечные множества, и потому уникальна полнота по идеалу конечных множеств, получившая ранее полное решение.

УДК: 519.716.37

Статья поступила: 10.07.1989


 Англоязычная версия: Discrete Mathematics and Applications, 1992, 2:1, 59–68

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


© МИАН, 2024