Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Алексиадис Н.Ф.
Об алгоритмической неразрешимости распознавания А-функции в функциональной системе полиномов с целыми коэффициентами
Аннотация:
A-функция в функциональной системе F=(F,O) - это аналог функции Шеффера в двузначной логике, т.е. это функция, из которой с помощью заданных операции из O можно получить все заданные функции множества F. В настоящей работе рассматривается задача: существует ли алгоритм, который для любого заданного полинома с целыми коэффициентами выясняет - является он A-функцией или нет; другими словами, в функциональной системе полиномов с целыми коэффициентами проблема распознавания A-функции алгоритмически разрешима или нет? Ответ отрицательный: оказывается, что в функциональной системе полиномов с целыми коэффициентами проблема распознавания A-функции алгоритмически неразрешима.
