Читаем Принцесса или тигр? полностью

Теперь представим себе, что программа для генерирующей машины записывается не на естественном языке, а кодируется в виде некоторого целого числа (представляющего собой цепочку цифр); кодирование можно осуществить так, чтобы каждое положительное целое число представляло собой номер определенной программы. Пусть Мn — это машина, программа которой имеет кодовый номер n. Расположим теперь все генерирующие машины в виде бесконечной последовательности М1, М2…, Мn… (М1 — это машина с номером программы 1, М2 — машина с номером программы 2 и т. д.)

Для любого множества чисел А (естественно, имеется в виду множество положительных целых чисел) и для любой машины M мы будем говорить, что машина M генерирует множество А, или, иначе, машина M перечисляет множество А, если каждое число, входящее в множество А, в конце концов будет напечатано машиной M, и в то же время ни одно число, не входящее в А, этой машиной напечатано не будет. Множество А мы будем называть эффективно перечислимым (иногда говорят — рекурсивно перечислимым), если существует хотя бы одна машина Мi которая перечисляет множество А. Кроме того, мы будем говорить, что множество А разрешимо (или рекурсивно), если существуют одна машина Мi, которая перечисляет само множество А, и другая машина Мj которая перечисляет множество всех чисел, не входящих в А. Таким образом, множество А является разрешимым том и только том случае, если и A, и его дополнение являются эффективно перечислимыми.

Предположим, что множество А — разрешимо и у нас имеются машина Мi, которая генерирует А, и машина Мj которая генерирует дополнение . Тогда оказывается, что существует эффективный способ, позволяющий определять, входит ли некоторое число n в множество А или нет. Допустим, к примеру, нас интересует, входит ли в множество А число 10. Мы приводим в действие обе машины одновременно и ждем. Если число 10 принадлежит множеству А, то рано или поздно это число будет напечатано машиной Мi, так что мы сразу узнаем, что число 10 входит в А. Если же число 10 не принадлежит множеству А, то в конце концов это число напечатает машина Мj — тем самым мы сразу узнаем, что число 10 не входит в А. Таким образом, в конечном итоге мы обязательно выясним, принадлежит ли число 10 множеству А или нет. (Понятно, что сказать заранее, сколько нам придется ждать, невозможно; нам известно лишь, что через какой-то конечный промежуток времени мы непременно узнаем ответ.)

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

Первое важное свойство генерирующих машин заключается в том, что можно сконструировать так называемую универсальную машину U, назначение к торой — систематически наблюдать за поведением во машин M1, М2, М3…, Мn… и, как только машина Мх напечатает число у, сразу же сообщить нам об этом. Но каким образом это сделать? Очень просто — напечатать некоторое число, скажем для данных x и у напечатать x*y, то есть число, как и ранее, состоящее из цепочки единиц длиной х, за которой следует цепочка нулей длиной у. Итак, основная команда для машины U такова: когда машина Мх напечатает число у, то напечатать число x*y.

Допустим, например, что машина Мa запрограммирована на генерирование множества нечетных чисел, а машина Мb — на генерирование множества четных чисел. Тогда машина U будет печатать числа а*1, а*3, а*5 и т. д., а также числа b*2, b*4, b*8 и т. д., однако она никогда не напечатает число а*4 (поскольку машина Мa никогда не напечатает число 4) или число b*3 (поскольку машина Мb никогда не напечатаем число 3).

Далее, поскольку машина U имеет свою собственную программу, то, следовательно, она входит в семейство программируемых машин M1, М2…, Мn… Это значит, что существует некоторая машина Мk, номер программы которой k совпадает с номером программы машины U, причем машина Мk и есть сама машина U! (В строгой научной статье я указал бы, что это за число k.)

Перейти на страницу:

Все книги серии Математическая мозаика

Как же называется эта книга?
Как же называется эта книга?

Книга американского профессора Р. Смаллиана, написанная в увлекательной форме, продолжает серию книг по занимательной математике и представляет собой популярное введение в некоторые проблемы математической логики. Сюда входят более 200 новых головоломок, созданных необычайно изобретательным автором. Задачи перемежаются математическими шутками, анекдотами из повседневной жизни и неожиданными парадоксами. Завершает книгу замечательная серия беллетризованных задач, которые вводят читателя в самую суть теоремы Курта Гёделя о неполноте, — одного из замечательнейших результатов математической логики 20 века.Можно сказать — вероятно, самый увлекательный сборник задач по логике. Около трехсот задач различной сложности сгруппированы по разделам, герои которых Рыцари и Лжецы, Алиса в Стране Чудес, Беллини и Челлини и даже сам граф Дракула! Если человек произносит «Я лгу» — говорит ли он неправду? Почему физики и математики по-разному решают задачи? Как вовремя распознать упыря? Ответы на эти и более серьезные вопросы Вы найдете в этом сборнике, а может быть, и ответ на вопрос «Как же называется эта книга?». Для всех, кто хочет научиться рассуждать.

Рэймонд Меррилл Смаллиан

Научная литература

Похожие книги

Простая одержимость
Простая одержимость

Сколько имеется простых чисел, не превышающих 20? Их восемь: 2, 3, 5, 7, 11, 13, 17 и 19. А сколько простых чисел, не превышающих миллиона? Миллиарда? Существует ли общая формула, которая могла бы избавить нас от прямого пересчета? Догадка, выдвинутая по этому поводу немецким математиком Бернхардом Риманом в 1859 году, для многих поколений ученых стала навязчивой идеей: изящная, интуитивно понятная и при этом совершенно недоказуемая, она остается одной из величайших нерешенных задач в современной математике. Неслучайно Математический Институт Клея включил гипотезу Римана в число семи «проблем тысячелетия», за решение каждой из которых установлена награда в один миллион долларов. Популярная и остроумная книга американского математика и публициста Джона Дербишира рассказывает о многочисленных попытках доказать (или опровергнуть) гипотезу Римана, предпринимавшихся за последние сто пятьдесят лет, а также о судьбах людей, одержимых этой задачей.

Джон Дербишир

Математика
Прикладные аспекты аварийных выбросов в атмосферу
Прикладные аспекты аварийных выбросов в атмосферу

Книга посвящена проблемам загрязнения окружающей среды при авариях промышленных предприятий и объектов разного профиля и имеет, в основном, обзорный справочный характер.Изучается динамика аварийных турбулентных выбросов при наличии атмосферной диффузии, характер расширения турбулентных струйных потоков, их сопротивление в сносящем ветре, эволюция выбросов в реальной атмосфере при наличии инверсионных задерживающих слоев.Классифицируются и анализируются возможные аварии с выбросами в атмосферу загрязняющих и токсичных веществ в газообразной, жидкой или твердой фазах, приводятся факторы аварийных рисков.Рассмотрены аварии, связанные с выбросами токсикантов в атмосферу, описаны математические модели аварийных выбросов. Показано, что все многообразие антропогенных источников загрязнения атмосферного воздуха при авариях условно может быть разбито на отдельные классы по типу возникших выбросов и характеру движения их вещества. В качестве источников загрязнений рассмотрены пожары, взрывы и токсичные выбросы. Эти источники в зависимости от специфики подачи рабочего тела в окружающее пространство формируют атмосферные выбросы в виде выпадающих на поверхность земли твердых или жидких частиц, струй, терминов и клубов, разлитий, испарительных объемов и тепловых колонок. Рассмотрены экологические опасности выбросов при авариях и в быту.Книга содержит большой иллюстративный материал в виде таблиц, графиков, рисунков и фотографий, который помогает читателю разобраться в обсуждаемых вопросах. Она адресована широкому кругу людей, чей род деятельности связан преимущественно с природоохранной тематикой: инженерам, научным работникам, учащимся и всем тем, кто интересуется экологической и природозащитной тематикой.

Вадим Иванович Романов

Математика / Экология / Прочая справочная литература / Образование и наука / Словари и Энциклопедии