Framework to create turing machines with binary increment example

Question

I created a way to create turing machines and implemented one that increments a binary number as an example.

This is the turing machine itself:

use std::fmt::{self, Display};

pub struct TuringMachine<'state, TapeItem: Default> {
    tape: Tape<TapeItem>,
    current_state: &'state dyn State<TapeItem>,
}

impl<'state, TapeItem: Default> TuringMachine<'state, TapeItem> {
    pub fn new(
        tape: Tape<TapeItem>,
        initial_state: &'state dyn State<TapeItem>,
    ) -> TuringMachine<TapeItem> {
        Self {
            tape,
            current_state: initial_state,
        }
    }

    // makes progress on the turing machine (updating it) and returns whether an end state was reached
    pub fn update(&mut self) -> bool {
        let (item_replacement, mv, state_replacement, end_state) =
            self.current_state.process(self.tape.get_current());
        if let Some(item) = item_replacement {
            self.tape.replace_current(item);
        }
        if let Some(mv) = mv {
            self.tape.apply_move(mv);
        }
        if let Some(state) = state_replacement {
            self.current_state = state;
        }
        end_state
    }
}

// implements the display trait for tape items which also do. Prints the state on the first line and the tape on the second
impl<'state, TapeItem: Default + Display> Display for TuringMachine<'state, TapeItem> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_fmt(format_args!("{}\n{}", self.current_state, self.tape))
    }
}

// represents the position on a tape either on the right or the left side
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum TapePosition {
    RightSide(usize),
    LeftSide(usize),
}

// represents the tape of the turing machine with a left and a right side
#[derive(Debug, Clone, PartialEq)]
pub struct Tape<TapeItem> {
    pos: TapePosition,
    right: Vec<TapeItem>,
    left: Vec<TapeItem>,
}

impl<TapeItem: Default> Tape<TapeItem> {
    // given a vector of tape items and a start position returns a tape where the items are placed on the right side and the selected item is on the right side at start_pos
    pub fn new(items: Vec<TapeItem>, start_pos: usize) -> Tape<TapeItem> {
        Self {
            pos: TapePosition::RightSide(start_pos),
            right: items,
            left: Vec::new(),
        }
    }

    // returns a reference to the currently selected tape item
    fn get_current(&self) -> &TapeItem {
        match self.pos {
            TapePosition::RightSide(pos) => &self.right[pos],
            TapePosition::LeftSide(pos) => &self.left[pos],
        }
    }

    // replaces the currently selected tape item
    fn replace_current(&mut self, replacement: TapeItem) {
        match self.pos {
            TapePosition::RightSide(pos) => self.right[pos] = replacement,
            TapePosition::LeftSide(pos) => self.left[pos] = replacement,
        }
    }

    // applies a given move to the tape changing the currently selected tape item
    fn apply_move(&mut self, mv: TapeMove) {
        self.pos = match mv {
            TapeMove::Right => {
                match self.pos {
                    // we are on the right side of the tape and want to move further right
                    TapePosition::RightSide(pos) => {
                        // we need to make sure there is enough space for the current item and the next
                        if self.right.len() <= pos + 1 {
                            self.right.resize_with(pos + 2, TapeItem::default);
                        }
                        TapePosition::RightSide(pos + 1)
                    }
                    TapePosition::LeftSide(pos) => {
                        // do we need to change sides?
                        match pos {
                            0 => {
                                // if so we need to make sure the other side has at least two items
                                if self.right.len() <= 1 {
                                    self.right.resize_with(2, TapeItem::default);
                                }
                                TapePosition::RightSide(0)
                            }
                            _ => TapePosition::LeftSide(pos - 1),
                        }
                    }
                }
            }
            // mirrored for the left side
            TapeMove::Left => match self.pos {
                TapePosition::LeftSide(pos) => {
                    if self.left.len() <= pos + 1 {
                        self.left.resize_with(pos + 2, TapeItem::default);
                    }
                    TapePosition::LeftSide(pos + 1)
                }
                TapePosition::RightSide(pos) => match pos {
                    0 => {
                        if self.left.len() <= 1 {
                            self.left.resize_with(2, TapeItem::default);
                        }
                        TapePosition::LeftSide(0)
                    }
                    _ => TapePosition::RightSide(pos - 1),
                },
            },
        }
    }
}

impl<TapeItem: Display> Display for Tape<TapeItem> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> fmt::Result {
        // format the left side of the tape
        if let Some(r) = self
            .left
            .iter()
            .enumerate() // we need the index to tell if this item is selected
            .rev() // since the index of the innermost item is 0 and that of the outermost item the highest, we need to reverse it
            .map(|(i, item)| -> fmt::Result {
                if let TapePosition::LeftSide(pos) = self.pos {
                    if pos == i {
                        // if an item on the left side of the tape is selected and this is that item, mark it with underscores on either site
                        f.write_fmt(format_args!("_{item}_"))
                    } else {
                        item.fmt(f) // otherwise format it normally
                    }
                } else {
                    item.fmt(f) // also if an item on the other site is selected
                }
            })
            .find(|r| r.is_err())
        {
            // find the first error (if any) and return it
            r
        } else {
            // otherwise continue with the right side
            if let Some(r) = self
                .right
                .iter()
                .enumerate()
                .map(|(i, item)| -> fmt::Result {
                    if let TapePosition::RightSide(pos) = self.pos {
                        if pos == i {
                            f.write_fmt(format_args!("_{item}_"))
                        } else {
                            item.fmt(f)
                        }
                    } else {
                        item.fmt(f)
                    }
                })
                .find(|r| r.is_err())
            {
                r
            } else {
                Ok(())
            }
        }
    }
}

// represents a movement of the tape either to the right or the right
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum TapeMove {
    Right,
    Left,
}

// represents a state of the turing machine which may move the tape, change the current item on the tape, change the state and reports whether it transitioned into an end state
// it also needs to implement display
pub trait State<TapeItem>: Display {
    fn process(
        &self,
        item: &TapeItem,
    ) -> (
        Option<TapeItem>,             // optionally replace the current tape item
        Option<TapeMove>,             // optionally move on the tape
        Option<&dyn State<TapeItem>>, // optionally change state
        bool,                         // is this an end state
    );
}

And this is an example for a TM that increments a binary number:

use std::fmt::{self, Display};

pub mod turing_machine;
use crate::turing_machine::{Tape, TuringMachine};
use turing_machine::{State, TapeMove};

fn main() {
    let mut tm = TuringMachine::new(
        Tape::new(
            vec![
                BinaryTapeItem::One,
                BinaryTapeItem::One,
                BinaryTapeItem::One,
            ],
            0,
        ),
        &Q0 {},
    );
    loop {
        println!("{tm}\n");
        if tm.update() {
            // if we reached the end state of the turing machine we are done
            break;
        }
    }
    println!("{tm}");
}

#[derive(Debug, Clone, Copy, PartialEq)]
enum BinaryTapeItem {
    Default,
    One,
    Zero,
}

impl Default for BinaryTapeItem {
    fn default() -> Self {
        BinaryTapeItem::Default
    }
}

impl Display for BinaryTapeItem {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(match self {
            BinaryTapeItem::Default => "?",
            BinaryTapeItem::One => "1",
            BinaryTapeItem::Zero => "0",
        })
    }
}

// image of the implemented turing machine: https://media.geeksforgeeks.org/wp-content/uploads/20200924004938/GFGArticles.png

struct Q0 {}

impl Display for Q0 {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("Q0")
    }
}

impl State<BinaryTapeItem> for Q0 {
    fn process(
        &self,
        item: &BinaryTapeItem,
    ) -> (
        Option<BinaryTapeItem>,             // optionally replace the current tape item
        Option<TapeMove>,                   // optionally move on the tape
        Option<&dyn State<BinaryTapeItem>>, // optionally change state
        bool,                               // is this an end state
    ) {
        match item {
            // 0/0,R
            BinaryTapeItem::Zero => (None, Some(TapeMove::Right), None, false),
            // 1/1,R
            BinaryTapeItem::One => (None, Some(TapeMove::Right), None, false),
            // B/B,L
            BinaryTapeItem::Default => (None, Some(TapeMove::Left), Some(&Q1 {}), false),
        }
    }
}

struct Q1 {}

impl Display for Q1 {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("Q1")
    }
}

impl State<BinaryTapeItem> for Q1 {
    fn process(
        &self,
        item: &BinaryTapeItem,
    ) -> (
        Option<BinaryTapeItem>,             // optionally replace the current tape item
        Option<TapeMove>,                   // optionally move on the tape
        Option<&dyn State<BinaryTapeItem>>, // optionally change state
        bool,                               // is this an end state
    ) {
        match item {
            // 1/0,L
            BinaryTapeItem::One => (
                Some(BinaryTapeItem::Zero),
                Some(TapeMove::Left),
                None,
                false,
            ),
            // B/1,N
            BinaryTapeItem::Default => (Some(BinaryTapeItem::One), None, None, true),
            // 0/1,N
            BinaryTapeItem::Zero => (Some(BinaryTapeItem::One), None, None, true),
        }
    }
}

This is what it outputs:

Q0
_1_11

Q0
1_1_1

Q0
11_1_

Q0
111_?_

Q1
11_1_?

Q1
1_1_0?

Q1
_1_00?

Q1
?_?_000?

Q1
?_1_000?

Answer 1

// represents the position on a tape either on the right or the left side
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum TapePosition {
    RightSide(usize),
    LeftSide(usize),
}

// represents the tape of the turing machine with a left and a right side
#[derive(Debug, Clone, PartialEq)]
pub struct Tape<TapeItem> {
    pos: TapePosition,
    right: Vec<TapeItem>,
    left: Vec<TapeItem>,
}

Your approach to the tape is complicated here by having left and right side of the tape. You've got to handle both cases of TapePosition in a lot of places. Instead, I'd suggest either:

1. Use VecDeque to hold a single tape. You can add onto either end of a VecDeque to grow the tape on either side.

2. Use left and right stacks along with a current item. Move left by popping the left stack and pushing onto the right stack, and move right by popping the right stack and pushing onto the left stack.

Next:

pub trait State<TapeItem>: Display {
    fn process(
        &self,
        item: &TapeItem,
    ) -> (
        Option<TapeItem>,             // optionally replace the current tape item
        Option<TapeMove>,             // optionally move on the tape
        Option<&dyn State<TapeItem>>, // optionally change state
        bool,                         // is this an end state
    );
}

Firstly, I'd suggest defining and returning a struct here rather than a tuple. There's a lot of different parts here without an obvious order, so I think name fields would benefit it.

Secondly, it contains a borrow in the return. Due to Rust's rules, this means that it has to return something with the same lifetime as self. But in practice that would be tricky. You can either return something that is inside the original state (which seems unlikely to be helpful), or something with a static lifetime. In your case, you return constants with a static lifetime.

Your code would be simpler to simply require the 'static lifetime here. Then TuringMachine wouldn't need the special lifetime. However, you'd gain flexibility by return something like a Box instead of a borrow.

However, a rustier solution would be use enums. In particular, rather then defining seperate Q0 and Q1 traits and dynamically dispatching over them in your example, you'd define something like:

enum State {
   Q0,
   Q1,
}

Then you can define your transition rules as a method on State.