Как да напишем най-най-най-голямото число?

Знаете ли как да напишете с минимум знаци най-голямото възможно цяло число? За този математичен трик и за пределите на компютърните изчисления разказа с много хумор испанецът Едуардо Саенз де Кабазон на изминалия Софийски фестивал на науката.

Едуардо де Кабазон е доктор по математика в университета ла Рьоха и е на нашия фестивал благодарение на Института Сервантес.

Едуардо притежава великолепно чувство за хумор и харизма, които вероятно са му помогнали да стане победител на конкурса FameLab в Испания през 2013г. Той е член-основател на "The Big Van theory", пътуваща с ван група млади учени, които с невероятен успех са изнесли повече от 200 презентации в Испания.

И ако учените в сериала „Теория за Големия взрив“ (The Big Bang Theory) предизвикват смях, то Едуардо и съмишлениците му чрез хумор провокират интерес към науката.

Групата "The Big Van theory"

Нагоре по стълбата на степените

"Кое е най-голямото число, което можете да напишете за десет секунди?", - зададе въпросът си Едуардо, а две момчета от публиката излязоха на сцената за да отговорят на предизвикателството.

Рангел написа "9999999999", а Виктор - "гугъл". Виктор печели това състезание, защото гугъл означава 10¹⁰⁰, но това е преди симпатичният испански лектор да ни поведе през дълбоките и сложни концепции на математиката.

"Ако ви е страх от математиката, може да се държите за ръцете със съседа си" - подхвърли шеговито Едуардо. - "А ако много сте се изплашили, може да викате". 

В задачата на тази лекция обаче не влиза безкрайността, занимаваме се само с цели числа - "Безкрайността веднага да излиза от този театър", въпреки че логото на фестивала е ∞.

Има един много стегнат вид за записване на големи числа, изобретен от Архимед - степенуването. Използвайки своята система древногръцкият математик изчислил, че броят на песъчинките, необходими за запълване на цялата Вселена е 10⁶⁴.

"Ако запишем 9⁹⁹ кое ще е по-голямо" - пита Едуардо- " (9⁹)⁹ или 9^{(99 )}?" Ако приемем, че колкото повече цифри има едно число, толкова е по-голямо, то в първия случай получаваме число със 78 цифри, а във втория - с 369 693 100 цифри и вече рекордът на Виктор е разбит.

И така със степенуване, можем да покажем огромни числа:

• 10²³ е броят на звездите в космоса;
• 10⁸⁵ е броят на атомите във Вселената;
• 10^101000000 са броят на възможните вселени в мултивселената, според теорията на хаотичната инфлация;
• 10^1033013730 е "броят на вариантите, по които можем да подредим книгите на Борхес" - не спира да се шегува Едуардо.

Рекурсията или да захапеш опашката си

През 1997 г. големият гросмайстор Гари Гаспаров е играл срещу компютъра Deep Blue и е загубил, но играта не е честна, защото само компютър може да проследи всичките 10¹⁵⁰ комбинации, между впрочем, японската игра "Го" има 10³⁶⁶ комбинации и все още е твърде сложна за компютрите.

Броят на комбинациите се изчисляват с математическото действие "факториел". Например:

5!=5.4.3.2.1 , или 5!=5.4!, или 5!=5.4.3! и т.н.

Тук отново се срещаме с т.н. рекурсия, за която писахме неотдавна. Тя, казано обобщено, е нещо, което се обръща само към себе си и често я асоциират като змия, захапала опашката си.

Всяко изчислимо число е рекурсивно, според немският гимназиален учител Вилем Акерман, който е открил рекурсията и я изразил с формулата: n!=n (n-1)!

Четворка в квадратче - границата на изброимото 

Може постепенно да усложняваме математичните действия:

n.m = n+...+n - m пъти, а 

n^m = n. ... .n - m пъти.

Ако продължим в същия дух, ще стигнем до действие, означаващо многократно степенуване:

n ↥↥ m = n^{n ......n} m пъти.

Получава редицата:

1+1
2 . 2
3³
4 ↥↥ 4
5 ↥↥↥ 5
...

За улеснение да означим степенуването (3³) с триъгълник, а 4 ↥↥ 4 с квадрат - така само с една четворка, оградена в квадратче стигаме до толкова огромно число, по-голямо от броя на атомите във Вселената и което дори за всичкото време на Вселената не бихме могли да запишем. 

Тези числа са рекурсивни и са изчислими. Ако някога имаме достатъчно мощни компютри, те биха се справили с това число.

А ако поставим 4 в петоълник или т.н. функция ​​pentation: 

Никой не познава по-голямо число от това.

Машината на Тюринг

Алан Тюринг е герой на един нашумял наскоро филм, "Игра на кодове" и е един от най-светлите умове на своето време. Освен, че е успял да разбие кода на немската "Енигма", той е доказал, че има задачи в математиката, които никога няма да бъдат решени и че компютрите няма да могат да изчислят всичко, колкото и да се развива тази технология.

Машината на Тюринг е само абстрактен модел. Състои се от бекрайна лента с клетки, с които има нули и единици и глава, която чете клетката, на която е позиционирана и според прочетенето се мести напред или назад и пише в клетките.

Не може обаче да се определи кога машината на Тюринг ще завърши изчислението си.

На базата на този виртуален компютър унгарският математик Тибор Радо изобретява числата на "заетия бобър" (Busy Beaver - ВВ) последователност от числа, които не са изчислими. 

Има ли наистина някакви последователности от числа, които растат толкова абсурдно бързо, че просто не могат да бъдат изчислени? Една неизчислима задача е проблемът за спирането.

Определението на Радо за машината на Тюринг е следното:

• Машината работи на безкрайна и в двете посоки (неограничена) лента.
• За всяка стъпка машината има 2 входни данни:
• позицията на лентата;
• символът, написан на текушата клетка.
• и произвежда три изхода:
  • символ, който да бъде написан върху символа, който е в момента на текущата позиция на лентата;
  • посока на движение (ляво или дясно); 
  • нова позиция, където да отиде или да спре.
    
    

При машината на Тюринг е позволено да видим само един от символите на лентата в даден момент. Така че можем да си представим малък бобър, който тича напред-назад покрай безкрайна река, като поглежда отметките на дърветата и никога не знае какво ще направи после, докато не види знака на дървото, до което е в момента. Машината на Тюринг няма ограничение за времето, за което може да работи, а лентата е безкрайна и може да се пишат безкрайно много символи.

Пускаме машината с празна лента (във всяка клетка е записано 0).

Задачата за работливия бобър се състои в търсене на такава машина на Тюринг, съдържаща автомат с n състояния, която пусната на празна лента, се спира и записва на лентата най-голям брой символи.

В края на краищата, машшината ще спре. Някои машини никога няма да спрат и ги елиминираме.

Резултатът на функцията на заетият бобър BB(n) е броят единици, записани от машината - шампион с n състояния. Самата машина шампион се нарича "работливия бобър" -  BB.

Тибор Радо е доказал, че функцията е неизчислима и расте по-бързо от коя да е изчислима функция.

Стойностите за малки n могат да се намерят и досега са известни за n до 4.

ВВ (1) = 1

ВВ (2) = 6

ВВ (3) = 21

ВВ (4) = 107

ВВ (5) > 2133492

ВВ (6) > 10^36534???

Тези числа са неизчислими, за разлика от числата на Акерман. Кои са по-големи е трудно да се каже - в началото по-бързо расте ВВ, а после числата на Акерман.

Каква е ползата от тези чудовищни числа?

Ако имаме някаква програма първото нещо, което трябва да се прецени порядъка на сложността на алгоритъма й. А сте инженер е важно да знаете колко време ще ви трябва за изчислението, защото е възможно то да клони към безкрайност.

Да се изчисляват големи числа е много трудно. ВВ (5) и ВВ(6) имат крайна стойност, но са неизчислими. Не съществува такава Радо машина, която да изчисли ВВ(7).

Така ако искаме да покажем на една математичка колко я обичаме, бихме могли да й кажем:

"Обичам те ето толкова:

много".

Още по темата

15/05/2015

Човекът

Победителите в лабораторията за слава FameLab

25/01/2015

Математика

Алън Тюринг за леопардовите петна и ивиците на зебрата

12/09/2016

Математика

Игра на кодове: трагичната съдба на един гениален математик

28/01/2015

Математика

Рекурсия