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