Ackermann Function

Here is a solution using classical TeX tools (without expl3).

\def\afterfi#1#2\fi{\fi#1}
\def\Ac#1#2{\ifnum#1=0 \afterfi{\the\numexpr#2+1\relax}%
            \else \afterfi{\ifnum#2=0 \afterfi{\Aeval{#1-1}{1}}%
                           \else \afterfi{\Aeval{#1-1}{\Aeval{#1}{#2-1}}}\fi}\fi}
\def\Aeval#1#2{\expanded{\noexpand\Ac{\the\numexpr#1}{\the\numexpr#2}}}
\def\A(#1,#2){$A(#1,#2)=\Ac{#1}{#2}$\par}

\A(0,0)
\A(1,0)
\A(2,0)
\A(0,1)
\A(0,2)
\A(1,1)
\A(2,2)
\A(2,3)
\A(3,3)
\A(3,4)

\bye

The \afterfi macro is used in order to spare TeX stack.

Here is a \romannumeral-expansion-based solution using the bigintcalc-package.

Be aware: The Ackermann-function being defined recursively implies nesting calls to \romannumeral which takes its toll on the semantic nest.

The solutions of egreg, wipet and Marcel Krüger don't have this problem.

\documentclass{article}
\usepackage{amsmath}
\usepackage{bigintcalc}

\newcommand\UDfirstoftwo[2]{#1}%
\newcommand\UDsecondoftwo[2]{#2}%
\newcommand\UDPassFirstToSecond[2]{#2{#1}}%
\csname @ifdefinable\endcsname\UDstopromannumeral{\chardef\UDstopromannumeral=`\^^00}%

% \Ackermann{m}{n}

\newcommand\Ackermann{%
  \romannumeral\Ackermannloop
}%

\newcommand\Ackermannloop[2]{%
  \ifnum\bigintcalcCmp{#1}{0}=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
  {\expandafter\expandafter\expandafter\UDstopromannumeral\bigintcalcInc{#2}}{%
    \ifnum\bigintcalcCmp{#2}{0}=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
    {%
       \expandafter\expandafter\expandafter\Ackermannloop\expandafter\expandafter\expandafter{\bigintcalcDec{#1}}{1}%
    }%
    {%
       \expandafter\UDPassFirstToSecond\expandafter{%
         \romannumeral
         \expandafter\expandafter\expandafter\UDPassFirstToSecond
         \expandafter\expandafter\expandafter{\bigintcalcDec{#2}}{\Ackermannloop{#1}}}{%
         \expandafter\expandafter\expandafter\Ackermannloop\expandafter\expandafter\expandafter{\bigintcalcDec{#1}}%
      }%
    }%
  }%
}%

\begin{document}

$\text{Ackermann}(0, 0)=\Ackermann{0}{0}$

$\text{Ackermann}(1, 0)=\Ackermann{1}{0}$

$\text{Ackermann}(2, 0)=\Ackermann{2}{0}$

$\text{Ackermann}(0, 1)=\Ackermann{0}{1}$

$\text{Ackermann}(0, 2)=\Ackermann{0}{2}$

$\text{Ackermann}(1, 1)=\Ackermann{1}{1}$

$\text{Ackermann}(2, 2)=\Ackermann{2}{2}$

$\text{Ackermann}(2, 3)=\Ackermann{2}{3}$

$\text{Ackermann}(3, 3)=\Ackermann{3}{3}$

$\text{Ackermann}(3, 4)=\Ackermann{3}{4}$

% \Ackermann{4}{2}
% I suppose the above yields something like:
% ! TeX capacity exceeded, sorry [input stack size=5000].

\end{document}

Of course this needs a LuaTeX answer. I optimized some of the easy cases, but it is based on 64bit signed integers, so it fails whenever any value gets bigger than 2^63-1=9223372036854775807. It does check for this though:

\documentclass{article}
\directlua{
  local maxint = math.maxinteger
  local almostmaxint = math.maxinteger
  local almosthalfmaxinteger = maxint/2-2
  local function A(m, n)
    if m == 0 then
      if n==maxint then
        error[[Overflow]]
      end
      return n+1 end
    if n == 0 then return A(m-1, 1) end
    if m == 1 then
      if n==almostmaxint or n ==maxint then
        error[[Overflow]]
      end
      return n+2
    end % Optimize simple case
    if m == 2 then
      if n > almosthalfmaxinteger then
        error[[Overflow]]
      end
      return 2*n+3
    end % Optimize simple case
    return A(m-1, A(m, n-1))
  end
  ackermann = A
}
\NewExpandableDocumentCommand\ackermann{mm}{\directlua{tex.write(ackermann(token.scan_int(), token.scan_int()))} \numexpr#1\relax \numexpr#2\relax}

\begin{document}

$A(0,0)=\ackermann{0}{0}$

$A(1,0)=\ackermann{1}{0}$

$A(2,0)=\ackermann{2}{0}$

$A(0,1)=\ackermann{0}{1}$

$A(0,2)=\ackermann{0}{2}$

$A(1,1)=\ackermann{1}{1}$

$A(2,2)=\ackermann{2}{2}$

$A(2,3)=\ackermann{2}{3}$

$A(3,3)=\ackermann{3}{3}$

$A(3,7)=\ackermann{3}{7}$

$A(3,8)=\ackermann{3}{8}$

$A(3,9)=\ackermann{3}{9}$

$A(3,20)=\ackermann{3}{20}$

$A(3,40)=\ackermann{3}{40}$

$A(4,0)=\ackermann{4}{0}$

$A(4,1)=\ackermann{4}{1}$

\end{document}