Про дійсно ВЕЛИКИХ числах (частина 1)

imageІдея написати популярно про великі числа прийшла під час читання цієї статті. Мова в ній йшла про числа-гіганти, які мають хоч якийсь фізичний сенс. І закінчується вона згадкою числа Грема. Того числа, яке буде точкою відліку сьогоднішньої статті. Щоб уявити собі масштаби лиха я настійно рекомендую попередньо прочитати ось цю статтю, яке пояснюється числі про Грема на пальцяхTM — там автор дуже яскраво і послідовно розповідає про межі сприйняття, в які ми себе затискаємо, коли говоримо про великих числах.Увагу, дисклеймер!Я не є професійним математиком. Тому помилки у спеціальній термінології практично неминучі, враховуючи повну відсутність матеріалів російською мовою. Більше того, я навіть не впевнений, що ті слова, які я використовую для перекладу з англійської, взагалі використовуються російськомовними математиками. З іншого боку, я спробував все це зрозуміти і пояснити мовою, доступною для звичайних читачів. Будь-які зауваження прохання відписувати в лічку — будемо покращувати текст разом. Для початку, щоб запобігти можливі коментарі в стилі «а нафіга воно треба, адже це все одно не має зовсім ніякого практичного сенсу» — відповідь знаменитої картинці:image загалом, як сказав IngvarrT в обговоренні статті про числа-гіганти, весь подальший текст зводиться до фрази «Прикиньте, шо придумали математики».

Для початку необхідно прояснити, що коли ми говоримо про великих числах (навіть не ВЕЛИКИХ, а просто великих), то зазвичай маємо на увазі не послідовність цифр, що утворюють це число, а спосіб (або метод), за допомогою якого дане число виходить. Звичайно, ми можемо написати секстиллион як 1000000000000000000000, але все ж звичніше бачити 1021. В даному випадку способом опису числа буде операція зведення в ступінь (яка виглядає як запис числа верхнім індексом праворуч). Використання подібних способів дозволяє скоротити запис числа, залишаючи лише спосіб його утворення (чого, зрозуміло, цілком достатньо для здійснення математичних дій над ним). Так ми логічно підійшли до того, що всі розмови у ВЕЛИКИХ числах зводяться до пошуку максимально компактного запису максимально великого числа. Отже, «шо ж придумали ці математики».

Всі ми знаємо три основні арифметичні операції: додавання (a+b), множення (a × b), зведення в ступінь (ab). Ніколи не замислювалися, що всі ці операції послідовно випливають одна з іншої? А якщо так:

image

image

image

Узагальнено ці операції називаються гипероператорами. Для додавання, множення і зведення в ступінь — 1-го, 2-го і 3-го порядку відповідно. Продовження цього ряду на більш високі порядки напрошується саме собою: гипероператором 4 порядку (тетрацией) називають послідовне зведення в ступінь:

image

А ось для гипероператоров більш високих порядків використовувати таку систему позначень вже не вийде — надто громіздкими і заплутаними будуть статечні вежі. Тому для позначення великих чисел використовуються інші системи нотацій.

Однією з найбільш поширених є стрілкова нотація Дональда Кнута, запропонована в 1976 році. Принцип запису чисел випливає з послідовності гипероператоров і за великим рахунком являє собою явне вказівку порядку гипероператора. Звичайне зведення в ступінь (гипероператор 3 порядку) позначається однією стрілкою: a↑b, тетрация — двома стрілками a↑↑b і так далі. Ось як обчислюється тетрация:
image


Змінивши всього одну цифру ми отримуємо гігантський зростання значення числа:

— в цьому числі більш, ніж 10153 цифр.

Додавши ще одну стрілку ми отримуємо гипероператор 4 порядку — пентацию:




Зміна однієї цифри тут призводить до настільки великого зростання значення, що епітети можна і не підбирати:
— висота степеневої вежі становить 7,625,597,484,987 елементів…
(це число назвается тритри, і воно нам ще придасться)
Щоб не малювати багато стрілок, використовується скорочений запис: a↑nb для позначення a↑↑...↑b n стрілець.

Тут потрібно бути вкрай обережним в оцінках швидкості зростання функції по мірі збільшення порядку гипероператора (ви явно помилилися в меншу сторону) — якщо три не пентировать, а гексировать в три (ну просто збільшити n на одиницю), то ми маємо 3 два рази пентировать по три, тобто 3 пентировать в три 7,625,597,484,987 раз… (але не розслабляйтеся, все це тільки початок, початок).
До речі, ви вже здогадались, яке саме слабке місце стрілочної нотації Батога? Так, саме n — кількість стрілок. А що, якщо воно настільки велике, що звичайне число вже не в змозі його передати? Короткий відступ: якщо три, пентированное в два, піддається хоч якогось розуміння, то вже три, пентированное в три, ні уявити, ні усвідомити неможливо. Навіть не заїкаючись про таких порядках гипероператоров. Це область чистої чистої абстрактної математики і, чорт візьми, it's fucking awesome!

Рішенням проблеми нотації Батога є ланцюжка Конвея. Вони використовуються тоді, коли для запису числа навіть стрілкова нотація Батога стає занадто громіздкою. Пам'ятайте про число Грема, яке згадувалося в самому початку? Позначити його стрілками Батога просто неможливо. Визначення ланцюжка та її взаємозв'язок зі стрілочками Батога:



Начебто все одне і те ж. Але проблема «кількості стрілок» у ланцюжках Конвея вирішується легко і витончено: додаванням ще однієї стрілки. А кожна стрілка звертає всю попередню ланцюжок на себе. Спробуємо розібратися на прикладі: візьмемо тетрацию 3 → 3 → 2 (що це таке: беремо перші два числа і проробляємо операцію зведення в ступінь три рази), додамо праворуч → 2.
3 → 3 → 2 → 2 = 3 → 3 → ( 3 → 3 → 1 → 2) → 1 = 3 → 3 → (3 → 3) = 3 → 3 → 27
Додавши всього одну стрілочку ми відразу перейшли до гипероператору 27 порядку. І число Грема, ніяк не надається стрілочної нотації Батога, ланцюжками Конвея записується дуже лаконічно: 3 → 3 → 64 → 2. А адже можна продовжувати додавати стрілочки і переходити до все більш неймовірним порядків чисел.

Ха! Але хіба це правильно, малювати стільки стрілок? Та й надто вже ме-е-повільно ростуть числа… загалом, Джонатан Бауерс ввів масивну позначення (array notation), яка у своїй максимально розширеній формі називається BEAF (Bowers Exploding Array Function, вибухова масивна функція Бауэрса, гра слів з англійським beaf — яловичина. Треба зазначити, що Бауерс навіть у своїх наукових працях відрізняється особливим почуттям гумору). Запис її дуже проста і нагадує вже розглянуті нотації: 3↑↑↑3 = 3 → 3 → 3 = {3,3,3}. Використовується також інша система масивної нотації, коли останній елемент, що позначає порядок гипероператора, переноситься в середину запису, тобто {3,3,2} = 3 {2} 3 (логіка така — беремо дві цифри по краях і робимо з ними те, що зазначено в середині).
На даному етапі ніяких відмінностей масивної нотації від ланцюжків Конвея немає. Але додавання четвертого елемента масиву має принципово інший зміст, а саме — кількість скобочек: {3,3,3} = {3,3,3,1}, {3,3,3,2} = {{3,3,3}}.
{a,b,1,2} = a {{1}} b = a { a { a....a { a { a } a } a… a } a } a, де b — кількість a, що розходяться від центру.

Для наочності подивимось, що відбувається при зміні елемента всередині центральних скобочек «всього на одиницю»:
{3,3,1,2} = 3 {{1}} 3 = 3 {3 {3} 3} 3 = {3, 3, {3, 3, 3}} = {3, 3, тритри}
{3,3,2,2} = 3 {{2}} 3 = 3 {{1}} 3 {{1}} 3 = {3, {3, 3, тритри}, 1, 2} = 3 {3 {3… 3 {3 {3} 3} 3… 3} 3} 3, де кіль трійок, що розходяться від центру до країв, одно {3,3, тритри}.

У порівняння з ланцюжками Конвея вибухове зростання числа відбувається на етап раніше — якщо у Конвея лише четверте число звертає всі попередні операції на себе, то у Бауэрса — вже третє. Яскравий приклад з розглянутими вище числами:
у Конвея третя одиниця «з'їдає» залишок ланцюжка 3 → 3 → 1 → 2 = 3 → 3 = 27, у Бауэрса вона «працює» на подальше його зростання: {3,3,1,2} = {3,3, тритри}.

До речі, це був всього лише масив з 4 елементів. Додамо божевілля? Просто збільшувати кількість елементів масиву через кому, слідуючи вже сформульованих правил роботи з ними — це нецікаво. Тому Бауерс придумує видозмінені «дужки» для того, щоб хоч мінімально наочно представити» числа масивної нотації. Четверте число в масиві ще залишається з фігурними дужками, а далі починається формене неподобство: п'яте — квадратні дужки, повернені на 90 градусів, шосте — кільця навколо попередньої конструкції, сьоме — зворотні кутові дужки, восьме — як тривимірні квадратні… Коротше, простіше це показати:

(ще на подібні картинки можна подивитися тут)

Ви думаєте, що Бауерс на цьому зупинився? Як би не так. Ну ось що, ЩО ще можна придумати в запису масивів? А можна звернути увагу, що там є коми… нехай позначають елементи одновимірного масиву. А якщо поставити між числами (1), то це перехід на наступний рядок, (2) — перехід на наступну площину.
Квадрат з трійок («дутритри») записується як {3,3,3(1)3,3,3(1)3,3,3}.
Куб з трійок («диментри») — {3,3,3(1)3,3,3(1)3,3,3(2)3,3,3(1)3,3,3(1)3,3,3(2)3,3,3(1)3,3,3(1)3,3,3}.

Ось так невигадливо ми перейшли від площинних масивів до об'ємним (і зауважте, це всього лише запис якогось числа, яка через своїх масштабів зажадала вийти з площини просто в своєму написанні!). Зрозуміло, далі ми вводимо нові позначення для чотиривимірних, пятимерных «об'єктів» (вибачте, називати ці монструозна контрукції числами вже складно). Наприклад, & означає «масив»: {10,100,2} & 10. Тобто {10,100,2}-масив десяток, або ж 10↑↑100-масив десяток. Ну тобто потрібно 100 разів звести десять на десяту ступінь, побудувати грати з такою кількістю клітинок (причому вона буде перебувати в стозмерении, тобто вимірі вимірювань вимірів… вимірів (слово повторено сто разів), а потім заповнити комірки десятками — і тільки тоді можна починати вирішувати цей масив.
Ось як можна намалювати число трилатри {3,3,2}&3:image
Думаєте хоча б на цьому все? Неа. Позначимо «легіон» прямим слешем (/). У масиві {a,b,c,.../2} двійка знаходиться у другому легіоні. Спочатку ми повинні вирішити перший легіон (зліва від косою риси), а потім взяти таку кількість елементів в ланцюжку «масив масив… масив з...», яке вийшло при вирішенні: {3,3 / 2} = 3 & 3 & 3 = {3,3,3} & 3. А от якщо взяти {3,3,3 / 3} = {3 & 3 & 3 / 2}. На цей раз тритри — це не кількість елементів у масиві, а кількість елементів у ланцюжку 3 & 3 &… & 3 & 3.
Ще одне розширення Бауерс зробив додавши символ @ (a@b позначає «легионный масив розміру a з b») і зворотній слеш \ (лgion). Ну тут вже все зрозуміло: {a,b \ 2} = a @ a @ a… a @ a @ a (де а повторюється b разів).

Зрозуміло, що процес придумування нових найменувань для якихось операцій не може бути нескінченним (за легіонами і лугионами йдуть лагионы, лэгионы і лигионы, але очевидно, що це ніщо, враховуючи наш розмах), тому Бауерс зробив простіше — визначив L як прогресію з легіонів, лугионов, лагионов, лэгионов і лигионов: L1, L2, L3… І далі число опередляется індексами.
Наприклад для «обчислення» (смішно, звичайно, говорити про обчисленнях на таких масштабах) {L100,10}10,10 потрібно взяти сотий член прогресії «легіони, лугионы, лагионы...» і скласти з нього масив в 10 вимірах. Потім треба прибирати по одному члену, кожен раз додаючи ланцюжок з«10 % 10 %… %10» (де % — L100-гионный масив на кількість десяток, яке вийшло на попередньому етапі. І тільки після того, як всі соті члени (а також L99, L98 і іже з ними, аж до \ і /) закінчаться, ми зможемо, власне, почати вирішувати перший масив в божевільній прогресії масивів.

До речі, для 340 великих чисел Бауерс ввів власні найменування, багато з яких за своєю безумности повністю відповідають алгоритмів розрахунку. Зустрічайте, МЕАМЕАМЕАЛОККАПУВА УМПА: {{L100,10}10,10 & L,10}10,10.

Примітка для нердов:
Зрозуміло, Бауерс визначив строгий набір правил здійснення операцій над масивами.
Визначення:
— перший запис у масиві називається «базою» (base) — b;
— другий запис у масиві називається «початкової» (prime) — p;
— перша неединичная запис після початкової називається «пілотом» («pilot»);
— запис масиву, яка слідує відразу за пілотом називається «другим пілотом». Вона не існує, якщо пілот є першим записом в своєму ряду;
— структура — це частина масиву, яка складається з груп меншої розмірності. Це може бути запис (Х0), ряд (Х1), площину (Х2), область (Х3) тощо, не кажучи вже про структурах більшої розмірності (Х5 Х6 і т. д.) і тетрационных структурах, наприклад, X↑↑3. Можна також продовжити пентационными, гексационными і т. п. структурами.
— «попередній запис» (previous entry) називається запис, яка утворюється перед пілотом, але в тому ж ряду, що й інші попередні записи. «Попереднім рядом називається ряд, який з'являється перед пілотним поруч, але в тій же площині, що і всі інші попередні ряди і т. д.
— «початковий блок» (prime block) структури S обчислюється заміною всіх входжень Х на p. Наприклад, якщо S = Х3, то початковим блоком буде p3 або куб зі стороною довжини p. Початковим блоком Хх-структури буде pp, p-гіперкуб з довжиною сторони p.
— «літак» включає в себе пілота, всі попередні записи, а також початковий блок всіх попередніх структур;
— «пасажири» — це запису в літаку, які не є пілотом або другим пілотом;
— значення масиву записується як v(A), де А — це масив.
Правила обчислення:
1. Якщо p = 1, v(A) = b
2. Якщо немає пілота, то v(A) = bp
3. Якщо перше і друге не застосовується, то:
— пілот зменшується на 1;
— другий пілот приймає значення оригінального масиву з початковим значенням, зменшеним на 1;
— кожен пасажир стає b;
— інша частина масиву не змінюється
Всі приклади, описані вище, підкоряються цим простим правилам.


Як вже говорилося вище, BEAF за своєю могутністю значно перевершує ланцюжка Конвея, не кажучи вже про нотації Батога… Цікаво, що далі?

А далі ми вступаємо на полі швидше філософії, ніж власне математики. Всі описані вище нотації являють собою вычислимые функції або функції, які можуть бути реалізовані на машині Тьюринга.

У другій частині ми розглянемо необчислювані функції: завдання старанних бобрів, сигма-функцію Радо Σ(n), кількість Райо, BIG FOOT та інші, а також розглянемо швидкорослу ієрархію, щоб зрозуміти, чи є межа цього математичного божевілля.

Використані матеріали:
1. Головний сайт на гугологии: http://googology.wikia.com/wiki/Googology_Wiki
2. Бесконечноскребы Джонатана Бауэрса
3. Exploding Array Function


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.