Теорема Гудстейна
У Савватеева на ютубе - познавательнейший мини-курс лекций про теорему Гудстейна, а вдогонку - про теорему Гёделя.
Рассмотрим игру 3x+1 шучу, рассмотрим гораздо более злую последовательность.
Возьмём некое стартовое число и разложим его на сумму степеней двойки, а затем показатели тоже разложим на суммы степеней, и так далее до показателей 0 и 1.
И будем применять такое действие: пусть у нас на k-м шаге разложение по основанию k, тогда на шаге k+1 мы механически заменяем основание с k на k+1, а затем вычитаем из полученного числа 1 (при этом разложение, конечно, тоже поменяется).
Например, для числа 3
- G(3)(2) = 2^1 + 1
- G(3)(3) = 3^1 + 1 - 1 = 3^1
- G(3)(4) = 4^1 - 1 = 3
- G(4)(4) = 3 - 1 = 2
- G(4)(5) = 2 - 1 = 1
- G(4)(6) = 1 - 1 = 0
Например, для числа 13 уже появится степень степени:
13 = 1•2^3 + 1•2^1 + 1; в свою очередь, 3 = 1•2^1 + 1;
итого, 13 = 1•2^(1•2^1 + 1) + 1•2^1 + 1
- G(13)(2) = 13
- G(13)(3) = 1•3^(1•3^1 + 1) + 1•3^1 + 1 - 1 = 1•3^(1•3^1 + 1) + 1•3^1 = 84
- G(13)(4) = 1•4^(1•4^1 + 1) + 1•4^1 - 1 = 1•4^(1•4^1 + 1) + 3 = 259
- G(13)(5) = 1•5^(1•5^1 + 1) + 2 = 15'627
- G(13)(6) = 1•6^(1•6^1 + 1) + 1 = 279'937
- G(13)(7) = 1•7^(1•7^1 + 1) = 5'764'801
- G(13)(8) = 1•8^(1•8^1 + 1) - 1 = 8^9-1
= (8-1) • (8^8+8^7+8^6+8^5+8^4+8^3+8^2+8^1+1)
= 7•8^(8^1) + 7•8^7 + 7•8^6 + 7•8^5 + 7•8^4 + 7•8^3 + 7•8^2 + 7•8^1 + 7 - (следующие 7 шагов тривиальные...)
- G(13)(15) = 7•15^(15^1) + 7•15^7 + 7•15^6 + 7•15^5 + 7•15^4 + 7•15^3 + 7•15^2 + 7•15^1
Ну и так далее.
Мы видим, что, если записать разложение в виде дерева возведений в степень, то на каждом шаге высота последней ветки этого дерева убывает, но ширина может довольно люто разрастаться. Не говоря уж о том, что основания растут. Поэтому сами числа тоже растут, и гораздо круче экспоненты.
Но вот убывание высоты даёт нам надежду, что рано или поздно это дерево превратится в последнюю веточку с нулевым показателем, и мы добежим до нуля, где и остановимся.
Теорема Гудстейна утверждает, что последовательность для любого числа, начиная с разложения на любую степень (мы начали с 2) придёт к 0.
А мета-теорема Гудстейна (доказательство Кирби-Париса) утверждает, что фиг вы докажете теорему Гудстейна, оставаясь в рамках арифметики Пеано!
Бамбук для курения:
английская википедия
Ютуб Алексея Савватеева, а именно лекции Николая Казимирова (у него есть свой канал, кстати)
Click to viewСамая мякотка, что в доказательстве мета-теоремы появляется функция Аккермана. То есть, это не просто забавная фигня, которая вычисляется за гигантское время и даёт гигантские числа, а важный инструмент.