2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Последовательность деревьев из TREE(3)
Сообщение20.01.2022, 14:43 
Аватара пользователя


16/05/12
70
Число $TREE(3)$ довольно часто приводится в качестве примера очень большого числа, равного максимально возможной длине последовательности деревьев из вершин с возможными 3 цветами вершин, где $i$-ое дерево не имеет в качестве inf-вложения никакие из предыдущих $0...(i-1)$ деревьев последовательности
В качестве примера везде приводится похожая картинка, подобная следующей, однако нигде не удалось найти описание, каким способом были получены эти самые деревья, составляющие начало вышеобозначенной последовательности $TREE(3)$
Изображение

Вопрос - как получены эти начальные деревья последовательности и как генерировать следующие деревья? Кроме того, как определить, что эта последовательность деревьев образует начало той самой последовательности длины $TREE(3)$?
Понятное дело, что на приведенной картинке соблюдены требования - не более 3 цветов, не более $i$ вершин в $i$-ом элементе последовательности и отсутствие inf-вложения слева направо - но ведь это не единственно возможный вариант начала последовательности, в том смысле, что она не продлится длиной $TREE(3)$ элементов, но вполне себе может продлиться $k$ элементов, и только на $k+1$-ом дереве узнается, что она была неправильной, и чтобы достичь длины $TREE(3)$, надо вернуться к началу и переделать ее элементы
Если на картинке все-таки правильные начальные элементы той самой последовательности длины $TREE(3)$, то как их получили и проверили на правильность?

Попытки подступиться к решению вопроса посредством гугления не увенчались успехом - попадаются только научно-популярные статьи с рассказами о невероятной величине числа $TREE(3)$ и одна и та же вышеприведенная картинка в различных дизайнерских вариациях
Если о настоящих статьях, более-менее интересная нашлась эта (и посмотрена через scihub), но несмотря на сертифицированное программное доказательство, никаких формул конструктивного построения $i$-ых деревьев там не обнаружилось

Кстати еще вопрос вдогонку - существует ли доказательство конечности любого $TREE(N)$ без заигрываний с бесконечными ординалами? Если мне правильно удалось понять, то здесь, как и в случае с Гудстейном, доказательство через трансфинитные штуки

 Профиль  
                  
 
 Re: Последовательность деревьев из TREE(3)
Сообщение20.01.2022, 22:54 
Заслуженный участник
Аватара пользователя


18/05/06
13440
с Территории
Здесь надо поиграться с малой tree()-функцией, чтобы понять, как эти штуки вообще работают. Основной ход примерно такой: одну ногу отщипываем по единичке, потом отращиваем остальные на все деньги.

Начало последовательности вряд ли известно точно, как и само число (что бы это ни значило). Потыкались с разными вариантами, получили разные чудовищно громадные оценки, с трудом сравнили их - и вот, эта лучшая (пока что).

Я, впрочем, тоже охотно выслушал бы более квалифицированное объяснение.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Skipper


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group