110 МАТЕМАТИКА М УДК 519.716 Алгоритмическая неразрешимость проблемы полноты для полиномов с целыми коэффициентами Н. Ф. Алексиадис * Исследована проблема полноты для полиномиальных функций с целыми коэффициентами. <...> Доказано, что система функций является полной только тогда, когда она целиком не содержится ни в одном предполном классе. <...> Мощность множества всех предполных классов равна континууму. <...> Каждая полная система имеет базис, более того, для любого положительного целого числа n имеется базис мощности n. <...> Обозначим через FG – множество всех всюду определенных функций f (x1, x1, ., xn), переменные которых определены на множестве G, и сами функции принимают значения из этого же множества G. <...> Предполагается, что множество FG – содержит и все функции от нулевого числа переменных, т.е. функции, являющиеся просто элементами (константами) G. <...> Так как в данной работе изучается функциональная система, которая состоит из всюду определенных функций, то определения функциональной системы и других понятий рассматриваются только для всюду определенных функций. <...> В этом случае мы говорим, что xi является существенной переменной функции f (x1, ., xi–1, xi, xi+1, ., xn). <...> Алгебра FG = (FG , O), где FG — некоторое непустое подмножество множества FG –, O — некоторое множество операций, при этом эти операции замкнуты относительно множества FG, называется функциональной системой (ф.с.) <...> Для произвольного подмножества M множества FG обозначим через IO(M) множество всех функций из FG, которые получаются из M с помощью конечного числа применения операций из O. <...> С замыканием множества естественным образом можно связать оператор замыкания. <...> Оператор, переводящий произвольное подмножество M множества FG на множество IO(M), называется оператором замыкания (относительно операций из O) и обозначается через IO. <...> Ясно, что: • IO(M) является замкнутым классом (M FG ); • пустое множество является замкнутым классом; сом. • все множество FG также является, замкнутым <...>