|
Для любого множества чисел А (естественно, имеется в виду множество положительных целых чисел) и для любой машины М мы будем говорить, что машина М генерирует множество А, или, иначе, машина М перечисляет множество А, если каждое число, входящее в множество А, в конце концов будет напечатано машиной М, и в то же время ни одно число, не входящее в А, этой машиной напечатано не будет. Множество А мы будем называть эффективно перечислимым (иногда говорят — рекурсивно перечислимым), если существует хотя бы одна машина Мi котора Стр. 214 перечисляет множество А. Кроме того, мы будем говорить, что множество А разрешимо (или рекурсивно), если существуют одна машина Мi, которая перечисляет само множество А, и другая машина Мj которая перечисляет множество всех чисел, не входящих в А. Таким образом, множество А является разрешимым том и только том случае, если и A, и его дополнение А являются эффективно перечислимыми. Предположим, что множество А — разрешимо и у нас имеются машина Мi, которая генерирует А, и машина Мj которая генерирует дополнение А. Тогда оказывается, что существует эффективный способ, позволяющий определять, входит ли некоторое число n в множество А или нет. Допустим, к примеру, нас интересует, входит ли в множество А число 10. Мы приводим в действие обе машины одновременно и ждем. Если число 10 принадлежит множеству А, то рано или поздно это число будет напечатано машиной Mi, так что мы сразу узнаем, что число 10 входит в А. Если же число 10 не принадлежит множеству А, то в конце концов это число напечатает машина Mj—тем самым мы сразу узнаем, что число 10 не входит в А. Таким образом, в конечном итоге мы обязательно выясним, принадлежит ли число 10 множеству А или нет. (Понятно, что сказать заранее, сколько нам придется ждать, невозможно; нам известно лишь, что через какой-то конечный промежуток времени мы непременно узнаем ответ.) Предположим теперь, что множество А эффективно перечислимо, но неразрешимо. В таком случае у нас имеется машина Мi, которая генерирует множество А, но не окажется машины, которая генерировала бы дополнение А. Допустим, что мы опять хотим узнать, входит ли в А некоторое заданное число — скажем, число 10. Лучшее, что мы можем сделать в таком случае — запустить машину Mi, и надеяться на удачу! Теперь наши шансы узнать ответ составляют лишь 50%. Если число 10 действительно входит в множество А, то в конце концов мы обязательно это узнаем, поскольку рано или поздно машина М, напечатает это число. Если же число 10 в А не входит, то машина Мi, никогда этого числа не напечатает, однако сколько бы — 134 —
|