turing/
turing.rs

1// Copyright 2019 Andrew Thomas Christensen
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the
4// MIT license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option. This file may not be copied,
5// modified, or distributed except according to those terms.
6
7use mode::{Automaton, Family, Mode};
8
9const HEAD : u16 = 8;
10const MASK : u16 = 1 << HEAD;
11
12struct StateFamily;
13
14impl Family for StateFamily {
15    type Base = State;
16    type Mode = State;
17}
18
19#[derive(Copy, Clone, Debug)]
20enum PrintOp { Clear, Print }
21
22#[derive(Copy, Clone, Debug)]
23enum ShiftOp { Left,  Right }
24
25#[derive(Copy, Clone, Debug, Eq, PartialEq)]
26enum State { A, B, C, D, E, H }
27
28impl Mode for State {
29    type Family = StateFamily;
30}
31
32fn step(state : State, tape : &mut u16) -> (State, bool) {
33    use State::*;
34    use PrintOp::*;
35    use ShiftOp::*;
36
37    let bit = (*tape & MASK) >> HEAD;
38
39    let (next, op) =
40        match (state, bit) {
41            (A, 0) => (H, None),
42            (A, 1) => (B, Some((Clear, Right))),
43            (B, 0) => (C, Some((Clear, Right))),
44            (B, 1) => (B, Some((Print, Right))),
45            (C, 0) => (D, Some((Print,  Left))),
46            (C, 1) => (C, Some((Print, Right))),
47            (D, 0) => (E, Some((Clear,  Left))),
48            (D, 1) => (D, Some((Print,  Left))),
49            (E, 0) => (A, Some((Print, Right))),
50            (E, 1) => (E, Some((Print,  Left))),
51            (H, _) => (H, None),
52            (_, _) => unreachable!(),
53        };
54
55    print!("{:016b} {:?} => {:?}, ", *tape, state, next);
56
57    if let Some(op) = op {
58        println!("{:?}, {:?}", op.0, op.1);
59    }
60    else {
61        println!("Halt");
62    }
63
64    if let Some((print_op, shift_op)) = op {
65        match print_op {
66            Print => { *tape = *tape |  (1 << HEAD) },
67            Clear => { *tape = *tape & !(1 << HEAD) },
68        }
69
70        match shift_op {
71            Left  => { *tape = *tape << 1 },
72            Right => { *tape = *tape >> 1 },
73        }
74    }
75
76    // The first tuple element will be interpreted as the next Mode to swap in. The second will become the return value
77    // of the Automaton::next_with_result() function.
78    (next, next != State::H)
79}
80
81fn main() {
82    let mut tape : u16 = 0b111 << HEAD;
83    let mut automaton = StateFamily::automaton_with_mode(State::A);
84
85    // NOTE: We can do this because step() returns false in the "result" parameter if the machine has halted.
86    while Automaton::next_with_result(&mut automaton, |current_state| step(current_state, &mut tape)) { }
87}
turing/turing.rs

turing/
turing.rs
