The Insane Ackermann Function

Researchers proved that navigating certain systems of vectors is among the most complex computational problems and involves a function called the Ackermann function. Find out how an easy-sounding problem yields numbers too big for our universe.
Watch our full video explainer: • The Easy-Sounding Prob...
Read the article: www.quantamaga...
--------
VISIT our website: www.quantamaga...
LIKE us on Facebook: / quantanews
FOLLOW us Twitter: / quantamagazine
@QuantaScienceChannel
#math #computerscience

[@tjrh123]

New favourite word unlocked: quinquagintillion

[@onurakcay061]

they done achieved quagmiremillion

[@atomgutan8064]

Googology words are fun

[@JeadyVT]

i know that one from cookies clicker

[@kneau]

Me in fourth grade, after coming across 'antidisestablishmentarianism' The risk assessment always running within my mind has prompted me to return and add apostrophes.

[@cosmosapien597]

Quinquagintillionaire

[@OutsiderLabs]

Ackerman has only one function: to pwn titans

[@phazerxp339]

I'm glad people are still using pwned in 2024.

[@OutsiderLabs]

@@phazerxp339 I am a product of my time

[@Eiravxe]

jj

[@LinkRammer]

Knew it'd be commented

[@gamespotlive3673]

lol

[@not_mukul]

zeke won't enjoy studying this function

[@ssoark]

💀

[@setabkhan3081]

I searched for someone mentioning AOT

[@JustDeerLol]

Hello fellow AOT fan

[@Letsdraw534]

hi brother

[@mriz]

Collosal Number also mentioned 😂

[@solarsystem1958]

pov: you've been inventing your sorting algorithms and ended up with complexity of A(n) ☠️

[@FreeFireFull]

Fun fact: There are some algorithms whose time complexity is the inverse of the ackermann function.

[@gabrielmello3293]

@@FreeFireFull so pretty much constant

[@theairaccumulator7144]

​@@FreeFireFullsuch as?

[@FreeFireFull]

@@theairaccumulator7144 Searching through a disjoin-set forest

[@battesonb]

​@@theairaccumulator7144 the union and find operations for a weighted union find with path compression.

[@nunkatsu]

"Ackermann function" "Colossal number" Aot mentioned

[@KasparOne]

in the 50's scientists once attempted to calculate A[5], but the piece of paper on which the calculations were performed quickly turned into a black hole

[@shriiimp]

Since they disappeared, they couldn't tell us what they saw.

[@suhnih4076]

Lol

[@mdahsanraza]

Is this by Levi or mikasa?!

[@Thenormalguy101]

TATAKAE

[@phantomphoenix8828]

Naaah, it's Kenny

[@noobtommy4739]

@@phantomphoenix8828 more like "Keeenneeaayyyy!"

[@keshavvelayudhannair]

And after tetration (for 4) You get pentation (for 5) Pentation is just a tower of tetration Tetration of tetration Tetration 5 times is pentation of five It is represented by a 5 with a small five on its left side bottom (5 with ⁵ at bottom left)

[@Yjvt]

So as n>3 it just n{n-2}n

[@concerninghobbits5536]

Do you happen to know how high it goes before we don't have standard ways of notating it? Or is there a repeatable pattern at some point? I would've guessed pentation would be just more exponents stacked up, so you'd quickly end up with an absurd amount of exponents towered up but nobody has any need to ever write that.

[@keshavvelayudhannair]

@@concerninghobbits5536 yeah It is surely very large It might have more than a million digits

[@Yjvt]

So A(n) as n>3 its just n{n-2}2 Before you ask what's that this is BEAF notation so a{n}b is equal to a↑ⁿb (n is just n Arrow for shorthand) (a is number we gonna repeat) (b is how much we gonna repeat)

[@joaquinginestet4813]

what you get? 😧 pen*t*ation?

[@jean-joseftolosa8404]

You've def earned it for summoning a titanic fandom.

[@Pining_for_the_fjords]

In other words, the Ackerman function would be useful for describing the weight of your mum.

[@victorfunnyman]

my guy

[@MrBrilliant-pro]

Gotta change your phone's password, or your dead body won't be found even after n(4) years 😅😅😅

[@JUSTREGULARSCREAMINGAAHH]

​@@MrBrilliant-produde

[@gw6667]

Your brit is hanging out

[@EnerJetix]

The weight of CaseOh

[@1ntegerLimit]

And SQUARE it is mad

[@skeletoncrew3110]

AND THAT'S JUST AT 4!!!!!!!!!!

[@JordanMetroidManiac]

For those that don’t know how to visualize “squaring” it, it is equivalent to think of each atom of the universe containing an equally sized universe within itself. So imagine there are multiple universes of equal size, and the number of universes is equal to the number of atoms in one of them. The total number of atoms across all universes is the square of the number of atoms in our (observable) universe. It is not really a number that can be comprehended by us.

[@Joshua-uwafili]

fr😭

[@milanstevic8424]

@@JordanMetroidManiac so sad, I was just about to comprehend 1 universe

[@matthiasbendewald1803]

Yes and it is just the "number of zeros". You know, like a million has 6. This number is a bit out of comprehension or calculation or anything, just crazy...

[@Domo3000]

You got this completely wrong. This has nothing to do with the Ackerman function, except that both grow fast. The Ackerman function is a recursive function with 3 arguments. And it grows even faster and takes much longer to compute.

[@maxaafbackname5562]

That is was I learned. A very fast function rhat can only implement recursive, not interactive. A pure recursive function. There is a Computerphule video about it for example.

[@nosterkristoffbaron8819]

I immediately searched this up on Google. You were right, @Domo3000.

[@AnyVideo999]

Thank you for saying this, I thought I was going insane watching this haha

[@adamnevraumont4027]

There is an ackerman 1 argument function, 2 arguments and 3. They are all closely related.

[@jeffwells641]

I see you all looked this up on Wikipedia, and then boldly and confidently completely misunderstood what Wikipedia said. Well done, you've made yourselves look like idiots. A(m, n, p) is the original form of the function, as Ackermann described it. A(n) as described in the video is an alternate representation of the EXACT SAME FUNCTION. The Ackermann function doesn't grow faster than the Ackermann function, because it obviously IS the Ackermann function. There are ways of configuring it with A(m, n, p) that grow faster than the one typically used for A(n), however. Dunning-Kruger strikes again!

[@luckycandy4823]

It's actually very simple and beautiful idea, suppose you give me a list of functions f_n(x) with x natural, each growing faster than the one before. Now I could apply the diagonal n -> f_n(n) Which grows faster than each f_n. To get Ackermann you just choose some functions f_n, there are variations, the one I learnt was f_1(x)=2x and we get f_(n+1)(x) by iterating f_n(f_n(...f_n(1))...) x times, so that f_2(x)=2^x, f_3(x)=2^2^...^2 x times etc. Hope you have a wonderful day😊

[@nickronca1562]

A. Look up fast growing hierarchy. B. f_2(x) = (2^x)*x not just 2^x

[@Yjvt]

oh you mean fast growing hierarchy where fω(n) = fn(n) where f_1(n) is fⁿ0(n) which is 2n {the n is superscript} f_2(n) is fⁿ1(n) which is 2ⁿ×n so fα(n) is fⁿα-1(n)

[@ReginaldCarey]

What is A[pi]? What would the analytic continuation look like?

[@neodimium]

Interesting question

[@Lumegrin]

first youd have to do something like A[3.5] youre looking at fractional hyperoperations, which is something fascinating but im not sure theres any documentation on

[@nickronca1562]

​@@LumegrinA[3.5] would be two 3.5's with 1.5 up arrows in between but so far I haven't heard of anyways to have a fractional number of up arrows.

[@Lumegrin]

@@nickronca1562 hyper-3.5 yes

[@ReginaldCarey]

@@Lumegrin Fractional Hyperoperations has to be the coolest phase I’ve heard in a long time. I agree I thinking that working on the solution to a rational might give insight into the solution between A(3) and A(4). It feels like this multi-function (if that’s the right term) is highly ill behaved. Is there a Taylor series expansion for tetration?

[@Misteribel]

Its main use was to demonstrate a total computable function that is not primitively recursive. The original has three arguments. You essentially showed A(n, n, n) here, where all arguments are equal.

[@arpangupta69420]

KENNYYYY!

[@mincat1412]

oh, you haven’t grown at all!

[@arpangupta69420]

@@mincat1412 AoT reference: ✅

[@PhilipSportel]

I drove past Qinquagintillion on my way to Muskoka

[@carultch]

Ackermann Function with Graham's number as both of the parameters.

[@gooodels]

at the scale of grahams number, this is really not that much bigger

[@adamnevraumont4027]

G_64 is A^64(4) - to make Graham's number be small, you want to use better tools, not boring "function applications". Like use ordinals to define recursion and grab a large ordinal and have it define recursion of n:->n+1… Or pull out busy beaver, or other powerful tools.

[@nzqarc]

That's smaller than G(65) lmao

[@Yjvt]

Ack function < Graham Number why? So we gonna use BEAF notation a{n}b a is what number gonna repeat,n is n Arrow for shorthand,b is how much repeat to a uhh let's start with graham first G_0 = 4 G_1 = 3{4}3 or 3↑↑↑↑3(hexation) ≈ A(5) G_2 = 3{3{4}3}3 you should do inside first then outside G_3 = 3{3{3{4}3}3}3 G_n = 3{...{4}...}3 with n times

[@onionman8160]

If you want to dwarf Graham's number, it's more fun to use faster growing function, like the TREE function or busy beaver game. Both of those would quickly surpass anything you put into the Ackermann or g function.

[@tahmeedmansib4767]

Ah yes, the Ackermann function, the mathematical attempt to scale Levi's power level.

[@The_Engineerr]

''This escalated quickly''

[@jotarokujo9759]

Didn't know Mikasa was this good at math

[@leslieviljoen]

I'm glad we know how many atoms there are in the universe, I would have thought that would be impossible to know.

[@adamnevraumont4027]

"Observable universe" and an upper bound. The point is this grows so fast that it blows past such upper bounds, squared.

[@adamsmith7885]

so you believe in an unobservable universe? without observable evidence for it?

[@adamnevraumont4027]

@@adamsmith7885 I mean, suppose you have a flashlight. And you know the flashlight has a 1 meter range. And in every direction you see stuff, with no special edge at 1 meter. Would it be reasonable to assume "what I can observe is an artifact of my measuring device, and not the limit of reality"? We can observe some chunk of the universe. Assuming "it probably doesn't stop right at the edge of what we can see" seems reasonable.

[@adamsmith7885]

@@adamnevraumont4027 you aren't familiar with what "Observable Universe" means. It doesn't mean "observed-so-far universe".

[@adamnevraumont4027]

@@adamsmith7885 I am glad you are telepathic. Keep up the good work. This is not sarcasm. No really, no sarcasm at all. It is pure praise at your amazing abilities. Be content at how impressed everyone is.

[@theflamingmustafa7852]

levi going crazy w this one

[@space_twitch1926]

How would A(0) be? I can't think of any operations below addition, and A(0) = 0 seems like an incomplete answer...?

[@Freddie_Office]

it would be 1 since the first hyperoperation is the successor function which is just adding 1 to a number

[@Internet_guy69]

Bro pronounced it so well that I officially am going to use that word to express large quantities. Like I could write a quinquagintilion words

[@TheRealGregariousGreg]

Going from 27 to roughly 1 quinguagintillion in one go is kinda crazy

[@joaosa3689]

Good. Now extend it to the rationals

[@theguywhodoes6790]

I can't wait to see 3b1b make an analytic continuation video about the Ackerman function.

[@Jalalx]

Well, that escalated quickly

[@JrSti.]

it really did

[@fosascomunes]

Actually, A(4) is 4^1.34e+154, the number can't even be written, there's not enough of anmything to write it

[@sgbench]

I guess you mean that all of its *digits* can't be written. The number itself can be written very easily: A(4).

[@Photos-s7k]

You misspelled anything

[@symmetrie_bruch]

it´s used to slay titans and protect eren

[@MegaArti2000]

I had never seen Ackerman's function actual meaning besides being purely recursive. This content is good stuff!!

[@ceramic5153]

Its threatening to watch that two pop up on the final image with no volume

[@tulpamedia]

It's really dope hearing someone talk about tetration! In my opinion, it's a very under-discussed operation!

[@RSLT]

GREAT VIDEO 📹 👍 👏 👌

[@PC_Simo]

The Ackerman function really reminds me of f_ω(n) = f_n(n) ≈ 2↑(n-1)n, which is presented, in the ”Numberphile”-video: ”TREE vs. Graham’s Number - Numberphile”: f_ω(0) = f_0(0) = 0+1 = 1; f_ω(1) = f_1(1) = 2*1 = 2; f_ω(2) = f_2(2) = 2²*2 = 8; f_ω(3) = f_3(3) = 121-Million-Digit-Number; f_ω(4) = f_4(4) = [10↑³4; 10↑³5]; and so on…. The legendary infinite ordinal -indexed function, in the Fast-Growing Hierarchies / FGH (just in case you’re a bit rusty on the meaning of the index: ”ω”). 😅

[@TimJSwan]

The reason why it tests the limits of computation it's not because the numbers are large but because it is a small simple testable example of a non-primitive recursive function

[@Ygerna]

You can also write tetration with only 2 symbols. Instead of putting the "exponent" on the top right of the base, you write it on the top left. Quintation being the next step and you write it either with three arrows as you showed or on the bottom left. Pentation on the bottom right

[@cgillespie78]

Can it take negative or non-integer inputs?

[@m.v.j6804]

I was not expecting this ackerman

[@devnarula2003]

even cooler is the disjoint set union runtime can be optimized to inverse ackermann, which unlike ackermann grows extremely slowly, becoming near O(1)

[@professorboltzmann5709]

What’s the use of this mysterious function? Except being stupidly large ??!

[@vyrsh0]

It shows that all primitive recursive functions are total recursive.. but not all total recursive functions are primitive recursive. The actual Ackerman function takes 3 inputs. I've not seen the proof. The proof I know uses an imaginary language called the bloop language in which all the functions in the language are primitive recursive. The proof involves proving that we can't write the interpreter of the bloop language using bloop and we use a diagonal argument to prove that. it's a really simple and beautiful proof so I encourage you to check it out.

[@zzappligator]

Maybe someone can find a use, maybe not.

[@armandaneshjoo]

It determines a lower limit for computation. Under A(4) you cannot compute. Maybe we build microbots. But we can never build nanobots.

[@sevaluoth]

​@@armandaneshjooI can't understand how is the size of robots related to this function,

[@armandaneshjoo]

@@sevaluoth We need to go crazy small in order to go to space. We need nano-chips on micro rockets. We need microchips on small rockets. But Computation has a lower limit. If your chips are too small or too basic, they cannot do enough. So we can't easily scale down.

[@pet_r_o_c_k]

"One! I can count to one Two! I can count to two There! I can count to three Four! I CAN COUNT NO MORE!"

[@alt_meta3077]

This is not the full ackermann function. The full process is described recursively, as this version relies on knuth arrows, which ackermann does not have credit to. Ackermann's function relies on the "Ackermann's Worm" which is a weaker version of the Beklemishev Worm. You begin with a number, and a "row" number. eg 2 [1] 1. If list empty, return row 2. Else, increment row, 3. If last term = 0, delete it 4. Else, replace the last term with "row" copies of last term - 1 Process for A(2,1) is as follows: 2[1] 1,1[2] 1,0,0,0[3] 1,0,0[4] 1,0[5] 1[6] 0,0,0...[7] [14] A(2,1) = 14

[@muzzletov]

typically in a comp sc curriculum you get to learn about the ackermann function. theres even faster growing functions. investigating these kind of features has been largely motivated by results from georg cantor's work.

[@the98goober]

quinquagintillion is a word I’ve never heard before

[@Controlled_Khaos]

"and square it" oh you ate that

[@Rudxain]

The *true limits* of computation are the Busy-Beaver fns. Ack was just the 1st fn to prove "non-primitive" recursive fns exist and are computable

[@darrennew8211]

I don't think it counts if the function isn't computable in the first place. :-) There are lots of uncomputable functions that show the limits of computation.

[@Rudxain]

@@darrennew8211 I agree

[@INLF]

A new busy beaver value was recently proven BB(5)=47,176,870 The Busy beaver function is the fastest growing function which is still computable and grows even faster than this.

[@darrennew8211]

The busy beaver function isn't computable. If it were, you could solve all kinds of problems like the halting problem, simply by knowing that the longest computation a program that big will take is BB(...)

[@turolretar]

What is Quagmire doing here?

[@bm9917]

How do you know how many atoms are in universe, Did you count it?

[@malavoy1]

Actually the 4 is being raised to 4^256 which is the quinquagintillion. So it's even worse than they stated.

[@azaria_phd]

I mean, the limits of computation as in "if you try to calculate a number with more digits than there are atoms in the observable universe you can't".

[@TheGamingG810]

In beaf terms, A(n)={n,n,n-2}

[@Yjvt]

Was it like n{n-2}n ?

[@savitasharma5325]

“Ah, no one can visualise this thing” Meanwhile this guy:

[@duncreg]

This is why mathematicians ought to be licensed.

[@ArkSriva]

A[5] ?

[@neodimium]

Tetration in exponent?

[@xinterest9029]

That would look like 5 raised to itself in a tower of exponents with height equal to the quantity of 5 raised to itself four times, minus 1. I HOPE I got that correct. Someone else can figure out the magnitude if they want lol

[@EdKolis]

Your puter a splode, that's how much it is

[@jeffwells641]

@@EdKolis My puter sploded at universe^2.

[@Yjvt]

5↑↑↑5 or 5{3}5

[@raymitchell9736]

So a[5] ... and so on ?? It's a virtual cliffhanger! That's computationally complex!!!

[@yeetyeet7070]

Benannt nach einem gewissen Sparkassenvorstand und beschreibt die Geschwindigkeit mit der Gelder in schwarze Kassen verschwinden?

[@dpie4859]

But Tree(3) grows MUCH faster. Its insane.

[@shiinondogewalker2809]

@@dpie4859 technically Tree(3) doesn't grow at all, it's a constant number. But the Tree function does, yeah

[@tomkerruish2982]

For something really fast-growing, check out Goodstein sequences.

[@xmurrcattx3498]

and if you repeat the tower of powers, you get funky 16ths

[@alexcastrotello5165]

Thats a crazy sequence

[@radicant7283]

Why stop at 4?

[@Ympatisec2K24]

A(100)=A100(1,2)2 or 100{98}100 /100^...^10 x98 / {100, 100, 98}.

[@Photos-s7k]

Because When A(5) hits, We have Pentation

[@yodxxx1]

Me typing 10 into a computer and causing a instant black hole

[@Azman-bt8yw]

do ackermann numbers pls

[@mohammadrafhaan4092]

What will be A[5] ?

[@martbhdsuai]

Great video. I remember implementing karatsuba and dft integer multiplication for a final project in my advanced algorithms class. I have to say I felt quite smug after your karatsuba performance was equally as shit as mine 😂

[@NSGrendel]

As soon as I heard, "Tower of Powers" I immediately though of Frank Zappa and "Bobby Brown".

[@ThatobjectArtist]

note: this is the single-argument ackermann function the actual function is 3-arguments long

[@vari6989]

finally someone from googology server

[@СергейПастухов-э2м]

So what is A(inf) or A(-inf) or even A(0.5) would be?

[@JustDeerLol]

What about smth like A[3.5]? Seems unreasonable to have the 3.5th hyperoperation and do it 3.5 times

[@csdrew22]

This would break the function. First it's important to note that the most commonly used version of the Ackerman function is actually a binary function. It's implemented in such a way that if either of the inputs to the function are greater than zero, it subtracts one from them and they get fed back into the function recursively until they equal zero, at which point the function returns. Since you can't obtain 0 by iteratively subtracting 1 away from a non-integer number (such as 3.5), the function is only defined for the natural numbers.

[@JustDeerLol]

@@csdrew22 i just wondered if it can be generalized, just like how factorial can be applied to all real numbers when its just a recursive function and was only defined for natural numbers

[@Photos-s7k]

It’s Impossible to do it with decimals So Yeah. My answer is idk

[@Photos-s7k]

Or if i guess… It’s 3.5{1.5}3.5

[@MisterIncog]

Me and the boys about to pull up to the ackerman function

[@everyhandletaken]

I think you calculated my brain cells in the first equation 🥹

[@AdvaitBhalerao]

What about A[G(64)] i.e, Graham's Number??

[@Photos-s7k]

A(G64)?

[@Photos-s7k]

That’s G64{G64-2}G64

[@AdvaitBhalerao]

G64 followed by G64 arrows...

[@wyboo2019]

i wonder how quickly the equivalent for the commutative hyper-operations is. suppose you have some binary operation + and you want to create a hyperoperation •, then we define the commutative hyperoperations as: ln(a•b)=ln(a)+ln(b) clearly this turns addition into multiplication, but it also turns multiplication into a new operation, which is like a commutative version of exponentiation. this new operation is a^ln(b)=b^ln(a)=exp(ln(a)ln(b)) then just do the ackermann function thing with this. not sure if itd work well because the domains of the commutative hyperoperations are weird

[@larrywhitney]

We can finally measure how heavy caseoh is

[@Letsdraw534]

levi ackermann

[@D_Cragoon]

"That escalated quickly." meme.

[@prashil3k594]

Ackerman function leads to a colossal number....Hmmmmmmmm. KENNYYY!

[@BombaSoup]

Busy Beaver would like to have a word with mister Ackerman

[@_noturn0_474]

Everyone gangsta till the ackerman function of 1/2

[@whophd]

Of course the HACKERMAN function is to feed the result of A(x) into itself, but do it A(x) times, to get H(x).

[@YKRotter]

Bro summoned the entire aot fandom 😂

[@kaiserdaniman]

All the atoms in the "visible" universe. The difference is extremely big, as the research on this topic suggest that the universe is -if not totally- almost flat (infinite).

[@包子-w2j]

A(1)=1+1 A(2)=2*2 A(3)=3^3 A(4)=4^^4 A(5)=5^^^5 A(10)=10{8}10 A(100)=100{98}100

[@Photos-s7k]

A(1000)=1000{998}1000 A(1000000)=1000000{999998}1000000

[@包子-w2j]

@@Photos-s7kthanks but you can shorten them if you understand beaf ban

[@Photos-s7k]

{1000000,1000000,999998}

[@Photos-s7k]

{1000,1000,998}

[@包子-w2j]

Uh thanks

[@IamFlaem1]

“Take all the atoms in the universe”: oh damn “Then square it”: OH D A M N

[@ptorq]

"All the atoms in the universe" is a surprisingly small number. It's well under a googol.

[@Photos-s7k]

But All The atoms in the universe squared? That’s 1 Googol x 10^60

[@luckytrinh333]

Modified Ackerman function

[@Theguyfromvoid]

Well well well, if ain't that escalated quickly.

[@Jesse608]

Thank you

[@cmyk8964]

This is called the *weak* Ackermann function, and the actual (strong) Ackermann function grows even faster

[@GabrielGABFonseca]

So the band Tower of Power should actually just be called "Tetration"?

[@Terraspark4941]

when i heard the number of the particles in the universe _squared_ my jaw literally fell off

[@heterodoxagnostic8070]

I came up with this function in like grade 6 or something after learning about exponentiation.

[@john38825]

I can't comprehend what 5 would be. Would it be a cubic matrix thing?

[@kiti_cat524]

Ackermann sequence: 2 4 27 10^10^153

[@Apollorion]

What is A(0) ? Is this Ackermann function continuous?

[@SparerRoom49700]

So A(n) = n{n-2}n?

[@jimmysyar889]

Another way to think about universe squared is an entire universe for ever particle in this universe.

[@GynxShinx]

So 0 next. Then, -1.