Принцесса или тигр   ::   Смаллиан Рэймонд

Две машины, толкующие о себе, а также друг о друге



Добавим к четырем нашим символам еще один — символ 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, NRA-X. Кроме того, пусть нам известно, что первая машина печатает только истинные утверждения, а вторая — только ложные. Условимся называть некоторое утверждение доказуемым в том и только том случае, если оно допускает распечатку первой машиной, и ложным — в том и только том случае, если оно: может быть напечатано второй машиной.