チューリングマシン入門〜Rustでつくる「2進数加算器」〜

どうも、ryudaiです！

みなさんはチューリングマシンというのを聞いたことがありますか？

文脈によって「チューリング完全」などでチューリングさんのお名前を見聞きすることはあれど、チューリングマシンの実態は掴めていませんでした。

今回「任意の2進数に1を足すチューリングマシンを再現する」という課題をもらったので、それを解きながら理解を深めていこうと思います！言語は何でも良いですが、今回は訓練中のRustにします。

「チューリングマシンを再現する」とは

まずは課題のレギュレーションを把握したいところです。

「2進数に1を足すプログラム」は簡単ですが、それをチューリングマシンとして実装すると…？となります。

調べてみると、チューリングマシンは

無限の長さを持つ「テープ」がある
テープに文字を読み書きできる「ヘッド」が存在する
ヘッドは左右に動き、テープの文字を1文字ずつスキャンできる
マシンは、事前に定義された有限個の状態を持つことができる
ヘッドがスキャンした文字と現在のマシンの状態の組み合わせによって、移動方向や書き込む文字を条件分岐できる

というようなことでした(※正確な定義ではないですが、簡単のため)。

2進数に1を足すには

次はこれをRustで再現するには…という話になるのですが、私は以下の変数を用意することにしました。

tape: テープに書かれた文字を保持する (char型のVec)
index: 現在のヘッドの位置を表す (usize)
state: 現在のマシンの状態を表す (enum Stateを用意して使う)

実装の大雑把な理解はこうです。

まず、tapeの初期値として、任意の2進数を書き込んでおきます (例: 10101)。

初期状態では、ヘッドはこの2進数の一番右まで移動します。

次に足し算のフェーズです。ヘッドがスキャンした数が0だったら1を書き込んで実行終了。スキャンした数が1だったら繰り上がりでヘッドは左に進む。

この単純な作業を反復すればうまくいきそうです。実際にコードを書いていきます。

武器を揃える

まず大元のMachineという構造体を用意しました。チューリングマシン全体をイメージしています。

struct Machine {
    tape: Vec<char>,
    state: State,
    index: usize,
}

状態は以下の4つとしました。
Printは、最後に結果を表示するためだけの状態なので、必要ないかもしれません。

enum State {
    Init,
    Add,
    End,
    Print,
}

このMachineに対していろんなメソッドをimpl(実装)していきます。

左右に動くメソッド:

fn move_right(&mut self) {
    self.index += 1;
}

fn move_left(&mut self) {
    self.index -= 1;
}

文字を書き込むメソッド:

fn write_char(&mut self, char: char) {
    self.tape[self.index] = char;
}

状態を変更するメソッド:

fn change_state(&mut self, state: State) {
    self.state = state;
}

コアロジックの実装

問題はこの先、状態による条件分岐です。Rustではmatch式を使うと便利に書けそうなところです。

今回はrunというメソッドを用意し、実装していきます。

fn run(&mut self) {
    let char = self.tape[self.index];
    match self.state {
        State::Add => match char {
            '1' => {
                self.write_char('0');
                self.move_left();
            }
            '0' | 'B' | _ => {
                self.write_char('1');
                self.change_state(State::End);
            }
        },
        _ => todo!(),
    }
    self.run();
}

上は、状態がAddのときの実装です。

もし読み取った数値が1だったら、(繰り上がりなので)0を書き込み左に進む
0もしくはB(ブランク/空白)の場合、1を書き込み、繰り上がりはないので終了

突然Bが出てきてびっくりしますが、チューリングマシンでは無限に続くテープを想定するため、2進数の外側はブランクとして定義しています。今回の場合、繰り上がりを続けて桁が1つ増えた時に限り、ブランクに書き込むことになります。

実装上無限にブランクを用意するのは大変だったので、Machineをnewするときに2進数を受け取り、その左右に2つずつブランクをくっつけるようにしています。

fn new(num: &str) -> Self {
    Self {
        tape: format!("BB{num}BB").chars().collect(),
        state: State::Init,
        index: 2,
    }
}

index: 2の部分は、初期状態(Init)の実装の都合で恣意的に決めています。「ヘッドを2進数の一番左の文字にセットしてから始める」という意味合いになりますが、他にうまいやり方はありそうです。

そんなこんなで、他の状態も作成したら完成です。コード全体は最後に載せたので興味のある方はそちらを！

実行してみる

まず、100で実行してみます。

fn main() {
    let mut machine = Machine::new("100");
    machine.run();
}

1桁目が1になり、101と返ってきました。

では繰り上がりの場合はどうでしょうか？以下のように、11111で始めてみます。

fn main() {
    let mut machine = Machine::new("11111");
    machine.run();
}

正しく、100000が返ってきました！

感想

今回チューリングマシンを再現する中で、「数字を足す」という概念を「有限個の状態の条件分岐によって、数字を書き換える操作」と捉え直すことができました。

この状態数を増やしていけば、たしかに0と1でなんでも表現できそうな気がしてきます。

今回扱った状態とその条件分岐を表にするとこうなります。ソースコードと照らし合わせて見てみてください。

コード全体

以下が今回書いたコード全体です。

#[derive(Debug, PartialEq)]
enum State {
    Init,
    Add,
    End,
    Print,
}

#[derive(Debug)]
struct Machine {
    tape: Vec<char>,
    state: State,
    index: usize,
}

impl Machine {
    fn new(num: &str) -> Self {
        Self {
            tape: format!("BB{num}BB").chars().collect(),
            state: State::Init,
            index: 2,
        }
    }

    fn move_right(&mut self) {
        self.index += 1;
    }

    fn move_left(&mut self) {
        self.index -= 1;
    }

    fn write_char(&mut self, char: char) {
        self.tape[self.index] = char;
    }

    fn change_state(&mut self, state: State) {
        self.state = state;
    }

    fn run(&mut self) {
        let char = self.tape[self.index];
        match self.state {
            State::Init => {
                if char == 'B' {
                    self.move_left();
                    self.change_state(State::Add);
                } else {
                    self.move_right();
                }
            }
            State::Add => match char {
                '1' => {
                    self.write_char('0');
                    self.move_left();
                }
                '0' | 'B' | _ => {
                    self.write_char('1');
                    self.change_state(State::End);
                }
            },
            State::End => {
                if char == 'B' {
                    self.move_right();
                    self.change_state(State::Print);
                } else {
                    self.move_left();
                }
            }
            State::Print => {
                if char == 'B' {
                    return;
                } else {
                    print!("{}", char);
                    self.move_right();
                }
            }
        }
        self.run();
    }
}

fn main() {
    let mut machine = Machine::new("11111");
    machine.run();
}

チューリングマシン入門 〜Rustでつくる「2進数加算器」〜