Принцесса или тигр?

Итак, возьмем произвольное число а. Согласно утверждению 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 не генерирует множество V̅, потому что она может напечатать по крайней мере одно число 2a*2a, которое не входит в множество V̅. Если же выполняется (2), то мы опять получаем, что машина М_a не генерирует множество V̅ поскольку число 2a*2a принадлежит множеству V̅, а машина М_a это число напечатать не может. Итак, в обоих случаях машина М_a не генерирует множество V̅. В силу произвольности выбора а это означает, что никакая машина не может перечислить множество V, и, следовательно, это множество не является эффективно перечислимым.

Конечно, в частном случае а = 5 число n окажется равным 10*10.

Но все же какое это имеет отношение к мечтам Лейбница? Строго говоря, мы не можем ни доказать, ни опровергнуть возможность осуществления лейбницевых надежд, поскольку они никогда точно не формулировались. Ведь во времена Лейбница не существовало строгого определения понятий «вычислительная машина» или «генерирующая машина»; соответствующие точные определения были получены лишь в нашем веке. Подобных определений имеется много (их вводили Гёдель, Эрбран, Клини, Черч, Тьюринг, Пост, Смаллиан, Марков и многие другие), однако было проверено, что все они эквивалентны между собой. И если под словом «разрешимо» понимать разрешимость в соответствии с любым из этих эквивалентных определений, то мечта Лейбница оказывается неосуществимой по той простой причине, что сами машины можно перенумеровать таким образом, что утверждения 1 и 2 обязательно будут выполняться. Тогда по теореме L множество V, генерируемое универсальной машиной, оказывается неразрешимым — оно будет лишь полу разрешимо. Следовательно, не существует никакой «чисто механической» процедуры, с помощью которой можно было бы узнать, какие утверждения доказуемы в той или иной системе аксиом, а какие нет. Таким образом, любая попытка изобрести некий хитроумный «механизм» для решения всех математических задач обречена на провал.

Это означает, что, выражаясь пророческими словами известного логика Эмиля Поста (1944), математическое мышление является и всегда будет оставаться по сути своей сугубо творческим процессом. Или, как остроумно заметил математик Пол Розенблум, — человеку никогда не избавиться от необходимости пользоваться своим умом, сколько бы ума он не приложил к этому.