Знаете ли как да напишете с минимум знаци най-голямото възможно цяло число? За този математичен трик и за пределите на компютърните изчисления разказа с много хумор испанецът Едуардо Саенз де Кабазон на изминалия Софийски фестивал на науката.
Едуардо де Кабазон е доктор по математика в университета ла Рьоха и е на нашия фестивал благодарение на Института Сервантес.
Едуардо притежава великолепно чувство за хумор и харизма, които вероятно са му помогнали да стане победител на конкурса 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 пъти, а
nm = 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
11.09 2020 в 11:18
17.12 2015 в 12:23
07.09 2015 в 13:12
07.09 2015 в 07:31
Инак, доколкото числата са безкраен брой, цифрата за най-голямото възможно число ще е просто знакът за безкрайност. Ако искаме да е по-сложно, можем дори да напишем, че 1∞ = 2∞ = 9∞ = 10∞ = ∞∞, при това вторите символи за безкрайност можем да ги схващаме и като умножаеми, и като степенувани, защото безкрайността си е все една и съща :) Впрочем, това показва безпомощнстта на аритметиката пред по същество философски термини.
Последни коментари