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?