Rustでチューリングマシン

## TL;DR;

Rustの勉強がてらチューリングマシンのエミュレータを作成し、足し算・かけ算などの関数を実現するチューリングマシンを作りました。依存クレートなし、１ファイル。コアな部分は150行くらいです。

## 機械の仕様

書籍ごとに若干の違いがあるので、実装するチューリング機械の仕様を整理します。なお、本記事の仕様は Boolos "Computability and Logic" に概ね準じます。

**4-tupleな状態遷移**: 機械は「内部状態 `S` でヘッドのテープ値が `a` の時, コマンド `c` を実行し 内部状態を `S'` に更新せよ」という4-tupleで表現できる形式の指示（の一覧）を持つ。コマンドは「0 or 1 を書く」「左or右にひとつ動く」の4つであり **テープの書き込みとテープの移動は同時に行わない** (同時に行えるモデルの場合は 5-tupleな状態遷移となる. 参考:[wikipedia](https://en.wikipedia.org/wiki/Turing_machine#Alternative_definitions)。計算能力に違いはない)。

**初期状態について**: 機械の内部状態に 1,2,3....,k と識別子を振るが、初期状態は 1 で識別されると約束する（そのように状態遷移を定義することと約束する）。ヘッドの初期位置は、最も左に存在する 1 の場所と約束する。なお、全てが 0 のテープの場合は適当に選んだ場所を初期位置と約束する。

**停止に関して**: 明示的には停止状態を定義しない。機械の動作中にマッチする遷移指示が存在しない場合、停止状態になると約束する。言い換えると、停止状態及び停止状態への遷移指示をすべて省略すると約束する。

**関数と機械の対応**: 機械と $\mathbb N^{+k} \rightarrow \mathbb N^+$ な部分関数を対応付ける。入力となる k 個の数は 0 で区切られた1の塊であらわす。例えば 2 + 3 の計算では `110111` (すなわち `--.---`)がテープの初期状態となるようにする。関数値が定義できるとは、停止時に a) 1が連続する塊が 1つのみ b) かつテープヘッドが 最も左に存在する 1 の場所にある 、の両方が満たされている場合のみに限る。そうでない場合の関数値は undefined とする。

## やること
以下の関数をチューリング機械で実装する（いずれもBoolosの教科書で実装されている）

- 定数関数 `const_3`（引数0で出力が3となる関数)
- 二倍する関数 `double`
- パリティ関数 `parity` (偶数のときは0, 奇数の時は1)
- 足し算関数 `add`
- かけ算関数 `mult`

## 設計/概要
いきなりコードを見せてもアレなので、少しまとまりのない文章だが 設計思想を箇条書きする。

**略記**: テープの 0, 1 をそれぞれ `.`, `-` で書く。４種類のコマンドは `.`, `-`, `R`, `L` で書く。これは後述のヘルパ関数や表示関数で使う。

**マーク**: テープに書かれるのは 0 か 1 のどちらかなのでenum で定義する。0には `Brank`, 1には `Stroke` という名前で enum `Mark` を定義する。

**テープ**: テープは動作中に左右に伸びうる。注目している部分を Vec で保持し、機械のヘッド位置を そのVec における index で保持する構造にする。Vecへのランダムアクセスはさせないように、引数無しの `scan`, `set` および一つシークする `seek_right`, `seek_left` というメソッドを用意する。`seek_*`の内部実装で Vec の容量が足りない場合は適宜伸ばす。

**機械**: 機械は以下4つを保持する構造となる: 内部状態(型:`State`), 停止判定フラグ(型`bool`), 状態遷移指示一覧(型`Vec<Instr>`), テープ(型:`Tape`) 。機械生成を簡便にするためには、a) 初期テープ状態 b) 状態遷移指示一覧 を簡便に生成する生成関数をそれぞれ定義する(`Tape::from_str`, `Instr::new`)。「停止判定フラグが立つまで ステップ実行する」という while ループを作る（その為、停止しない場合にはCtrl+Cなどで強制終了させる必要がある）。停止した場合には、それが正しい停止かどうかをチェックする（上述『関数と機械の対応』参考。）。この判定は、テープとヘッドのみから判定できるので `Tape` のメソッドとして定義するのが妥当 (cf `check_result`)。

## ソースコード
間違えや、よりよい書き方があれば指摘ください。

```rust
#[derive(Debug, Clone, Copy, PartialEq)]
enum Mark {
    Brank,
    Stroke
}

#[derive(Debug)]
struct Tape {
    value: Vec<Mark>,
    position: usize, // index of head location
}

impl Tape {
    pub fn from_str(s:&str) -> Tape {
        if s == "" { // ensure tape is at least one element
            Tape {
                position: 0,
                value: vec![Mark::Brank],
            }
        } else {
            Tape {
                position: 0,
                value: s.chars().map(|c| if c == '.' { Mark::Brank } else { Mark::Stroke }).collect(),
            }
        }
    }
    pub fn seek_right(&mut self) {
        self.position += 1;
        if self.position == self.value.len() { // tape expansion
            self.value.push(Mark::Brank);
        }
    }
    pub fn seek_left(&mut self) {
        if self.position == 0 {
            self.value.insert(0, Mark::Brank);
            self.position = 0; // just for explnatory
        } else {
            self.position -= 1;
        }
    }
    pub fn scan(&self) -> Mark {
        self.value[self.position].clone()
    }
    pub fn write(&mut self, v:Mark) {
        self.value[self.position] = v;
    }
    pub fn check_result(&self) -> Option<usize> {
        // n: leftmost index of a stroke, m: rightmost index of a stroke
        if let Some(n) = self.value.iter().position(|&x| x == Mark::Stroke) {
            // NG if machine is not located the position n.
            if n != self.position {
                return None
            }
            // NG if more than one blocks of strokes
            let m = self.value.iter().rposition(|&x| x == Mark::Stroke).unwrap();
            if self.value[n..m].iter().any(|&x| x == Mark::Brank) {
                return None
            }
            Some(m-n+1)
        } else { // empty tape
            Some(0)
        }
    }
}

impl std::fmt::Display for Tape {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let s:String = self.value.iter().map(|x| match *x { Mark::Brank => '.', _ => '-' }).collect();
        write!(f, "{} {}", s, self.position)
    }
}

// Machine
#[derive(Debug, Clone, Copy, PartialEq)]
enum Command {
    Erase,
    Print,
    Right,
    Left,
}

#[derive(Debug, Clone, Copy, PartialEq)]
struct State (usize);

#[derive(Debug, Clone, Copy, PartialEq)]
struct Instr (State, Mark, Command, State); // 4-tuple
impl Instr {
    fn new(s0:usize, m:char, c:char, s1:usize) -> Instr {
        Instr(
            State(s0),
            if m == '.' { Mark::Brank } else { Mark::Stroke },
            match c {
                'R' => Command::Right,
                'L' => Command::Left,
                '.' => Command::Erase,
                '-' => Command::Print,
                _ => panic!("invalid command")
            },
            State(s1),
        )
    }
}


#[derive(Debug)]
struct TMachine {
    state: State,
    instr: Vec<Instr>,
    tape: Tape,
    halted: bool,
}

impl TMachine {
    pub fn new(tstr:&str, instr:Vec<Instr>)-> TMachine {
        TMachine {
            state: State(1), // initial state. 1-indexed!
            instr,
            tape: Tape::from_str(tstr),
            halted: false,
        }
    }
    fn step(&mut self, a:Mark) {
        let result = self.instr.iter().find(|&ins| {
            self.state == ins.0 && ins.1 == a
        });
        if let Some(Instr(_,_,c,st))= result {
            match c {
                Command::Erase => self.tape.write(Mark::Brank),
                Command::Print => self.tape.write(Mark::Stroke),
                Command::Right => self.tape.seek_right(),
                Command::Left => self.tape.seek_left(),
            }
            self.state = st.clone();
            // println!("{:?}", self.tape);
        } else {
            self.halted = true;
        }
    }
    pub fn run(&mut self)->Option<usize> {
        while self.halted == false { // may loop forever...
            let mark = self.tape.scan();
            self.step(mark);
        }
        self.tape.check_result()
    }
}

fn constant_3() -> Option<usize> {
    let mut tm = TMachine::new(
        "",
        vec![
            Instr::new(1, '.', '-', 1),
            Instr::new(1, '-', 'L', 2),
            Instr::new(2, '.', '-', 2),
            Instr::new(2, '-', 'L', 3),
            Instr::new(3, '.', '-', 3),        
        ],
    );
    tm.run()
}

fn double(n:usize) -> Option<usize> {
    let mut tm = TMachine::new(
        &"-".repeat(n),
        vec![
            Instr::new(1, '-', 'L', 2),
            Instr::new(2, '.', 'L', 3),
            Instr::new(2, '-', 'L', 3),
            Instr::new(3, '.', '-', 3),
            Instr::new(3, '-', 'L', 4),
            Instr::new(4, '.', '-', 4),
            Instr::new(4, '-', 'R', 5),
            Instr::new(5, '-', 'R', 5),
            Instr::new(5, '.', 'R', 6),
            Instr::new(6, '-', 'R', 6),
            Instr::new(6, '.', 'L', 7),
            Instr::new(7, '-', '.', 7),
            Instr::new(7, '.', 'L', 8),
            Instr::new(8, '-', 'L', 9),
            Instr::new(8, '.', 'L', 11),
            Instr::new(9, '-', 'L', 9),
            Instr::new(9, '.', 'L', 10),
            Instr::new(10, '.', 'R', 2),
            Instr::new(10, '-', 'L', 10),
            Instr::new(11, '-', 'L', 11),
            Instr::new(11, '.', 'R', 12),
        ],
    );
    tm.run()
}

fn parity(n:usize) -> Option<usize> {
    let mut tm = TMachine::new(
        &"-".repeat(n),
        vec![
            Instr::new(1, '-', '.', 2),
            Instr::new(2, '.', 'R', 3),
            Instr::new(3, '-', '.', 4),
            Instr::new(3, '.', '-', 5),
            Instr::new(4, '.', 'R', 1),        
        ],
    );
    tm.run()
}

fn add(n:usize, m:usize) -> Option<usize> {
    let mut tm = TMachine::new(
        &format!("{}{}{}", "-".repeat(n), "." ,"-".repeat(m)),
        vec![
            Instr::new(1, '-', '.', 1),
            Instr::new(1, '.', 'R', 2),
            Instr::new(2, '-', 'R', 2),
            Instr::new(2, '.', '-', 3),
            Instr::new(3, '-', 'L', 3),
            Instr::new(3, '.', 'R', 4),
        ],
    );
    tm.run()
}

fn mult(n:usize, m:usize) -> Option<usize> {
    let mut tm = TMachine::new(
        &format!("{}{}{}", "-".repeat(n), "." ,"-".repeat(m)),
        vec![
            Instr::new(1, '-', '.', 1),
            Instr::new(1, '.', 'R', 2),
            Instr::new(2, '-', 'R', 3),
            Instr::new(2, '.', 'R', 15),
            Instr::new(3, '-', 'R', 3),
            Instr::new(3, '.', 'R', 4),
            Instr::new(4, '.', 'R', 4),
            Instr::new(4, '-', '.', 5),
            Instr::new(5, '.', 'R', 6),
            Instr::new(6, '-', 'R', 7),
            Instr::new(6, '.', '-', 12),
            Instr::new(7, '-', 'R', 7),
            Instr::new(7, '.', 'R', 8),
            Instr::new(8, '-', 'R', 9),
            Instr::new(8, '.', '-', 10),
            Instr::new(9, '-', 'R', 9),
            Instr::new(9, '.', '-', 10),
            Instr::new(10, '-', 'L', 10),
            Instr::new(10, '.', 'L', 11),
            Instr::new(11, '-', 'L', 11),
            Instr::new(11, '.', 'R', 4),
            Instr::new(12, '-', 'L', 13),
            Instr::new(13, '.', 'L', 13),
            Instr::new(13, '-', 'L', 14),
            Instr::new(14, '-', 'L', 14),
            Instr::new(14, '.', 'R', 1),
            Instr::new(15, '.', '-', 16),
            Instr::new(15, '-', 'L', 17),
            Instr::new(16, '-', 'R', 15),
            Instr::new(17, '-', 'L', 17),
            Instr::new(17, '.', 'R', 18),
            ],
    );
    tm.run()
}

fn main() {
    // constant
    assert_eq!(Some(3), constant_3());
    // double & parity
    for i in 1..100 {
        assert_eq!(Some(2*i), double(i));
        assert_eq!(Some(i%2), parity(i));
    }
    // add & mult
    for i in 1..10 {
        for j in 1..10 {
            assert_eq!(Some(i+j), add(i, j));
            assert_eq!(Some(i*j), mult(i, j));
        }
    }
}


```