The Ackermann function

Question

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}$$

Answer 1

APL (Dyalog Unicode), 22 bytes

{0=⍺:1+⍵⋄1∇⍣(⍵+1)⍨⍺-1}

Try it online!

A port of proud haskeller's Haskell answer. Uses the fact that Ack(m,n) is equal to Ack(m-1,?) applied n+1 times to 1.

How it works

{0=⍺:1+⍵⋄1∇⍣(⍵+1)⍨⍺-1}
{                    }  ⍝ ⍺←m, ⍵←n
 0=⍺:1+⍵⋄               ⍝ If m = 0, return 1 + n
          ∇      ⍨⍺-1   ⍝ Apply (m-1)∇ (∇ is recursive call)
           ⍣(⍵+1)       ⍝ n+1 times
         1              ⍝ to the initial value 1

Answer 2

Io, 53 bytes

Yet another recursion solution.

a :=method(m,n,if(m<1,n+1,a(m-1,if(n<1,1,a(m,n-1)))))

Try it online!

Answer 3

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

Answer 4

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).

Answer 5

Pyth, 15 bytes

M?GgtG?HgGtH1hH

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

Answer 6

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.)

Answer 7

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 .

Answer 8

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.

Answer 9

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

Answer 10

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+;;]]]@

Answer 11

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 2^2147483647-1.

Answer 12

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!

Answer 13

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

Answer 14

Python 3.11, 96 bytes

def a(m,n):
    if m==0:return n+1
    elif n==0:return a(m-1,1)
    else:return a(m-1,a(m,n-1))

Ungolfed:

def a(m, n):
    if m == 0:
        return n + 1
    elif n == 0:
        return a(m-1, 1)
    else:
        return a(m-1, a(m, n-1))

Answer 15

Pascal, 110 B

To prevent death-by-boredom victims, the boilerplate recursive definition has been omitted. Using the boilerplate recursive definition as reference, you can save 1 byte in code length by doing the following:

• Presume the m = 0 case the default case. Do not wrap it in an if statement, just calculate A ≔ n + 1 (and possibly overwrite this value).
• This necessitates a different expression for the m ≠ 0 ∧ n = 0 situation. The following code uses sets: [n] − [m] = [0]. It means, take the integer set consisting of the single element n, remove from it all elements found in the second set ([m]) and compare the resulting set value against the set [0].
• The fallback can be phrased as n × m > 0. Recall that any product is zero as soon as at least one factor is zero. Phrasing the fallback like this is necessary, because there are no else clauses.

function A(m,n:integer):integer;begin
A:=n+1;if[n]-[m]=[0]then A:=A(m-1,1);if n*m>0 then A:=A(m-1,A(m,n-1))end

NB: The limits of integer are implementation-defined. For example, the GNU Pascal Compiler implementation will require the ‑‑setlimit=8189 parameter (or larger) to work correctly for \$m \leq 3\$, \$n \leq 10\$ test cases (beside the fact of having sufficient memory).