Struct simple_turing_machine::TuringMachine

pub(crate) struct TuringMachine {
    pub(crate) states: Vec<String>,
    pub(crate) transitions: HashMap<(String, char), (String, char, char)>,
    pub(crate) current_state: String,
    pub(crate) final_states: Vec<String>,
    pub(crate) tape: Vec<char>,
    pub(crate) head_position: usize,
}

Represents a Turing Machine.

This Turing Machine struct consists of a set of states, transitions, a current state, final states, a tape, and a head position.

Fields

states: Vec<String>

The states of the Turing Machine.

transitions: HashMap<(String, char), (String, char, char)>

The transition function of the Turing Machine. Maps a pair of current state and tape character to a tuple containing the next state, the character to write, and the direction to move.

current_state: String

The current state of the Turing Machine.

final_states: Vec<String>

The final (accepting) states of the Turing Machine.

tape: Vec<char>

The tape of the Turing Machine.

head_position: usize

The current position of the tape head.

Implementations

impl TuringMachine

pub(crate) fn new( states: Vec<String>, transitions: HashMap<(String, char), (String, char, char)>, initial_state: String, final_states: Vec<String>, ) -> Self

Creates a new Turing Machine.

Arguments

• states - A vector of strings representing the states of the Turing Machine.
• transitions - A hash map representing the transition function.
• initial_state - The initial state of the Turing Machine.
• final_states - A vector of strings representing the final states.

Returns

A new instance of TuringMachine.

pub(crate) fn step(&mut self) -> bool

Executes a single step of the Turing Machine.

This function checks if the current state is a final state. If it is, the machine halts and returns false. Otherwise, it reads the current symbol under the tape head, finds the corresponding transition, writes the new symbol, moves the tape head, and updates the current state.

Returns

true if the Turing Machine successfully performed a step, or false if it has reached a final state and halted.

Panics

This function will panic if there is no transition defined for the current state and symbol, or if the direction in the transition is not ‘R’ or ‘L’.

pub(crate) fn run(&mut self, input_string: &str) -> String

Runs the Turing Machine with a given input string.

This function initializes the tape with the provided input string, appends a blank symbol at the end, and sets the head position to the start of the tape. It then repeatedly executes steps until the machine halts.

Arguments

• input_string - A string representing the initial input on the tape.

Returns

A String representing the contents of the tape after the machine has halted, with trailing blank symbols removed.

Trait Implementations

impl Clone for TuringMachine

fn clone(&self) -> TuringMachine

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TuringMachine

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.