В выходны читал заметки Пенроуза относительно искусственого интеллекта, мышления и т.п. ("Новый ум короля") Книга очень любопытная, хотя местами, где он пытается уходить в беллетристику, бывает скучновата. Однако, я там нашед еще один блестящий пример, когда "очевидное" не верно. Речь идет об удивительной теореме  Гудстейна (Goodstein R.L. Journal of symbolic logic)

Чтобы понять суть этой теоремы, рассмотрим любое целое положительное число, скажем, 581. Для начала мы представим его в виде суммы различных степеней числа 2:



581 = 2⁹+2⁶+2²+1.



(Такая процедура применяется для формирования двоичного представления числа 581, а именно, приведения его к виду 1001000101, где единицы соответствуют тем степеням двойки, которые присутствуют в таком представлении, а нули -- тем степеням, которых нет.) Далее можно заметить, что "показатели" в этом выражении -- т.е. 9, 6 и 2 -- могут быть, в свою очередь, представлены аналогичным образом (9=2³+1, 6=2²+2¹, 2=2¹); и тогда мы получим (вспоминая, что 2¹ = 2)



581 = 2^2**3+1+2^2**2+2+2²+1.

** - здесь и далее две звездочки означают возведение в степень.

Здесь все еще есть показатель больший, чем двойка -- в данном случае это "3", -- для которого тоже можно написать разложение 3 = 2¹ + 1, так что в конце концов мы будем иметь



581 = 2^2**2+1+2^2**2+2+2²+1.



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

(а) увеличивать "основание" на единицу,

(б) вычитать единицу.

Под "основанием" здесь понимается просто число "2", фигурирующее в исходном выражении, но мы можем сделать то же самое и с бОльшими основаниями: 3,4,5,6,... . Давайте посмотрим, что произойдет при применении операции (а) к последнему разложению числа 581, в результате которой двойки становятся тройками:



3^3**3+1+1+3^3**3+3+3³+1



(что дает -- если выписать его в обычной форме -- сороказначное число, начинающееся с 133027946...). После этого мы применяем (б) и получаем



3³³⁺¹⁺¹+3³³⁺³+3³



(т.е. по-прежнему сорокозначное число, начинающееся с 133027946...). Далее мы выполняем (а) еще раз и получаем



4^4**4+1+1+4^4**4+4+4⁴



(это уже значительно большее число, состоящее из 618 знаков, которое начинается с 12926802...). Следующая операция -- вычитание единицы -- приводит к выражению



4⁴⁴⁺¹⁺¹+4⁴⁴⁺⁴+3x4³+3x4²+3x4+3



(где тройки получаются по той же причине, что и девятки в обычной десятичной/ записи, когда мы получаем 9999, вычитая 1 из 10000). После чего операция (а) дает нам



5^5**5+1+1+5^5**5+5+3x5³+3x5²+3x5+3



(число, которое имеет 10923 знака и начинается с 1274...). Обратите внимание, что коэффициенты "3", которые возникают при этом, с необходимостью меньше, чем основание (в данном случае 5), и не изменяются с возрастанием последнего. Применяя (б) вновь, имеем число



5⁵⁵⁺¹⁺¹+5⁵⁵⁺⁵+3x5³+3x5²+3x5+2,



над которым мы опять производим последовательно действия (а), (б), (а), (б), ... и т.д., насколько возможно. Вполне естественно предположить, что этот процесс никогда не завершится, потому что каждый раз мы будем получать все бОльшие и бОльшие числа. Однако это не так: как следует из поразительной теоремы Гудстейна, независимо от величины исходного числа (581 в нашем примере), мы в конце концов получим нуль!

Кажется невероятным, но это так. А чтобы в это поверить, можно проделать вышеописанную процедуру, для начала -- с числом "3" (где мы раскладываем тройку как 2¹ + 1, что дает последовательность 4, 3, 4, 2, 1, 0); а затем -- что более важно -- попробовать то же самое с "4" (при этом стартовое разложение в виде 4 = 2² приводит к вполне закономерно возрастающему ряду 4, 27, 26, 42, 41, 61, 60, 84, ..., который доходит до числа из 121210695-ти знаков, после чего уменьшается вплоть до нуля!).

Это действительно поразительно...