45
\$\begingroup\$

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

$$\begin{align} A(0,n) & = n+1 \\ A(m,0) & = A(m-1,1) \\ A(m,n) & = A(m-1,A(m,n-1)) \end{align}$$

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 \le 3\$ and \$n \le 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:

$$\begin{array}{c|cccccccccc} A & n = 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 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 & \text{big} \end{array}$$

\$\endgroup\$
8
  • 16
    \$\begingroup\$ How has this not been asked before?? \$\endgroup\$ Oct 22, 2014 at 4:56
  • 12
    \$\begingroup\$ I think it'd be more fun to make this fastest-code \$\endgroup\$
    – Sp3000
    Oct 22, 2014 at 7:43
  • 23
    \$\begingroup\$ Downvoting 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. \$\endgroup\$ Oct 22, 2014 at 7:52
  • 1
    \$\begingroup\$ What 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. \$\endgroup\$ Oct 22, 2014 at 9:53
  • 7
    \$\begingroup\$ @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. \$\endgroup\$ Oct 22, 2014 at 13:15

42 Answers 42

1
2
1
\$\begingroup\$

Jelly, 17 bytes

’çç’}¥ɗ’ç1Ɗṛ?‘}ḷ?

Try it online!

Requires a higher recursion limit for \$A(3, 10)\$ than the Jelly interpreter has, but finishes within 1 minute when I adjust the limit locally

Full program, due to some bugs with ß.

How it works

’çç’}¥ɗ’ç1Ɗṛ?‘}ḷ? - Main link A(m, n). Takes m on the left and n on the right
                ? - If:
               ḷ  -   Condition: m is non-zero
                  -   Then:
            ?     -     If:
           ṛ      -       Condition: n in non-zero
      ɗ           -       Then:
’                 -         m-1
     ¥            -         Group the previous 2 links into a dyad f(m, n):
   ’}             -           n-1
  ç               -           A(m, n-1)
 ç                -         A(m-1, A(m, n-1)
          Ɗ       -       Else:
       ’          -         m-1
        ç1        -         A(m-1, 1)
              }   -   Else:
             ‘    -     n+1
\$\endgroup\$
2
  • \$\begingroup\$ I wonder if it's possible to adjust the limit via the python eval command \$\endgroup\$
    – Razetime
    Apr 28, 2021 at 11:34
  • \$\begingroup\$ @Razetime Unfortunately, the problem on TIO is that Jelly segfaults if it recurses too much: Try it online!, whereas it doesn't when run locally \$\endgroup\$ Apr 28, 2021 at 11:40
1
\$\begingroup\$

MMIX, 56 bytes (14 instructions)

5A000003 23000101 F8010000 27000001 5A010003 E3010001 F1FFFFFA
FE020004 23040001 27050101 FB03FFF6 F6040002 C9010003 F1FFFFF3

Disassembly and explanation

ack PBNZ  $0,0F     // if(!m) {
    ADDU  $0,$1,1   //   m = n + 1
    POP   1,0       //   return m }
0H  SUBU  $0,$0,1   // m = m - 1
    PBNZ  $1,0F     // if(!n) {
    SETL  $1,1      //   n = 1
    JMP   ack       //   return ack(m,n) }
0H  GET   $2,rJ     // x = retaddr (to avoid trampling)
    ADDU  $4,$0,1   // m' = m + 1
    SUBU  $5,$1,1   // n' = n - 1
    PUSHJ $3,ack    // a = ack(m',n')
    PUT   rJ,$2     // retaddr = x
    SET   $1,$3     // n = a
    JMP   ack       // return ack(m,n)

There's hefty use here of tail recursion optimization, not that that'll help much (four words of stack are used here for every time we don't tail recurse, and the stack segment only holds \$2^{58}\$ words).

\$\endgroup\$
1
\$\begingroup\$

Pyth, 15 bytes

M?GgtG?HgGtH1hH

Try it online! (sample usage of the function g3T added, which means g(3,10))

\$\endgroup\$
1
\$\begingroup\$

UGL, 31 30 bytes

iiRuldr%l%lR$d%rd:u%d:%+uRu:ro

Input separated by newlines.

Try it online!

(It has been implemented as a standard example in the interpreter.)

\$\endgroup\$
0
\$\begingroup\$

J : 50

>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.

Returns in a fraction of a second for 0...3 vs 0 ... 10:

   A=:>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.
   timespacex 'res=:(i.4) A"0 table (i.11)'
0.0336829 3.54035e6
   res
┌───┬──────────────────────────────────────────┐
│A"0│0  1  2  3   4   5   6    7    8    9   10│
├───┼──────────────────────────────────────────┤
│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│
└───┴──────────────────────────────────────────┘

PS: the "0 serves to make A work on each single element, instead of gobbling up the left and right array, and generating length errors. But it's not needed for eg. 9 = 2 A 3 .

\$\endgroup\$
1
0
\$\begingroup\$

Haskell: 81 69 bytes

a::Int->Int->Int
a 0 n=n+1
a m 0=a (m-1) 1
a m n=a (m-1) a m (n-1)

a 3 10 takes about 45 seconds.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ this is code golf, so you should try to have the shortest code possible. for example, remove unnecessary spaces and the explicit type \$\endgroup\$ Oct 22, 2014 at 13:34
  • \$\begingroup\$ you're also missing the parens on the fourth line \$\endgroup\$ Oct 22, 2014 at 13:36
0
\$\begingroup\$

Ruby, 65

h,a={},->m,n{h[[m,n]]||=m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])}

Explanation

This is a pretty straightforward translation of the algorithm given in the problem description.

  • Input is taken as the arguments to a lambda. Two Integers are expected.
  • For speed and avoiding stack-overflow errors, answers are memoized in the Hash h. The ||= operator is used to calculate a value that wasn't previously calculated.

a[3,10] is calculated in ~0.1 sec on my machine.

Here's an ungolfed version

h = {}
a = lambda do |m,n|
  h[[m,n]] ||= if m < 1 
    n + 1
  elsif n < 1
    a[m-1,1]
  else
    a[m-1,a[m,n-1]]
  end
end
\$\endgroup\$
2
  • \$\begingroup\$ a[3,10] throw a SystemStackError on my machine... \$\endgroup\$ Jun 18, 2016 at 15:44
  • \$\begingroup\$ Golf nitpicks: You could change m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]]) to m<1?n+1:a[m-1,n<1?1:a[m,n-1]] \$\endgroup\$ Nov 6, 2017 at 23:32
0
\$\begingroup\$

Mouse-2002, 99 83 bytes

$Y1%j:j.0=m:2%k:k.0=n:m.n.>[k.1+!|m.n.<[#Y,j.1-,1;|m.n.*0=[#Y,j.1-,#Y,j.,k.1+;;]]]@
\$\endgroup\$
0
\$\begingroup\$

Java, 274 bytes

import java.math.*;class a{BigInteger A(BigInteger b,BigInteger B){if(b.equals(BigInteger.ZERO))return B.add(BigInteger.ONE);if(B.equals(BigInteger.ZERO))return A(b.subtract(BigInteger.ONE),BigInteger.ONE);return A(b.subtract(BigInteger.ONE),A(b,B.subtract(BigInteger.ONE)));}}

It calculates A(3,10) in a few seconds, and given infinite memory and stack space, it can calculate any combination of b and B as long as the result is below 22147483647-1.

\$\endgroup\$
1
  • \$\begingroup\$ I know it's been a while, but you can golf this to 185 bytes: import java.math.*;BigInteger A(BigInteger b,BigInteger B){return b.equals(B.ZERO)?B.add(B.ONE):B.equals(B.ZERO)?A(b.subtract(B.ONE),B.ONE):A(b.subtract(B.ONE),A(b,B.subtract(B.ONE)));} \$\endgroup\$ Mar 21, 2018 at 10:28
0
\$\begingroup\$

Haskell, 47 bytes

a 0 n=n+1
a m 0=a(m-1)1
a m n=a(m-1)(a m (n-1))

(Run using ghci <filename>) Almost directly copies from the problem definition (thank you pattern matching!).

\$\endgroup\$
2
  • \$\begingroup\$ You may want to include a TIO link so everyone can test your submission? \$\endgroup\$
    – RGS
    Mar 22, 2020 at 18:38
  • \$\begingroup\$ I think a(m-1)(a m (n-1)) can be a(m-1).a m$n-1. \$\endgroup\$ Mar 23, 2020 at 1:44
0
\$\begingroup\$

Erlang (escript), 53 bytes

I tried to put the pattern matching in an if statement; turns out that makes the program longer...

a(0,N)->N+1;a(M,0)->a(M-1,1);a(M,N)->a(M-1,a(M,N-1)).

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 12 bytes

?ßUÉ!V´ªß:VÄ

Try it

?ßUÉ!V´ªß:VÄ     :Implicit input of integers U=m & V=n
?                :If U is not 0
 ß               :Recursive call with arguments
  UÉ             :  U-1 and
    !V´          :  Logical NOT of postfix decremented V
       ª         :  Logical OR with
        ß        :  Recursive call with arguments U and the now decremented V
         :VÄ     :Else return V+1
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.