РАЗРЕШИМЫЙ ПРЕДИКАТ

такой n-местный предикат Р, заданный на нек-ром множестве конструктивных объектов (напр., натуральных чисел) М, для к-рого существует алгоритм, позволяющий для любого набора а _1; . . ., а _п элементов множества Мнайти значение (И или Л) предиката Рна этом наборе. Иными словами, предикат является разрешимым, если он, рассматриваемый как n-местная функция на Мсо значениями во множестве {И, Л}, является вычислимой функцией.

Когда в качестве математич. уточнения понятия вычислимости используется понятие рекурсивной функции или какое-либо эквивалентное понятие, то вместо "Р. п." обычно употребляется термин "рекурсивный предикат". В. Е. Плиско.