☰

阿克曼函数

tag-icon • tag-icon macros errors recursion robust-commands
阿克曼函数

我正在尝试编写一个宏来评估 Ackermann 函数的结果。如果有人不知道，定义如下：

在此处输入图片描述

因此，我尝试编写一个能够计算它的代码，但我似乎无法弄清楚。

答案1

这是一个\romannumeral基于扩展的解决方案，使用bigintcalc-包裹。

请注意：以递归方式定义的 Ackermann 函数意味着嵌套调用，\romannumeral这会对语义嵌套造成影响。

egreg、wipet和Marcel Krüger的解决方案不存在这个问题。

说实话：我认为 TeX 不是计算 Ackermann 函数值的合适工具。可能更好的方法是\write18使用 来调用外部程序，该程序可以更有效地进行计算，并将结果存储在文本文件中，之后 TeX 可以通过导入结果来处理该文件\input。

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

在此处输入图片描述

答案2

这是一个使用经典 TeX 工具（不带 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

该\afterfi宏用于节省 TeX 堆栈。

答案3

当然，这需要 LuaTeX 的答案。我优化了一些简单的情况，但它基于 64 位有符号整数，因此只要任何值大于，它就会失败2^63-1=9223372036854775807。但它确实会检查这一点：

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

在此处输入图片描述

答案4

很遗憾迟到了，但是既然已经发布了 Lua(La)TeX 答案，我将编写一个 ConTeXt 答案（不过，它可以像其他 LuaTeX 答案一样，使用扫描仪轻松适应 LuaLaTeX）。除非您想冻结计算机，否则不要尝试直接实现它，而是像其他答案一样在更简单的情况下进行切片。它不会崩溃，而是会打印警告。:)

为了作弊，我们需要lua-nums图书馆，感兴趣的人可以通过 Luarocks 访问。

\startluacode
--Use bn if bn.lua is in your working directory:
--local bn = require"bn"
--Use nums.bn if you've installed it via Luarocks
local bn = require"nums.bn"

local function ackermann(m,n)
    local m, n = bn(m), bn(n)
    if m == bn(0) then return n + 1 end
    if m == bn(1) then return n + 2 end
    if m == bn(2) then return (n<<1) + 3 end
    if m == bn(3) then return (bn(1)<<(n+3)) - 3 end
    if m == bn(4) and n == bn(0) then return 13 end
    if m == bn(4) and n == bn(2) then return ((bn(1)<<65536) - 3) end
    if (m == bn(4) and n == bn(1)) or (m == bn(5) and n == bn(0)) then return 65533 end
    context.writestatus("ackermann","Please don't!") 
    return "" 
end

--\hyphenateddigits requires an up-to-date ConTeXt
interfaces.implement{
    name            = "ackermann",
    public          = true,
    arguments   = "2 strings",
    actions         = 
    function(x,y)
        context.hyphenateddigits(tostring(ackermann(x,y)))
    end
}
\stopluacode
\starttext
\startTEXpage
%% Examples
%% Rather boring
\startlines
\ackermann{0}{0}
\ackermann{1}{0}
\ackermann{1}{1}
\ackermann{2}{0}
\ackermann{2}{1}
\ackermann{2}{2}
\ackermann{3}{0}
\ackermann{3}{1}
\ackermann{3}{2}
\ackermann{3}{3}
\ackermann{3}{70}
\ackermann{4}{0}
\ackermann{4}{1}
\stoplines
\stopTEXpage
%% Fun
\ackermann{4}{2}
\stoptext

在此处输入图片描述

因为\ackermann{4}{2}我们有一些非常有趣的事情：

在此处输入图片描述

相关内容