はじめに
Rustの macro_rules! はチューリング完全か？
結論：チューリング完全です
手法
2 状態 18 記号、固定された遷移ルールのチューリングマシン $T$ がチューリング完全1であることはよく知られていますが、Rust のマクロ上でそれを実行可能とすることでチューリング完全であることを示します。
fn main() {
let t = tm0!("F", "A", "A", "A",
"F", "F", "A", "A", "A", "A", "A", "A", "F", "A", "A",
"F", "F", "Q", "Q"; "F", "A", "A", "A",
"M", "A", "M");
print!("{}", t);
}
ああ！待ってください！
「結局マクロで置き換えてRustの処理を実行しているだけか、舐めプ乙」と思った方、もう少し話をお聞きください。実際、１つの遷移ルールを表すマクロの宣言はこんな感じになります。
($left:tt; "A", $($rights:tt),*) => {
tm1!("C"; $left, "R", $($rights),*)
};
ね？Rustの処理は入っていない でしょう？
以降では、チューリングマシンをどのようにマクロに畳み込んだのかを説明していきます。
どうやって動くの？
まず、マクロの仕様面の話から始めます。
マクロは tm1! と tm2! があります。これは $T$ の内部状態に対応しており、内部状態が $q_1$ の時は tm1! を、そうでないときは tm2! を解決します。これにより、状態遷移も内部で別のtm マクロを呼び出すことで行うことができます。
macro_rules! tm1 {
($left:tt; "A", $($rights:tt),*) => {
tm1!("C"; $left, "R", $($rights),*)
};
//...
}
macro_rules! tm2 {
($($lefts:tt),*; "A", $right:tt) => {
tm2!("C", $($lefts),*; $right, "C")
};
//...
}
テープの埋め込みは、単に文字列リテラルを "," で並べて行います。例えば最初に出した以下のコードはテープ "…CQQFFAAFAAAAAAFFAAAF*FAAAMAMC…" を表しています(*F が初期ヘッド位置)。なお、マクロ上では ; の右の記号が現在ヘッド位置であり、ヘッドの左側の記号は逆順に記載します。
fn main() {
let t = tm0!("F", "A", "A", "A",
"F", "F", "A", "A", "A", "A", "A", "A", "F", "A", "A",
"F", "F", "Q", "Q"; "F", "A", "A", "A",
"M", "A", "M");
print!("{}", t);
}
以上で、状態・テープの取り扱い方が明確になったので、改めて遷移ルールの実装を記述できます。
遷移ルール？
$T$ の、ある１つの遷移ルールを抜き出してきました。これは、「状態 $q_1$ の時に 記号 $A$ を読んだら、記号$R$に書き換えて左に移動する」というルールを表しています。（２つでひとかたまりです。)
macro_rules! tm1 {
($left:tt; "A", $($rights:tt),*) => {
tm1!("C"; $left, "R", $($rights),*)
};
($left:tt, $($lefts:tt),*; "A", $($rights:tt),*) => {
tm1!($($lefts),*; $left, "R", $($rights),*)
};
//...
}
なんとなくヘッドの位置 (; の位置) が動いていることを感じてください。
"C" は空白記号（テープの左右に無限にある記号）です。ヘッドがテープの外に出ないよう、適宜"C"を補います。
また、右に移動する場合、
macro_rules! tm1 {
//...
($($lefts:tt),*; "B", $right:tt) => {
tm1!("E", $($lefts),*; $right, "C")
};
($($lefts:tt),*; "B", $right:tt, $($rights:tt),*) => {
tm1!("E", $($lefts),*; $right, $($rights),*)
};
//...
}
です。ちょうど left と right が逆になった形となっています。（前述のとおり、; より左の記号は逆順で記載されています。）
停止ルール？ (ツッコミポイント)
マクロがチューリング完全な系であるためには、停止ルールを定める必要があります。停止ルールは以下です。
macro_rules! tm1 {
//...
($($lefts:tt),*; "Q", $($rights:tt),*) => {{
let mut t = vec![$($lefts),*];
t.reverse();
t.extend(vec!["*Q", $($rights),*]);
t.join("")
}};
//...
}
「おい！Rustの式が出てるやんけ！」...ごもっともです。マクロの tt 要素をそのまま取り出す方法が皆目見当つきませんでしたので、妥協した面があります。
一方で、ここに至るまでマクロ上の tt のみで演算をしているので、その意味で私はチューリング完全の要件を満たしているとも考えています2。
制限
チューリング完全性に関するいくつかの制限・議論点を述べます。ただし、他のチューリング完全と言われている系もだいたい同じ問題を孕んでいます。
- 上述の、「停止ルール問題」
- 真にチューリングマシンを再現するためには、再帰の深さが無限である必要があります（そして、Rustはそうではありません）。特に、この方法であると$T$ の１ステップが１再帰に相当するため、すぐに上限に達します。ということで、
#![recursion_limit = "1024"]をコードの先頭に補っています。他の言語も同じことですが - 真に〃メモリが無限に必要ですが、他の言語も同じです
補遺
停止ルールのバリアントについて (3/15 追記)
$T$のテープ記号を表すものとして、文字列の代わりに以下のマクロを使用することにすれば...
macro_rules! A {() => {print!("A")}}
macro_rules! B {() => {print!("B")}}
macro_rules! C {() => {print!("C")}}
// ...
macro_rules! P {() => {print!("P")}}
macro_rules! Q {() => {print!("Q")}}
macro_rules! R {() => {print!("R")}}
macro_rules! head {() => {print!(";")}}
停止ルールは ↓ のようになりますね。こちらの方がマクロだけで構成する記法としては自然でしょうか。
macro_rules! tm1 {
//...
($($lefts:tt),*; Q, $($rights:tt),*) => {{
$($lefts!();)*head!();Q!();$($rights!();)*
}};
//...
}
終わりに
形式言語をこねくり回すのは楽しい
リンク集（Playground 含む）
オリジナル：
「停止ルールのバリアントについて」を適用したもの (3/15 追記)：
Rustの型システムがチューリング完全である、という主張の記事 （マクロがチューリング完全である...という記事は現在なさそう？）