2014 dxdy logo

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

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


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


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



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


16/05/12
67
Число $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
13438
с Территории
Здесь надо поиграться с малой tree()-функцией, чтобы понять, как эти штуки вообще работают. Основной ход примерно такой: одну ногу отщипываем по единичке, потом отращиваем остальные на все деньги.

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

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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