Аналогично, если машина выдаст нам утверждение РА — X, тогда (поскольку утверждение РА — X должно быть истинным) она должна напечатать нам также и выражение X—X. Помимо этого, если машина напечатает утверждение NP—X, тогда она не сможет напечатать утверждение Р—X, поскольку эти два высказывания не могут одновременно являться истинными: ведь первое из них утверждает, что машина не может напечатать выражение X, а второе — что машина может его напечатать. Следующая задача высвечивает идею Гёделя так хорошо, что лучше трудно себе представить. 1. На редкость гёделева задача. Найдите истинное утверждение, которое машина не может напечатать! 2. Дважды гёделева головоломка. Все исходные условия остаются прежними — и, в частности, то, что машина абсолютно точна. Пусть у нас имеются утверждение X и утверждение Y; одно из них является истинным, но не допускающим распечатки; однако, пользуясь лишь условиями, вытекающими из правил 1—4, мы не можем сказать, какое именно это утверждение, X или Y. Можете ли вы найти такие утверждения X и Y? (Подсказка: найти такие утверждения X и Y, чтобы утверждение X говорило Стр. 190 нам о том, что Y допускает распечатку, а в утверждении Y говорилось бы о том, что X не допускает распечатки. Существуют два способа построения таких утверждений, причем оба они связаны с законами Фергюссона!) 3. Трижды гёделева проблема. Построить такие утверждения X, Y и Z, чтобы X говорило о том, что Y допускает распечатку, Y говорило бы о том, что не допускает распечатки, a Z—о том, что X в свою очередь вновь допускает распечатку, и показать, что по крайней мере одно из этих утверждений (правда, нельзя сказать, какое именно) должно быть истинным, но не допускающим распечатки на машине. Две машины, толкующие о себе, а также друг о друге Добавим к четырем нашим символам еще один— символ R. Таким образом, теперь у нас пять символов: Р, R, N, А,—. Пусть нам даны две машины, М1 и М2, каждая из которых может печатать различные выражения, составленные из этих пяти символов. При этом под символом Р в данном случае мы будем подразумевать «допускающий распечатку первой машиной», а под символом R—«допускающий распечатку второй машиной». Таким образом, запись Р—X означает, что выражение X допускает распечатку первой машиной, а запись R — X—что выражение X допускает распечатку второй машиной. Запись РА—X означает, что ассоциат выражения X допускает распечатку первой машиной, а запись RA—X показывает, что ассоциат выражения X допускает распечатку второй машиной. Наконец, «фразы» NP—X, NR — X, NPA—X, NRA — X говорят соответственно о следующем: выражение X не допускает распечатки первой машиной; выражение X не допускает распечатки второй машиной; выражение X—X не допускает распечатки первой машиной; выражение X—X не допускает распечатки второй машиной. Под утверждением мы будем теперь понимать любое выражение одного из следующих восьми типов: Р—X, R — X, NP—X, NR—X, РА—Х, RA—X, NPA—X, — 118 —
|