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

Наука ОFFNews Последна промяна на 21 май 2015 в 12:37 48392 4

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 1023 е броят на звездите в космоса;
  • 1085 е броят на атомите във Вселената;
  • 10101000000 са броят на възможните вселени в мултивселената, според теорията на хаотичната инфлация;
  • 101033013730 е "броят на вариантите, по които можем да подредим книгите на Борхес" - не спира да се шегува Едуардо.

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

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

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

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

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

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

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

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

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

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

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

n ↥↥ m = nn ......n m пъти.

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

1+1
2 . 2
33
4 ↥↥ 4
5 ↥↥↥ 5
...

За улеснение да означим степенуването (33) с триъгълник, а 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) > 1036534???

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

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

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

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

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

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

много".

 

 

Най-важното
Всички новини
За писането на коментар е необходима регистрация.
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!

3005

4

Todor Todorov

11.09 2020 в 11:18

&/&=1. (&^&)/&=0. >> &^&=0.

17.12 2015 в 12:23

Числото на Греъм G (известна висока степенна кула) е много, ама много по-голямо от посоченото в статията число A(5). С помощта на нотацията на Конуей (създателя на играта "Живот") с хоризонтални стрелки се образува следната нарастваща редица: A(5), 3→3→4→2, 10→10→10→2, 3→3→64→2, G, 3→3→65→2, 10→10→10→3, 10→10→10→4..., n→n→n→1..., n→n→...→n→n... Това е безкрайно множество, но и то може да се сравнява по размер. Знаем, че множеството на целите числа е изброимо и е с кардиналност по-малка от множеството на реалните числа, комплексните числа, кватернионите или октанионите, които са неизборимо безкрайни множества. Оттук идва и идеята за трансфинитните числа, по-големи от всяко крайно число, неизчислима функция (като BB(n) или S(n)), даже и от безкрайност.

07.09 2015 в 13:12

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

07.09 2015 в 07:31

Off News, имате бъг и не ви се вижда текстът.

Инак, доколкото числата са безкраен брой, цифрата за най-голямото възможно число ще е просто знакът за безкрайност. Ако искаме да е по-сложно, можем дори да напишем, че 1∞ = 2∞ = 9∞ = 10∞ = ∞∞, при това вторите символи за безкрайност можем да ги схващаме и като умножаеми, и като степенувани, защото безкрайността си е все една и съща :) Впрочем, това показва безпомощнстта на аритметиката пред по същество философски термини.