One of the foundational mathematical constructs behind computer science
is the universal Turing Machine.



(Alan Turing introduced the idea of such a machine in 1936–1937.)

Indeed one way to definitively prove that a language
is turing-complete
is to implement a universal Turing machine in it.



Task

Simulate such a machine capable
of taking the definition of any other Turing machine and executing it.

Of course, you will not have an infinite tape,
but you should emulate this as much as is possible.

The three permissible actions on the tape are "left", "right" and "stay".

To test your universal Turing machine (and prove your programming language
is Turing complete!), you should execute the following two Turing machines
based on the following definitions.


Simple incrementer

 States: q0, qf
 Initial state: q0
 Terminating states: qf
 Permissible symbols: B, 1
 Blank symbol: B
 Rules:
 (q0, 1, 1, right, q0)
 (q0, B, 1, stay, qf)


The input for this machine should be a tape of 1 1 1


Three-state busy beaver

 States: a, b, c, halt
 Initial state: a
 Terminating states: halt
 Permissible symbols: 0, 1
 Blank symbol: 0
 Rules:
 (a, 0, 1, right, b)
 (a, 1, 1, left, c)
 (b, 0, 1, left, a)
 (b, 1, 1, right, b)
 (c, 0, 1, left, b)
 (c, 1, 1, stay, halt)


The input for this machine should be an empty tape.


Bonus:

5-state, 2-symbol probable Busy Beaver machine from Wikipedia

 States: A, B, C, D, E, H
 Initial state: A
 Terminating states: H
 Permissible symbols: 0, 1
 Blank symbol: 0
 Rules:
 (A, 0, 1, right, B)
 (A, 1, 1, left, C)
 (B, 0, 1, right, C)
 (B, 1, 1, right, B)
 (C, 0, 1, right, D)
 (C, 1, 0, left, E)
 (D, 0, 1, left, A)
 (D, 1, 1, left, D)
 (E, 0, 1, stay, H)
 (E, 1, 0, left, A)


The input for this machine should be an empty tape.

This machine runs for more than 47 millions steps.




use std::collections::VecDeque;
use std::fmt::{Display, Formatter, Result};
 
fn main() {
    println!("Simple incrementer");
    let rules_si = vec!(
        Rule::new("q0", '1', '1', Direction::Right, "q0"),
        Rule::new("q0", 'B', '1', Direction::Stay, "qf")
    );
    let states_si = vec!("q0", "qf");
    let terminating_states_si = vec!("qf");
    let permissible_symbols_si = vec!('B', '1');
    let mut tm_si = TM::new(states_si, "q0", terminating_states_si, permissible_symbols_si, 'B', rules_si, "111");
    while !tm_si.is_done() {
        println!("{}", tm_si);
        tm_si.step();
    }
 
    println!("___________________");
    println!("Three-state busy beaver");
    let rules_bb3 = vec!(
        Rule::new("a", '0', '1', Direction::Right, "b"), 
        Rule::new("a", '1', '1', Direction::Left, "c"),
        Rule::new("b", '0', '1', Direction::Left, "a"),
        Rule::new("b", '1', '1', Direction::Right, "b"),
        Rule::new("c", '0', '1', Direction::Left, "b"),
        Rule::new("c", '1', '1', Direction::Stay, "halt"),
    );
    let states_bb3 = vec!("a", "b", "c", "halt");
    let terminating_states_bb3 = vec!("halt");
    let permissible_symbols_bb3 = vec!('0', '1');
    let mut tm_bb3 = TM::new(states_bb3 ,"a", terminating_states_bb3, permissible_symbols_bb3, '0', rules_bb3, "0");
    while !tm_bb3.is_done() {
        println!("{}", tm_bb3);
        tm_bb3.step();
    }
    println!("{}", tm_bb3);
 
    println!("___________________");
    println!("Five-state busy beaver");
    let rules_bb5 = vec!(
        Rule::new("A", '0', '1', Direction::Right, "B"), 
        Rule::new("A", '1', '1', Direction::Left, "C"),
        Rule::new("B", '0', '1', Direction::Right, "C"),
        Rule::new("B", '1', '1', Direction::Right, "B"),
        Rule::new("C", '0', '1', Direction::Right, "D"),
        Rule::new("C", '1', '0', Direction::Left, "E"),
        Rule::new("D", '0', '1', Direction::Left, "A"),
        Rule::new("D", '1', '1', Direction::Left, "D"),
        Rule::new("E", '0', '1', Direction::Stay, "H"),
        Rule::new("E", '1', '0', Direction::Left, "A"),
    );
    let states_bb5 = vec!("A", "B", "C", "D", "E", "H");
    let terminating_states_bb5 = vec!("H");
    let permissible_symbols_bb5 = vec!('0', '1');
    let mut tm_bb5 = TM::new(states_bb5 ,"A", terminating_states_bb5, permissible_symbols_bb5, '0', rules_bb5, "0");
    let mut steps = 0;
    while !tm_bb5.is_done() {
        tm_bb5.step();
        steps += 1;
    }
    println!("Steps: {}", steps);
    println!("Band lenght: {}", tm_bb5.band.len());
}
 
struct TM<'a> {
    state: &'a str,
    terminating_states: Vec<&'a str>,
    rules: Vec<Rule<'a>>,
    band: VecDeque<char>,
    head: usize,
    blank: char,
}
 
struct Rule<'a> {
    state: &'a str,
    read: char,
    write: char,
    dir: Direction,
    new_state: &'a str,
}
 
enum Direction{
    Left,
    Right,
    Stay,
}
 
impl<'a> TM<'a> {
 
    fn new(_states: Vec<&'a str>, initial_state: &'a str, terminating_states: Vec<&'a str>, _permissible_symbols: Vec<char>, blank: char, rules: Vec<Rule<'a>>, input: &str) -> Self {
        Self { state: initial_state, terminating_states, rules, band: input.chars().collect::<VecDeque<_>>(), head: 0, blank }
    }
 
    fn is_done(&self) -> bool {
        self.terminating_states.contains(&self.state)
    }
 
    fn step(&mut self) {
        let field = self.band.get(self.head).unwrap();
        let rule = self.rules.iter().find(|rule| rule.state == self.state && &rule.read == field).unwrap();
        let field = self.band.get_mut(self.head).unwrap();
        *field = rule.write;
        self.state = rule.new_state;
        match rule.dir {
            Direction::Left => {
                if self.head == 0 {
                    self.band.push_front(self.blank)
                } else {
                    self.head -= 1;
                }
            },
            Direction::Right => {
                if self.head == self.band.len() - 1 {
                    self.band.push_back(self.blank)
                }
                self.head += 1;
            },
            Direction::Stay => {},
        }
    }
}
 
impl<'a> Display for TM<'a> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        let band = self.band.iter().enumerate().map(|(i, c)| { 
            if i == self.head {
                format!("[{}]", c)
            } else {
                format!(" {} ", c)
            }
        }).fold(String::new(), |acc, val| acc + &val);
        write!(f, "{}\t{}", self.state, band)
    }
}
 
 
impl<'a> Rule<'a> {
    fn new(state: &'a str, read: char, write: char, dir: Direction, new_state: &'a str) -> Self {
        Self { state, read, write, dir, new_state }
    }
}
 