In one of my latest posts I reviewed the Ackermann function. We left with some unsolved problems about efficiency and computability of the function itself. Throughout this post I’ll give another point of view for the Ackermann function, and something magic wil come out …
Another form
The function A(x, y) is defined for every real pair (x, y). If we restrict the domain of x and y to the Integer set, we get a different image for the function. That is:
- A(0, y) = y + 1
- A(1, y) = y + 2
- A(2, y) = 2y + 3
- A(3, y) = 2^(y+3) – 3
- A(4, y) = 2^2^2^ … ^2 – 3
- A(5, y) = ?
As we can see, the form of A(x, y) becomes more and more difficult as x grows. Eg. to compute A(4, y) one has to compute the exponentiation of 2 by 2 for y+3 times. If you look carefully, though, you can see that the Ackermann function underlies an interesting pattern. It will be more clear if we chose a little different form of A(x, y).
Buck’s function
Buck’s function has the same recursive pattern of Ackermann’s function, but with different boundary values. That is:
$$F(x, y) = F(x-1, F(x, y-1))$$
with
$$F(0,y) = y+1 \\ F(1,0) = 2 \\ F(2,0) = 0 \\ F(x, 0) = 1, for x = 3,4,\dots$$
Well, starting from here, we have the following:
$$F(0, y) = y + 1 \\ F(1, y) = 2y \\ F(2, y) = 2^y \\ F(3, y) = 2^{2^{\dots^2}} = 2\uparrow\uparrow y$$
Now the pattern should be clear:
- x = 0 represents the sum
- x = 1 represents the repetition of the sum y times, the multiplication
- x = 2 represents the repetition of the multiplication y times, the exponentiation
- x = 3 represents the repetition of the exponentiation y times, the so called power tower
and so on. To represent in a concise form the latter case the Knoth’s up-arrow notation has been used. We can use this notation to generalize the function this way:
$$F(x, y) = 2\uparrow^{x – 1}y, \ \ \ \ \ \text{for } x \geq 2$$
Easily, we can see the Buck’s function as a succession of operators and hyper operators:
$$(+, \times, \uparrow, \uparrow\uparrow, \uparrow\uparrow\uparrow, \ldots, \uparrow^{n}, \ldots)$$
Back to algorithms
I started this “conversation” speaking about algorithmic implementation. We can now rewrite the Ackermann’s function in a different way, as expressed in the beginning of this article. Sadly, we define the new function only for x < 5:
import sys from math import pow def A2(x, y): if x <= 1: return x + y + 1; if x == 2: return 2 * y + 3 if x == 3: return pow(2, y + 3) if x == 4: res = 2 y += 3 while y > 1: res = pow(2, res) y -= 1 return res - 3 return 0 x = int(sys.argv[1]) y = int(sys.argv[2]) print "Result of A2(%d, %d) is %d" % (x, y, A2(x, y))
Now, the algorithm will give results till A(4, 1). As we said, A(4, 2) has about 19,000 decimal digits, since it’s equal to $$2^{65536}-3$$.
I will also give you an implementation of the Buck’s function, using a generalized implementation of the hyper operator function:
import sys from math import pow def F(x, y): if x == 0: return y + 1 if x == 1: return 2 * y if x == 2: return pow(2, y) return hyper(2, x, y) def hyper(a, n, b): if n == 1: return pow(a, b) if b == 0: return 1 return hyper(a, b - 1, hyper(a, b, n - 1)) x = int(sys.argv[1]) y = int(sys.argv[2]) print "Result of F(%d, %d) is %d" % (x, y, F(x, y))
where hyper(a, n, b) is the simpler algorithmic implementation to $$a\uparrow^{n}b$$.
The Nightmare returns, once again
Did you notice something in the last piece of code? Isn’t the hyper(a, n, b) function similar, in its recursive form, to the Ackermann’s function?
It simply is not possible to efficiently compute A(x, y) for “large” values of x (x >= 4).
I every time emailed this website post page to
all my friends, for the reason that if like to read
itt after that my contascts will too.
Here is my homepage :: among us always impostor
I intended to draft you a bit of remark to thank you very much again for these incredible methods you’ve discussed in this article. It has been certainly remarkably generous of people like you to present freely exactly what a number of us could have distributed for an ebook to help with making some bucks for themselves, and in particular given that you could have tried it if you ever desired. These thoughts in addition worked as a easy way to realize that other people have similar interest much like mine to know many more with regard to this condition. I’m certain there are numerous more enjoyable times up front for people who take a look at your site.
Source textile zero liquid discharge plant
We purchase present playing cards and pay you cash.
You are so interesting! I don’t believe I’ve truly read a single thing like that before. So nice to discover someone with unique thoughts on this issue. Really.. thank you for starting this up. This site is one thing that is needed on the internet, someone with some originality!
Not all offers are ideal for onerous money loans.
Obtain gorgeous free photos about bouquet flowers.
Say I like you” with stunning anniversary flowers.
Also, the flowers were absolutely beautiful.
I like this post, enjoyed this one thanks for posting .
A bouquet of beautiful lily flower is stuffed with surprises.
Online casinos had been invented to supply this reside gaming expertise
completely to users or as part of a bigger providing.
Arrangement was lovely and delivery was fast.
Hello there! I know this is kinda off topic but I was wondering which
blog platform are you using for this website? I’m getting tired of WordPress because I’ve had problems with
hackers and I’m looking at options for another platform.
I would be fantastic if you could point me in the direction of a good platform.
My webpage: absolute carpet & upholstery cleaning
Payday lenders don’t do exhausting credit checks.
A: Money advance charges vary by lender and by state.
This is a topic that’s close to my heart… Cheers! Where are your contact details though?|
http://me2gov.com/__media__/js/netsoltrademark.php?d=www.fairporn.net/
Instagram takipçisi paketleri alımlarının bu site üzerinde her bakımdan en güvenli şekilde yapılabilmesi mümkün oluyor
My Aunt cherished the flowers. My mom loved the flowers.
I’m not sure where you’re getting your information, but great topic. I needs to spend some time learning more or understanding more. Thanks for fantastic information I was looking for this information for my mission.
Nice service – fast and on time delivery.
We are a group of volunteers and starting a new scheme in our community. Your web site provided us with valuable information to work on. You’ve done an impressive job and our entire community will be grateful to you.
The first is a broad range of banking methods available to gamers.
Hi! I could have sworn IÃve been to this website before but after looking at a few of the posts I realized itÃs new to me. Anyhow, IÃm certainly happy I discovered it and IÃll be bookmarking it and checking back regularly!
I added a new list today. I’m going to try to find new sites in a slightly different way. Read all about it by clicking the link above.
However, this could appear more complicated than many people could have initially
believed.
I am also writing to let you understand what a outstanding encounter my friend’s child experienced browsing your web site. She discovered too many details, not to mention what it is like to possess a great coaching heart to get the mediocre ones easily fully understand some tortuous things. You actually did more than our expected results. I appreciate you for coming up with such invaluable, trusted, educational and also easy guidance on this topic to Jane.
I simply could not leave your web sit prior to suggesting
that I actually enjoyed the standard information an individual suply in your guests?
Is going to be back frequently too inspect new posts
Feel free to visit my homepage: among us mod android
Pay dates can’t be on bank holidays or weekends.
This is a great tip especially to those fresh to the blogosphere. Short but very precise info… Thank you for sharing this one. A must read post!
Oh my goodness! Amazing article dude! Many thanks, However I am going through difficulties with your RSS. I don’t understand why I can’t join it. Is there anybody else getting identical RSS issues? Anyone who knows the solution will you kindly respond? Thanx!!
Hello there, I found your web site via Google while looking for a related topic, your web site came up, it looks good. I’ve bookmarked it in my google bookmarks.
Only wanna input on few general things, The website pattern is perfect, the subject matter is very excellent. “If a man does his best, what else is there” by George Smith Patton, Jr..
This might have a big impression on your likelihood of successful for certain video games.
In short, applying for these loans is incredibly straightforward.
Massive full centerpiece of combined flowers.
https://ucuztakipcitr.medium.com/instagram-takipC3A7i-hilesi-2021-41e5b167dda1
They provide probably the most stunning flowers.
Hi there! I just would like to offer you a big thumbs up for the great info you’ve got here on this post. I am coming back to your web site for more soon.