Итак, главный вопрос, стоящий перед нами, можно сформулировать следующим образом. Пусть V — множество чисел, которые может напечатать универсальная машина U (это множество иногда называют универсальным множеством). Разрешимо множество V или нет? Если оно разрешимо, то мечта Лейбница осуществима; если же нет, то его стремления никогда не смогут быть реализованы. Поскольку V эффективно перечислимо (ведь оно генерируется машиной U), то вопрос сводится к тому, существует ли некая машина М>a, которая сможет напечатать дополнение V, а именно множество V̅. Иначе говоря, существует ли такая машина М>a, которая печатает те и только те числа, которые машина U не печатает? На этот вопрос можно дать исчерпывающий ответ лишь на основании утверждений 1 и 2, о которых мы упоминали выше.
Теорема L. Множество V̅ не является эффективно перечислимым: для любой заданной машины М>a либо существует какое-то число, принадлежащее множеству V̅, которое машина М>a не может напечатать, либо машина М>a напечатает по крайней мере одно число, которое принадлежит не множеству V̅, а множеству V.
Сумеет ли читатель доказать теорему L?
Рассмотрим также следующий частный случай. Пусть у нас имеется утверждение о том, что машина М>5 перечислила множество V̅. Чтобы опровергнуть это утверждение, достаточно отыскать некоторое число n, показав при этом, что либо оно принадлежит множеству V̅, но не может быть напечатано машиной М>5, либо оно не принадлежит множеству V, но машина М>5 может его напечатать. Сумеете ли вы найти такое число n?
Я приведу решение этой задачи сразу, а не в конце главы, — по существу, это решение просто повторяет доказательство Гёделя.
Итак, возьмем произвольное число а. Согласно утверждению 2, машина М>a напечатает число x*x, если и только если машина М>2a напечатает число х. Но, согласно утверждению 1, машина М>2a напечатает число х, если и только если универсальная машина U напечатает число 2а*х, или, что то же самое, если число 2а*х принадлежит множеству V. Следовательно, машина М>a напечатает число x*x, если и только если число 2a*х входит в V. В частности (положив x равным 2а), машина М>a напечатает число 2a*2a, если и только если число 2a*2a принадлежит множеству V. Итак, либо (1): машина М>a напечатает число 2a*2a, и число 2a*2a принадлежит множеству V; либо (2): машина М>a не напечатает число 2a*2a, и число 2a*2a принадлежит множеству V.
Если выполнено условие (1), то машина Ма напечатает число 2a*2a, которое входит не в V̅, а в V; это означает, что машина М>a не генерирует множество