要約

競プロの練習(APG4b)をやってたら再帰関数が出てきて、再帰の様子をプログラムに出力するものがあったので、最近やったAckerman関数の計算の様子をプログラムで作ってやった。

Ackerman関数とは

原始再帰的ではない再帰関数. 正確には2重再帰関数. 記号論理学でやった(計算可能な関数が部分再帰関数の集合と一致するとか). 定義は$n, m \in \mathbb{N} $に対して, $$ \text{Ack}(m, n) = \begin{cases} n + 1 & \text{if } m = 0 \cr \text{Ack}(m - 1, 1) & \text{if } n = 0 \cr \text{Ack}(m - 1, \text{Ack}(m, n - 1)) & \text{otherwise} \end{cases} $$ その値は爆発的に増加する.

プログラム

言語はC++, 出力はログが消えるので、テキストファイルに出した.

やりたいこと

Ack(1, 1)
=Ack(0, Ack(1, 0))
=Ack(0, Ack(0, 1))
=Ack(0, 2)
=3

手計算でやるときのこんな感じのテキストを作りたい

本体

説明

基本的にvectorack_processに手計算の数字だけを並べたものを格納する感じ. ack_calcでack_processを求め、print_lineを行数繰り返すことで出力する.

ack_calcにはack_processを参照渡ししている. 参照については今日知った. このプログラムでは配列を返す必要がなくなり、また膨大な配列をコピーする必要がなくなるので、参照を使う絶好の機会だと思った. 計算終了判定のあと、Ackerman関数の場合分けに乗っ取って、ack_processに1つ要素を追加してそこに次の値をあたしていく動作をする.

print_lineもまた、再帰を使って括弧閉じを出力するようにしている.

これを.txtファイルに出力すれば目的のログが得られる.

例(Ack(3, 3))¹

長いのでこちらへ(画像付き) とにかく長い

感想

Ack(4, 1)でアウトになったのででかさがわかった. ログが長すぎていろいろ大変. 巨大数って巨大なんだな(小並感).

おまけ：数式表示について

久しぶりに数式のある記事を編集していろいろ気づいたのでまとめる.

①:inline表示

以前の記事ではinline表示ができていなかった²。こちらの記事を参考にinlineを$ ... $で表示するようにしてみたところ問題なく動いた.

②:curly brace

KaTeXでは\left\{,right\}は使えない模様(Supported Functionsに載ってなかった)(\left(, \left.などは使える.). なので今回のようなcurly braceで場合分けをする場合はcasesを使うしかない.

③:改行

Hugoを使っているので、mdを一度HTMLに変換して、そのあとにKaTeXが作用する。そのさい改行のコード\\ \nがHugoによって処理され、<br>が挿入されうまくレンダリングができなかった.

1. mdで\\の後に改行を入れない
2. KaTeXでサポートされているほかの物を使用する(\crなど. 詳しく.)

ことで対処できる.

おまけ②:syntax highlightについて

なんかテーマのsyntax highlightが嫌だった(おそらくVS Codeのものと違いすぎるため)ので、テーマを見ていて見つけたgistを使う方法を試してみた。見た目の問題は無し. ダークモードには対応してないけど、rawも見れるしけっこういいのでは?³