Число Грэма и еще большие числа

[Rusit8800]

На днях увидел число Грема в википедии, которое перевернуло мое представление о больших числах.Конечно же, я захотел перевернуть мое представление о числах еще сильнее и решил ознакомится с теоремой Краскала.Мне опять стало мало, поэтому я хотел бы спросить какие числа больше числа из этой теоремы, которые что-то ЗНАЧАТ(например такие ответы как "число из теоремы Краскала+1" или $\infty$ не принимаются)

[arseniiv]

Rusit8800 в сообщении #1108269 писал(а):

или $\infty$

Это не число.

Может, перед тем как задавать вопросы, следует как минимум их уточнить? Может, вы имели в виду нестандартные действительные числа или ординалы, кто знает?

[INGELRII]

Присоединяюсь. Определите, что значит понятие ЗНАЧИТ. Скажем, число "число из теоремы Краскала $+1$" тоже кое-что значит: это, например, наименьшее целое число, большее, чем число из теоремы Краскала. Чем это вас не устраивает?!

[Anton_Peplov]

Господа, ну ладно вам придираться.
В. П. Катаев хотел сказать ТС имел в виду (пусть он меня поправит, если что):
1. Число - это действительное число. А про бесконечность он так, случайно брякнул.
2. Число "что-то значит" - т.е. оно использовалось в доказательстве нетривиального факта, о чем можно прочесть в математической литературе.

[Rusit8800]

1."Значит" означает это данное число использовать в доказательстве теоремы, леммы и т.д. Например, то же число Грэма.Ну, или просто какие-нибудь числа больше числа из теоремы Краскала имеющие собственное название(как гуголплекс, хоть он меньше этого числа, но все равно).
2. Если бесконечность не число, то что?

[arseniiv]

Ничего. Бесконечности самой по себе не существует. В математике много разных видов бесконечности, не сводящихся к чему-то одному, хотя и связанных.

[Anton_Peplov]

Rusit8800 в сообщении #1108318 писал(а):

2. Если бесконечность не число, то что?

Бесконечность - не число, а бесконечность. Так же как вектор - не число, а вектор. Если кратко, в определении понятия натурального (и через него - действительного) числа участвует аксиома Архимеда: для любого числа $a$ можно записать в выражении $1 + 1 + 1+...$ столько слагаемых, что сумма будет больше $a$. Бесконечность этому требованию не удовлетворяет и потому числом не является.
А лучше создайте про это отдельную тему в ПРР. Не то завяленная Вами изначально (и интересная) тема по отысканию очень больших поименованных чисел тут же и утонет в разъяснениях, что такое число и что такое бесконечность.

[arseniiv]

На самом деле, парочка тем с перечислением всех возможных бесконечностей здесь уже есть, надо только, чтобы повезло их найти.

[Anton_Peplov]

Мне за разумное время найти тему с перечислением всех видов бесконечности не удалось. Навскидку:
- есть понятие бесконечного множества и его мощности. Есть арифметика порядковых чисел.
- есть значок $x \to \infty$, который означает, что последовательность $\{x\}$ неограниченна. Обычно еще конкретизируют до $x \to + \infty$ или $x \to -\infty$, что означает, что последовательность неограниченно возрастает или убывает; монотонность при этом как будто не предполагается, а впрочем, не помню. Как такового понятия бесконечности здесь нет, есть значок для сокращения записи.
- есть нестандартный анализ.
- есть разные упражнения по расширению числовой прямой за счет двух новых элементов $+\infty$ и $-\infty$, подобные тем, что делают Ильин и Позняк в своем учебнике матана в главе про измеримые функции. Но над этими элементами остаются неопределенными некоторые арифметические операции (например, $\infty - \infty$), что, как и аксиома Архимеда, не позволяет считать их числами.

Наверное, есть что-то еще, но я иссяк.

P.S. Неплохо бы, чтобы кто-нибудь из профессиональных математиков взялся написать FAQ "какие бывают бесконечности и с чем их едят" объемом так в страничку, с коротеньким абзацем про каждый вид бесконечности и ссылкой на книжки, в которых о нем можно узнать подробнее. Чтобы всех последующих вопрошающих без лишних разговоров отсылать к нему.

[arseniiv]

Anton_Peplov в сообщении #1108333 писал(а):

Наверное, есть что-то еще, но я иссяк.

Ещё забыли элементы проективного пространства, не входящие в соответствующее аффинное/линейное. В случае $\mathbb R,\mathbb C$ это одна беззнаковая $\infty$.

Anton_Peplov в сообщении #1108333 писал(а):

Как такового понятия бесконечности здесь нет, есть значок для сокращения записи.

Хотя в $\mathbb R\cup\{\pm\infty\}$ или $\mathbb R\cup\{\infty\}$ с правильной топологией такие пределы являются нормальными элементами соответствующих множеств.

[Rusit8800]

С бесконечностью все ясно, но как насчет больших чисел?

[fractalon]

Я думаю, вам будет интересно узнать о функции усердных бобров (погуглите, материала много даже русскоязычного). Это функция которая растёт быстрее любой вычислимой функции. Вот вы в определении числа Грэма встречали функцию $f(n)$, рекурсивно определённую через гипероперации (стрелочки эти) такую, что $f(64)$ - как раз число Грэма. А функция усердных бобров растёт быстрее чем $f(n)$. И даже быстрее чем $f(f(n))$. И даже быстрее чем ${f^{f(n)}}(n)$. Просто потому что для вычисления этих функций можно написать программу (для фиктивного такого, супермощного, бесконечноразрядного компьютера) и вычислить за конечное время. На английской википедии есть доказательство невычислимости функции усердных бобров, его легко можно самому модифицировать до доказательства того факта, что это больше любой вычислимой функции. Успехов в поисках прекрасного.

И на хабрахабре была ещё пара статей относительно недавно. Но там про это как раз и рассказывалась, число Грэма, усердные бобры и т. д. Хотя, может, что-то новое и там обнаружите.

Ведь сколько вы ни будете узнавать всё больших и больших чисел, вам будет не хватать и не хватать. Так рассмотрите лучше функцию, которая растёт быстрее чем, всё, что вы можете вычислить (и, соответственно, представить в плане масштаба).

[worm2]

fractalon писал(а):

функция усердных бобров растёт быстрее чем $f(n)$. И даже быстрее чем $f(f(n))$. И даже быстрее чем ${f^{f(n)}}(n)$.

Так-то оно так, но речь-то про конкретное число. Можно ли сказать, что $\text{Бобёр}(64) > f(64)$. Я думаю, сравнить эти два числа — очень непростая задача. И почему мы интересуемся именно $f(64)$ ? Потому что именно оно встречается в теореме, которую Грэм доказал, а не $f(65)$, например, которое больше.

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

-- Вт мар 22, 2016 11:30:37 --

Подходящая задача, например — максимальная мощность спорадической простой конечной группы. К сожалению, результат слишком маленький

[Sender]

Справедливости ради, бобры теоретически тоже могут использоваться для доказательства чего-нибудь полезного. Вот выдержка из википедии:

Цитата:

In addition to posing a rather challenging mathematical game, the busy beaver functions offer an entirely new approach to solving pure mathematics problems. Many open problems in mathematics could in theory, but not in practice, be solved in a systematic way given the value of S(n) for a sufficiently large n.[2]

Consider any conjecture that could be disproven via a counterexample among a countable number of cases (e.g. Goldbach's conjecture). Write a computer program that sequentially tests this conjecture for increasing values. In the case of Goldbach's conjecture, we would consider every even number ≥ 4 sequentially and test whether or not it is the sum of two prime numbers. Suppose this program is simulated on an n-state Turing machine. If it finds a counterexample (an even number ≥ 4 that is not the sum of 2 primes in our example), it halts and notifies us. However, if the conjecture is true, then our program will never halt. (This program halts only if it finds a counterexample.)

Now, this program is simulated by an n-state Turing machine, so if we know S(n) we can decide (in a finite amount of time) whether or not it will ever halt by simply running the machine that many steps. And if, after S(n) steps, the machine does not halt, we know that it never will and thus that there are no counterexamples to the given conjecture (i.e., no even numbers that are not the sum of two primes). This would prove the conjecture to be true.

Thus specific values (or upper bounds) for S(n) could be used to systematically solve many open problems in mathematics (in theory). However, current results on the busy beaver problem suggest that this will not be practical for two reasons:

It is extremely hard to prove values for the busy beaver function (and the max shift function). It has only been proven for extremely small machines with fewer than 5 states, while one would presumably need at least 20-50 states to make a useful machine. Furthermore, every known exact value of S(n) was proven by enumerating every n-state Turing machine and proving whether or not each halts. One would have to calculate S(n) by some less direct method for it to actually be useful.
But even if one did find a better way to calculate S(n), the values of the busy beaver function (and max shift function) get very large, very fast. $S(6) > 1036534$ already requires special pattern-based acceleration to be able to simulate to completion. Likewise, we know that $S(10) > \Sigma(10) > 3 \uparrow\uparrow\uparrow 3$ is a gigantic number. Thus, even if we knew, say, S(30), it is completely unreasonable to run any machine that number of steps. There is not enough computational capacity in the known universe to have performed even S(6) operations directly.[3]

[Lukin]

(Оффтоп)

Rusit8800
1. Информация к размышлению:

fractalon в сообщении #1108393 писал(а):

Я думаю, вам будет интересно узнать о функции усердных бобров (погуглите, материала много даже русскоязычного).

2. О "Busy Beaver" на русском языке:

Lukin в сообщении #558830 писал(а):

Задача поиска усердных бобров и ее решения
Занятой бобер

3.Можно ли сказать,

worm2 в сообщении #1108408 писал(а):

что $\text{Бобёр}(64) > f(64)$. Я думаю, сравнить эти два числа — очень непростая задача.

4. Из существования универсальной машины Тьюринга следует,

Lukin в сообщении #559428 писал(а):

что мы не можем сравнить разные машины с $n$ состояниями, где $n$ - минимальное число состояний необходимых для построения универсальной машины, т.к. эти машины эквивалентны.

5. Фолиант: М.Минский "Вычисления и автоматы" Москва, "Мир", 1971 г. .pdf (гуглимо)
Параграф 14.8.1 Универсальная машина с четырьмя символами и семью состояниями (стр.328).
6. Успехов

fractalon в сообщении #1108393 писал(а):

в поисках прекрасного.