2.times { think_before :posting }
Post con tag Python
Mastering the Ackermann Function – Part 2
2 ago
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 …
Continua >
If you want to thank me for this post, feel free to pay me a coffee! :)
Mastering the Ackermann Function
29 lug
Yesterday I came in touch with a curious, astonishing mathematical function. It’s called Ackermann function.
Mathematically speaking, it is a well-defined total function. That is, it has defined values for every integer input (= total function), and this value is not ambiguous (every input has one and one only possible output value) (= well-defined).
Speaking about computer science, this function is computable, but it’s not a primitive recursive function. In other words, you can implement an algorithm to express the function using while-loops (= computable), but still you cannot write an equivalent algorithm using only do-loops (= not primitive recursive). I suggest you to try this statement.
The function has this form:
As you can see, it’s form is fairly simple. But, even if it seems simple, its values explode quickly. A(4, 2), for example, has more than 19.000 digits.
Representation of the Ackermann Function on the complex plane
What I want to talk about is the possible implementation of such a function by means of a computer algorithm. I will use Python for the next examples, but the description is language-independent.
If you want to thank me for this post, feel free to pay me a coffee! :)