|
"
0
C
F
G
H
K
L
N
P
S
T
W
Z
А
Б
В
Г
Д
Е
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Э
Ю
Я
РАЗРЕШИМОЕ МНОЖЕСТВОЗначение РАЗРЕШИМОЕ МНОЖЕСТВО в математической энциклопедии: множество конструктивных объектов какого-либо фиксированного типа, допускающее проверку принадлежности к нему его элементов при помощи алгоритма. Фактически мы можем ограничиться понятием Р. м. натуральных чисел, т. к. более общий случай может быть сведен к данному при помощи соответствующей нумерации рассматриваемых объектов. Множество Мнатуральных чисел наз. р а з р е ш и м ы м, если существует такая общерекурсивная функция f, что Многие известные математич. проблемы (такие, как проблема тождества, проблема гомеоморфии, 10-я проблема Гильберта, проблема разрешимости в математич. логике) состоят в требовании доказать или опровергнуть утверждение о том, что нек-рые конкретные множества суть Р. м. Известные (отрицательные) решения перечисленных выше проблем состоят в установлении неразрешимости соответствующих им множеств (см. также Алгоритмическая проблема). Лит.:[1] У с п е н с к и й В. А., Лекции о вычислимых функциях, М., 1960. Н. М. Нагорный. |
|
|
|
В этом случае f и представляет собой алгоритм, проверяющий принадлежность к Мнатуральных чисел. В самом деле, 
равносильно тому, что f(n)=0. Р. м. натуральных чисел часто наз. также о б щ е р е-к у р с и в н ы м, или р е к у р с и в н ы м, м н о ж ес т в о м.