divisibility/
divisibility.rs

1//! In this example for the turingmachine-rs crate a turing machine is created which, when
2//! supplied with two numbers `n` and `k` will determine whether `n` is divisable by `k`.
3//!
4//! Its usage is in the CLI by adding 2 args with numbers:
5//! `cargo run --example divisibility -- 9 6`
6//!
7//! The turing machine starts with a tape in the shape:
8//! ` _ 1^n _ 1^k _ ` and will output:
9//!     - ` _ 1^n _ 1^k _ h _ 1 ` if k is a divisor of n
10//!     - ` _ 1^n _ 1^k _ h _ 0 ` if k is __NOT__ a divisor of n
11//!
12//! here ` _ ` is a empty cell and ` 1^n ` is ` 1 ` repeated n times, and ` h ` is the halt symbol.
13
14use std::{fmt, iter::Cycle};
15use turingmachine_rs::*;
16
17#[derive(Clone, PartialEq)]
18enum Alphabet {
19    StartToken,
20    Delta,
21    One,
22    MarkedOne,
23    Halt,
24}
25
26impl fmt::Display for Alphabet {
27    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
28        use Alphabet::*;
29
30        match self {
31            StartToken => write!(f, "S"),
32            Delta => write!(f, "_"),
33            One => write!(f, "1"),
34            MarkedOne => write!(f, "!"),
35            Halt => write!(f, "h"),
36        }
37    }
38}
39
40#[derive(Debug, Clone, PartialEq)]
41enum States {
42    Start,
43    Started,
44    CycleStart,
45    Found1InDenominator,
46    Found1InNuminator,
47
48    LeftOver,
49    DivByNull,
50    InvalidSyntax,
51}
52
53impl TuringStates<Alphabet> for States {
54    fn step(&self, t: Alphabet) -> (Self, Alphabet, Move) {
55        use Alphabet::*;
56        use States::*;
57
58        match self {
59            Start => match t {
60                Delta => (Started, t, Move::Right),
61                _ => (Start, t, Move::Right),
62            },
63            Started => match t {
64                One => (Started, t, Move::Right),
65                Delta => (CycleStart, t, Move::Stay),
66                _ => (InvalidSyntax, t, Move::Stay),
67            },
68            _ => (InvalidSyntax, t, Move::Stay),
69        }
70    }
71}
72
73fn main() {
74    let n = std::env::args()
75        .nth(1)
76        .expect("No first argument given. Usage: cargo run --example divisibility -- <int> <int>");
77    let k = std::env::args()
78        .nth(2)
79        .expect("No second argument given. Usage: cargo run --example divisibility -- <int> <int>");
80
81    let n = n
82        .parse::<usize>()
83        .expect("First argument is not a positive integer");
84    let k = k
85        .parse::<usize>()
86        .expect("Second argument is not a positive integer");
87
88    println!("n: {}, k: {}", n, k);
89
90    let mut ns = vec![Alphabet::One; n];
91    let mut ks = vec![Alphabet::One; k];
92
93    let mut delta = vec![Alphabet::Delta];
94
95    let mut initial = Vec::new();
96
97    initial.append(&mut delta.clone());
98    initial.append(&mut ns);
99    initial.append(&mut delta.clone());
100    initial.append(&mut ks);
101    initial.append(&mut delta);
102
103    let tape = TuringTape::new(Alphabet::Delta, Alphabet::StartToken, initial);
104    println!("Tape: {}", tape);
105
106    println!("\n\nRunning...\n\n");
107
108    use States::*;
109    let end_state = tape.run_states(Start, vec![CycleStart, InvalidSyntax, DivByNull, LeftOver]);
110
111    println!("Tape: {}", tape);
112    println!("Endstate: {:?}", end_state);
113}
divisibility/divisibility.rs

divisibility/
divisibility.rs
