" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

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

Значение РАЗРЕШИМЫЙ ПРЕДИКАТ в математической энциклопедии:

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

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