Trait TuringMachine 

pub trait TuringMachine<S: Symbol> {
    // Required methods
    fn execute_once(
        &self,
        conf: Configuration<S>,
    ) -> Result<Configuration<S>, String>;
    fn execute_until(
        &self,
        conf: Configuration<S>,
        until: impl Fn(&Configuration<S>) -> bool,
    ) -> Result<Configuration<S>, String>;

    // Provided methods
    fn execute(
        &self,
        conf: Configuration<S>,
    ) -> Result<Configuration<S>, String> { ... }
    fn translate_std(&self, tape: Tape<S>) -> Result<Tape<S>, String> { ... }
    fn translate_nrm(&self, tape: Tape<S>) -> Result<Tape<S>, String> { ... }
}

Provides ability to execute crate::state::Configurations and translate crate::state::Tapes.

Most of the methods can be implement through the TuringMachine::execute_once and TuringMachine::execute_until methods.

Most important trait.

Examples

extern crate turing_machine_rs;

use turing_machine_rs::instruction::{Move, State};
use turing_machine_rs::machines::Classic;
use turing_machine_rs::program::{Extend, Program};
use turing_machine_rs::state::Tape;
use turing_machine_rs::TuringMachine;

fn main() -> Result<(), String> {
   let alphabet = vec!['t', 'e', 's', 'n', 'i', 'c', 'e', '_'];
   let mut program = Program::new(alphabet, State(4));
    // Trait for more comfortable coding
    program.extend([
        // Instruction consists of Head and Tail parts
        // Head state, Head symbol, Tail state, Tail symbol, Tail Move
        (1, 't', 2, 'n', Move::Right),
        (2, 'e', 3, 'i', Move::Right),
        (3, 's', 4, 'c', Move::Right),
        (4, 't', 0, 'e', Move::None),
        // Revers
        (1, 'n', 2, 't', Move::Right),
        (2, 'i', 3, 'e', Move::Right),
        (3, 'c', 4, 's', Move::Right),
        (4, 'e', 0, 't', Move::None),
    ])?;
    let machine = Classic::new(program, '_')?;

    let test = Tape::from("test");
    let nice = machine.translate_nrm(test.clone())?;
    println!(
        "{} {}!",
        String::from_iter(nice.as_vec()),
        String::from_iter(test.as_vec())
    );
    Ok(())
}

Required Methods

fn execute_once( &self, conf: Configuration<S>, ) -> Result<Configuration<S>, String>

A Turing machine must have the ability to execute crate::program::Program and change the Configuration once. This is important for machines, and its realization can vary depending on machine type.

fn execute_until( &self, conf: Configuration<S>, until: impl Fn(&Configuration<S>) -> bool, ) -> Result<Configuration<S>, String>

Executes program untill stop predicate equals to false and returns a mutated Configuration.

Examples

use turing_machine_rs::instruction::{Move, State};
use turing_machine_rs::machines::Classic;
use turing_machine_rs::program::{Extend, Program};
use turing_machine_rs::state::{Configuration, Tape};
use turing_machine_rs::TuringMachine;

fn main() -> Result<(), String> {
    let mut program = Program::new(vec!['0', '1'], State(3));
    program.extend([
        (1, '0', 2, '0', Move::Right),
        (1, '1', 1, '1', Move::Left),
        (2, '0', 3, '1', Move::Left),
        (2, '1', 2, '1', Move::Right),
        (3, '0', 0, '0', Move::None),
        (3, '1', 3, '0', Move::Left),
    ])?;
    let machine = Classic::new(program, '0')?;

    let conf = Configuration::new_std(Tape::from("010"))?;
    let result = machine.execute_until(conf, |conf| conf.state == State(3))?;

    let expected = Configuration::new(Tape::from("0101"), 2, State(3))?;
    assert_eq!(expected, result);

    Ok(())
}

Provided Methods

fn execute(&self, conf: Configuration<S>) -> Result<Configuration<S>, String>

Executes the crate::program::Program and returns a mutated Configuration using the TuringMachine::execute_until method with the conf.state == 0 predicate. This is the most commonly used method for crate::program::Program execution.

Examples found in repository

examples/hyper_machine.rs (line 84)

fn main() -> Result<(), String> {
    use nrm_machines::*;

    let stand = new_stand_machine();
    let zerofy = new_zerofy_machine();
    let l_shift = new_left_shift_machine();
    let r_shift = new_right_shift_machine();
    let trans = new_trans_machine();

    let mut program = Program::new(
        vec![
            stand.clone(),
            zerofy.clone(),
            l_shift.clone(),
            r_shift.clone(),
            trans.clone(),
        ],
        State(9),
    );
    // This is simplest implementation of `change choose second to choose third` machine
    program.extend([
        // Find l_shift
        (1, r_shift.clone(), 1, r_shift.clone(), Move::Right),
        (1, trans.clone(), 1, trans.clone(), Move::Right),
        (1, zerofy.clone(), 1, zerofy.clone(), Move::Right),
        (1, l_shift.clone(), 2, stand.clone(), Move::Left),
        // Clear until r_shift
        (2, zerofy.clone(), 2, stand.clone(), Move::Left),
        (2, trans.clone(), 2, stand.clone(), Move::Left),
        (2, r_shift.clone(), 3, r_shift.clone(), Move::Right),
        //
        // Set second r_shift
        (3, stand.clone(), 4, r_shift.clone(), Move::Right),
        // Set first trans
        (4, stand.clone(), 5, trans.clone(), Move::Right),
        // Set first zerofy
        (5, stand.clone(), 6, zerofy.clone(), Move::Right),
        // Set first l_shift
        (6, stand.clone(), 7, l_shift.clone(), Move::Right),
        // Set second trans
        (7, stand.clone(), 8, trans.clone(), Move::Right),
        // Set second zerofy
        (8, stand.clone(), 9, zerofy.clone(), Move::Right),
        // Set second l_shift and stop execution
        (9, stand.clone(), 0, l_shift.clone(), Move::None),
    ])?;

    let hyper_machine = Classic::new(program, stand.clone())?;
    let choose_second = Tape::new([
        r_shift.clone(),
        trans.clone(),
        zerofy.clone(),
        l_shift.clone(),
    ]);
    let result_choose_third = hyper_machine.translate_nrm(choose_second)?;

    let expected_choose_third = Tape::new([
        r_shift.clone(),
        r_shift.clone(),
        trans.clone(),
        zerofy.clone(),
        l_shift.clone(),
        trans.clone(),
        zerofy.clone(),
        l_shift.clone(),
    ]);

    assert_eq!(expected_choose_third, result_choose_third);
    println!("If you're reading this, hyper machine successful transform choose second machine");

    let tape = Tape::from("0101101110");
    let mut conf = Configuration::new_nrm(tape.clone())?;
    for machine in result_choose_third.as_vec() {
        conf = machine.execute(conf).unwrap();
        conf.state = State(1)
    }
    println!(
        "Choose third machine translate {} into {}",
        String::from_iter(tape.as_vec()),
        String::from_iter(conf.tape().as_vec())
    );

    Ok(())
}

fn translate_std(&self, tape: Tape<S>) -> Result<Tape<S>, String>

Translates and returns a mutated Tape using the TuringMachine::execute method as the Configuration::new_std.

Examples found in repository

examples/binary_addition.rs (line 67)

fn main() -> Result<(), String> {
    let mut program = Program::new(vec![' ', '0', '1', '+'], State(8));
    program.extend([
        // Sub 1, also init zero check
        (1, ' ', 0, ' ', Move::None),
        (1, '0', 1, '0', Move::Left),
        (1, '1', 2, '0', Move::Right),
        (1, '+', 6, '+', Move::Right),
        // Subs part
        (2, ' ', 3, ' ', Move::Left),
        (2, '0', 2, '1', Move::Right),
        // 2, '1' -> Impl
        // 2, '+' -> Err
        //
        // Find + on left
        // 3, ' ' -> Err
        (3, '0', 3, '0', Move::Left),
        (3, '1', 3, '1', Move::Left),
        (3, '+', 4, '+', Move::Left),
        // Add 1
        (4, ' ', 5, '1', Move::Right),
        (4, '0', 5, '1', Move::Right),
        (4, '1', 4, '0', Move::Left),
        // 4, '+' -> Err
        //
        // Find + on rigth
        // 5, ' ' -> Imp
        (5, '0', 5, '0', Move::Right),
        (5, '1', 5, '1', Move::Right),
        (5, '+', 6, '+', Move::Right),
        // Zero check
        (6, ' ', 8, ' ', Move::Left),
        (6, '0', 6, '0', Move::Right),
        (6, '1', 7, '1', Move::Right),
        // 6, '+' -> Err
        //
        // Find last num
        (7, ' ', 1, ' ', Move::Left),
        (7, '0', 7, '0', Move::Right),
        (7, '1', 7, '1', Move::Right),
        // 7, '+' -> Err
        //
        // Clear + and after
        // 8, ' ' - Imp
        (8, '0', 8, ' ', Move::Left),
        // 8, '1' - Imp
        (8, '+', 0, ' ', Move::Right),
    ])?;
    let machine = Classic::new(program, ' ')?;

    // Change and try to run this example!
    let lhs = "10101";
    let rhs = "111";
    // -----------------------------------
    let tape = Tape::from(format!("{}+{}", lhs, rhs));

    let res = machine.translate_std(tape)?;
    println!("{} + {} = {}", lhs, rhs, String::from_iter(res.as_vec()));

    Ok(())
}

fn translate_nrm(&self, tape: Tape<S>) -> Result<Tape<S>, String>

Translates and returns a mutated Tape using the TuringMachine::execute method as the Configuration::new_nrm.

Examples found in repository

examples/nice_test.rs (line 28)

fn main() -> Result<(), String> {
    let alphabet = vec!['t', 'e', 's', 'n', 'i', 'c', 'e', '_'];
    let mut program = Program::new(alphabet, State(4));
    program.extend([
        (1, 't', 2, 'n', Move::Right),
        (2, 'e', 3, 'i', Move::Right),
        (3, 's', 4, 'c', Move::Right),
        (4, 't', 0, 'e', Move::None),
        // Revers
        (1, 'n', 2, 't', Move::Right),
        (2, 'i', 3, 'e', Move::Right),
        (3, 'c', 4, 's', Move::Right),
        (4, 'e', 0, 't', Move::None),
    ])?;
    let machine = Classic::new(program, '_')?;

    let test = Tape::from("test");
    let nice = machine.translate_nrm(test.clone())?;
    println!(
        "{} {}!",
        String::from_iter(nice.as_vec()),
        String::from_iter(test.as_vec())
    );
    Ok(())
}

examples/hyper_machine.rs (line 65)

fn main() -> Result<(), String> {
    use nrm_machines::*;

    let stand = new_stand_machine();
    let zerofy = new_zerofy_machine();
    let l_shift = new_left_shift_machine();
    let r_shift = new_right_shift_machine();
    let trans = new_trans_machine();

    let mut program = Program::new(
        vec![
            stand.clone(),
            zerofy.clone(),
            l_shift.clone(),
            r_shift.clone(),
            trans.clone(),
        ],
        State(9),
    );
    // This is simplest implementation of `change choose second to choose third` machine
    program.extend([
        // Find l_shift
        (1, r_shift.clone(), 1, r_shift.clone(), Move::Right),
        (1, trans.clone(), 1, trans.clone(), Move::Right),
        (1, zerofy.clone(), 1, zerofy.clone(), Move::Right),
        (1, l_shift.clone(), 2, stand.clone(), Move::Left),
        // Clear until r_shift
        (2, zerofy.clone(), 2, stand.clone(), Move::Left),
        (2, trans.clone(), 2, stand.clone(), Move::Left),
        (2, r_shift.clone(), 3, r_shift.clone(), Move::Right),
        //
        // Set second r_shift
        (3, stand.clone(), 4, r_shift.clone(), Move::Right),
        // Set first trans
        (4, stand.clone(), 5, trans.clone(), Move::Right),
        // Set first zerofy
        (5, stand.clone(), 6, zerofy.clone(), Move::Right),
        // Set first l_shift
        (6, stand.clone(), 7, l_shift.clone(), Move::Right),
        // Set second trans
        (7, stand.clone(), 8, trans.clone(), Move::Right),
        // Set second zerofy
        (8, stand.clone(), 9, zerofy.clone(), Move::Right),
        // Set second l_shift and stop execution
        (9, stand.clone(), 0, l_shift.clone(), Move::None),
    ])?;

    let hyper_machine = Classic::new(program, stand.clone())?;
    let choose_second = Tape::new([
        r_shift.clone(),
        trans.clone(),
        zerofy.clone(),
        l_shift.clone(),
    ]);
    let result_choose_third = hyper_machine.translate_nrm(choose_second)?;

    let expected_choose_third = Tape::new([
        r_shift.clone(),
        r_shift.clone(),
        trans.clone(),
        zerofy.clone(),
        l_shift.clone(),
        trans.clone(),
        zerofy.clone(),
        l_shift.clone(),
    ]);

    assert_eq!(expected_choose_third, result_choose_third);
    println!("If you're reading this, hyper machine successful transform choose second machine");

    let tape = Tape::from("0101101110");
    let mut conf = Configuration::new_nrm(tape.clone())?;
    for machine in result_choose_third.as_vec() {
        conf = machine.execute(conf).unwrap();
        conf.state = State(1)
    }
    println!(
        "Choose third machine translate {} into {}",
        String::from_iter(tape.as_vec()),
        String::from_iter(conf.tape().as_vec())
    );

    Ok(())
}

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<Machine, S: Symbol> TuringMachine<S> for Debugger<Machine, S>

where Machine: TuringMachine<S>,

impl<S: Symbol> TuringMachine<S> for Classic<S>