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

РАЗРЕШЕНИЯ ПРОБЛЕМА

Значение РАЗРЕШЕНИЯ ПРОБЛЕМА в математической энциклопедии:

алгоритмическая проблема, в к-рой для заданного множества Атребуется построить алгоритм, разрешающий Аотносительно другого множества В, включающего , т. е. такой алгоритм , к-рый применим ко всякому элементу из В, причем , если , и , если . Важным классом алгоритмич. проблем являются Р. п. для формальных теорий, то есть Р. п. множества всех доказуемых в теории формул (множество А).относительно множества всех формул теории (множество В).

Термин "Р. п." следует отличать от термина "проблема разрешимости", означающего вопрос о разрешимости той или иной математической (напр., алгоритмической) проблемы. В. Е. Плиско.