Приветствую Вас,уважаемые Читатели! Сегодня я хочу рассказать Вам о числовом сверхгиганте - числе Райо, которое появилось в ходе т.н. "Дуэли больших чисел".
Сражение происходило в Массачусетском технологическом институте 26 января 2007 и имело следующие правила:
- Первое правило заключается в том, что "бойцами" на доске записываются числа, а победителем становится тот, кто запишет большее.
- Второе правило заключается в том, что допускаются только кардинальные числа, обозначающие мощность некоторого конечного множества (например, числа 17, 191823123 или любое другое). Ординалы - т.е. порядковые числа, заведомо большие, чем любое из натуральных, использовать нельзя (например, ω - первый бесконечный ординал, который идет сразу же за рядом 1,2,3,.....)
- Третье правило - в недопустимости использования логических конструкций, относящихся к числам оппонента. Например, классического детского принципа : "а моё число больше, чем твоё, на один".
Каждый раз, когда Августин или Адам записывал число, его оппонент должен был ответить бОльшим числом или признать поражение.
"Мы хотели, чтобы конкурс был войной оригинальности, а не войной терпения!"
Первый ход был за Августином, который написал на доске последовательность из тридцати или сорока единиц:
Адам ответил изящно, проведя ластиком по основанию всех единиц, кроме первым двух:
А это 11 с кучей факториалов! Даже число 11 !! равняется примерно 6 × 10^286,078,170, что уж говорить об остальных.
Следующий ход был за Августином, который, к счастью, вспомнил про число усердного бобра (busy beaver):
Почему Августин решил, что оно больше, чем предложенное оппонентом?Здесь надо сказать, что каким бы большим не было число с кучей факториалов, оно является значением вычислимой функции, т.е. результатом некоего алгоритма, реализуемого с помощью машины Тьюринга.
Определение конкретного значения числа усердного бобра, например, записанного на доске BB(10^100), является алгоритмически неразрешимой задачей. Об этой функции можно говорить лишь оценочно, сравнивая её рост с другими претендентами.
В течение следующих нескольких раундов дуэль превратилась в поиск все более и более "мощных" обобщений понятия Машины Тьюринга. Казалось бы, битва никогда не закончится. Что можно придумать еще?
Тогда Августин Райо в очередном раунде записал на доске такое, что Адаму не оставалось ничего, крое как признать поражение:
Самое маленькое число, большее, чем любое конечное число, которое может быть определено выражением на языке первого порядка теории множеств с использованием менее, чем гугола (10^100) символов».
Итак, давайте разберемся, что имелось ввиду. Прежде всего, что за "язык первого порядка теории множеств". На самом деле - это формула, которая может быть записана с помощью следующих символов:
Итак, число Rayo(n) - это число символов теории множеств первого порядка, которое требуется для записи функции φ(x₁, x₂, x₃, ...), возвращающей в случае подстановки в неё n вместо x₁, значение "Истина". Например, таким образом записывается число 0:
"Неверно, что существует такое x₂, что x₂ является частью x₁". Это выражение возвращает "истину", только если x₁ является пустым множеством. Ведь ни одно множество не является элементом пустого множества. Единица уже записывается более сложно:
Используя такой алгоритм можно строить всё большие и большие числа. Кажется, что такой способ записи очень избыточен, однако функция Райо растет просто невообразимыми темпами:
Здесь уже используется стрелочная нотация Кнута, потому что даже нижнюю границу чисел Райо трудно вообразить для n = 10000. Что уж говорить, про Rayo(10^100) ! Конечно, потом появился аналог - числа BIG FOOT, которые уже использует немного другую сигнатуру (набор символов для записи), но сам принцип, придуманный Августином так и остается непоколебимым. Спасибо за внимание!