36
2
The Ackermann function is notable for being the one of the simplest examples of a total, computable function that isn't primitive recursive.
We will use the definition of A(m,n)
taking in two nonnegative integers where
A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))
You may implement
- a named or anonymous function taking two integers as input, returning an integer, or
- a program taking two space- or newline-separated integers on STDIN, printing a result to STDOUT.
You may not use an Ackermann function or hyperexponentiation function from a library, if one exists, but you may use any other function from any other library. Regular exponentiation is allowed.
Your function must be able to find the value of A(m,n)
for m ≤ 3 and n ≤ 10 in less than a minute. It must at least theoretically terminate on any other inputs: given infinite stack space, a native Bigint type, and an arbitrarily long period of time, it would return the answer. Edit: If your language has a default recursion depth that is too restrictive, you may reconfigure that at no character cost.
The submission with the shortest number of characters wins.
Here are some values, to check your answer:
A | n=0 1 2 3 4 5 6 7 8 9 10
-----+-----------------------------------------------------------------
m=0 | 1 2 3 4 5 6 7 8 9 10 11
1 | 2 3 4 5 6 7 8 9 10 11 12
2 | 3 5 7 9 11 13 15 17 19 21 23
3 | 5 13 29 61 125 253 509 1021 2045 4093 8189
4 | 13 65533 big really big...
15How has this not been asked before?? – Calvin's Hobbies – 2014-10-22T04:56:22.963
Tried in Python, got ~60 bytes and a lot of stack overflows. Decided not to post as anything that can only calculate
m <= 2
is not very useful :D – PurkkaKoodari – 2014-10-22T06:37:49.2479I think it'd be more fun to make this [tag:fastest-code] – Sp3000 – 2014-10-22T07:43:48.480
22Downvoting because there's no challenge here. The obvious answer -- just naively implementing the function exactly according to its definition -- is always going to be the best answer. So the question is just "Which language has the least number of characters in the obvious expression of Ackermann's function?" The true winner is the programming language, not the person who wrote the obvious program in it. – David Richerby – 2014-10-22T07:52:22.060
I agree that this challenge would be more interesting as a fastest code, currently this challenge seems to be mostly, how can I implement the ackerman function in as little characters without much consideration to speed. Instead of how can I make use of any patterns in the ackerman function to speed it up – Tally – 2014-10-22T08:55:05.000
1What if my language's recursion limit is too low to compute
A(3,8)
and above as naively as the others did? Do I have to come up with a non-recursion solution, or can I also just "assume infinite stack space" in these cases? I'm fairly certain, it would terminate within a minute. – Martin Ender – 2014-10-22T09:53:31.6035@DavidRicherby "The obvious answer [...] is always going to be the best answer." This is not true of all languages. I feel a little dirty for only having an example in my home language, but there are multiple ways to express Ackermann and in some languages you can get savings by using that fact. This was my intention for the challenge. – algorithmshark – 2014-10-22T13:15:37.463
1
@Sp3000 A problem with fastest-code is what counts as cheating. My SO answer to a related question at http://stackoverflow.com/a/12188327/400547 used shortcuts for
– Jon Hanna – 2014-10-23T00:34:31.657m < 3
and one could addreturn BigInteger.Pow(2, n + 3) - 3
form == 3
too. Does that count as cheating?