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

Я не стануутомлять читателя и приводить все подробности полученного ими решения; упомяну лишь о том, что действительно представляется для нас важным. Переломный момент в их исследованиях наступил тогда, когда друзья в конце концов сумели сформулировать три ключевые особенности машины; этого оказалось достаточно для полного решения задачи. Кажется, первыми обратили внимание на эти особенности Крейг и Мак-Каллох, однако их окончательная формулировка принадлежит Фергюссону. Но прежде чем перейти к описанию особенностей машины. я позволю себе сделать небольшое отступление.

Для любого множества А положительных целых чисел, под его дополнением А понимается множество положительных целых чисел, не входящих в А. Например, если А — множество четных чисел, то его дополнением А будет множество нечетных чисел; если А — множество чисел, делящихся на 5, то А — это множество чисел, которые на 5 не делятся.

Для любого множества А положительных целых чисел под А* мы будем подразумевать множество всех положительных целых чисел х, для которых х*х является элементом множества А. Поэтому для любого числа х выражение «число х принадлежит множеству А*» эквивалентно выражению «число х*х принадлежит множеству А».

А теперь перечислим три главные особенности данной машины, которые были обнаружены Крейгом и Мак-Каллохом.

Свойство 1. Множество А8 — это множество всех чисел, которые машина может напечатать.

Свойство 2.