Теория алгоритмов. Зюзысов В.М. - 52 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

…
2×23
2
2
×
24
2
– 1 = 24
2
+ 23×24 + 23
25
2
+ 23×25 + 22
…
47
2
+ 23×47
48
2
+ 23×48 – 1 = 48
2
+ 22×48 + 47
49
2
+ 22×49 + 46
…
95
2
+ 22×95
96
2
+ 22×96–1 = 96
2
+ 21×96 + 95
97
2
+ 21×97 + 94
…
191
2
+ 21×191
192
2
+ 21×192–1 = 192
2
+ 20×192 + 191
193
2
+ 20×193 + 190
…
383
2
+20×383
384
2
+20×384–1 = 384
2
+19×384+383
385
2
+19×385+382
…
767
2
+19×767
768
2
+19×768–1 = 768
2
+18×768+767
769
2
+18×769+766
…
1535
2
+18×1535
1536
2
+18×1536–1 = 1536
2
+17×1536+1535
1537
2
+17×1537+1534
…
…
…
Эта последовательность доходит до числа из 121 210 695 цифр (для сравнения
заметим, что 1000000! содержит около 5 с половиной миллионов цифр), но потом числа
только уменьшаются (так как уже не содержат в наследственном представлении
основания) вплоть до 0. G
k
(4) впервые достигает 0 для k=3(2
402653211
-1) ≈ 10
121210695
.
Набросок доказательства теоремы Гудстейна
Будем использовать трансфинитные ординалы.
7
Пусть, как обычно, ω обозначает
ординал, равный порядковому типу множества натуральных чисел; а ординал ε
0
обозначает
.
sup( , , ,...)
ω
ωω
ωω ω
Для любого натурального числа n и любого основания b пусть B
b
(n) обозначает
выражение, полученное из наследственного представления числа n по основанию b, после
синтаксической замены b на ординал ω. Например, так как наследственное представление
266 есть
+ 2
21
2
2
+
2
+ 2, то B
2
(266) =
1
ω
ω
ω
+
+ ω
ω
+ ω.
Очевидно, B
b
(n) есть ординал, меньший ε
0
и представленный в виде
«экспоненциального полинома» относительно ω (канторова нормальная форма).
Имеем следующие свойства (для любых натуральных n и m и любого основания
b>1):
1. B
b
(n)=0 ⇔ n=0;
7
См., например, [18].

Страницы