turing_machine_rs/
turing.rs

1use crate::instruction::State;
2use crate::state::{Configuration, Tape};
3use crate::Symbol;
4
5/// Provides ability to execute [`crate::state::Configuration`]s and translate
6/// [`crate::state::Tape`]s.
7///
8/// Most of the methods can be implement through the [`TuringMachine::execute_once`]
9/// and [`TuringMachine::execute_until`] methods.
10///
11/// Most important trait.
12///
13/// # Examples
14/// ```rust
15/// extern crate turing_machine_rs;
16///
17/// use turing_machine_rs::instruction::{Move, State};
18/// use turing_machine_rs::machines::Classic;
19/// use turing_machine_rs::program::{Extend, Program};
20/// use turing_machine_rs::state::Tape;
21/// use turing_machine_rs::TuringMachine;
22///
23/// fn main() -> Result<(), String> {
24///    let alphabet = vec!['t', 'e', 's', 'n', 'i', 'c', 'e', '_'];
25///    let mut program = Program::new(alphabet, State(4));
26///     // Trait for more comfortable coding
27///     program.extend([
28///         // Instruction consists of Head and Tail parts
29///         // Head state, Head symbol, Tail state, Tail symbol, Tail Move
30///         (1, 't', 2, 'n', Move::Right),
31///         (2, 'e', 3, 'i', Move::Right),
32///         (3, 's', 4, 'c', Move::Right),
33///         (4, 't', 0, 'e', Move::None),
34///         // Revers
35///         (1, 'n', 2, 't', Move::Right),
36///         (2, 'i', 3, 'e', Move::Right),
37///         (3, 'c', 4, 's', Move::Right),
38///         (4, 'e', 0, 't', Move::None),
39///     ])?;
40///     let machine = Classic::new(program, '_')?;
41///
42///     let test = Tape::from("test");
43///     let nice = machine.translate_nrm(test.clone())?;
44///     println!(
45///         "{} {}!",
46///         String::from_iter(nice.as_vec()),
47///         String::from_iter(test.as_vec())
48///     );
49///     Ok(())
50/// }
51/// ```
52pub trait TuringMachine<S: Symbol> {
53    /// Executes the [`crate::program::Program`] and returns a mutated [`Configuration`]
54    /// using the [`TuringMachine::execute_until`] method with the `conf.state == 0`
55    /// predicate. This is the most commonly used method for [`crate::program::Program`] execution.
56    fn execute(&self, conf: Configuration<S>) -> Result<Configuration<S>, String> {
57        self.execute_until(conf, |conf| conf.state == State(0))
58    }
59
60    /// A Turing machine must have the ability to execute [`crate::program::Program`]
61    /// and change the [`Configuration`] once. This is important for machines,
62    /// and its realization can vary depending on machine type.
63    fn execute_once(&self, conf: Configuration<S>) -> Result<Configuration<S>, String>;
64
65    /// Executes program untill stop predicate equals to `false` and returns
66    /// a mutated [`Configuration`].
67    ///
68    /// # Examples
69    /// ```rust
70    /// use turing_machine_rs::instruction::{Move, State};
71    /// use turing_machine_rs::machines::Classic;
72    /// use turing_machine_rs::program::{Extend, Program};
73    /// use turing_machine_rs::state::{Configuration, Tape};
74    /// use turing_machine_rs::TuringMachine;
75    ///
76    /// fn main() -> Result<(), String> {
77    ///     let mut program = Program::new(vec!['0', '1'], State(3));
78    ///     program.extend([
79    ///         (1, '0', 2, '0', Move::Right),
80    ///         (1, '1', 1, '1', Move::Left),
81    ///         (2, '0', 3, '1', Move::Left),
82    ///         (2, '1', 2, '1', Move::Right),
83    ///         (3, '0', 0, '0', Move::None),
84    ///         (3, '1', 3, '0', Move::Left),
85    ///     ])?;
86    ///     let machine = Classic::new(program, '0')?;
87    ///
88    ///     let conf = Configuration::new_std(Tape::from("010"))?;
89    ///     let result = machine.execute_until(conf, |conf| conf.state == State(3))?;
90    ///
91    ///     let expected = Configuration::new(Tape::from("0101"), 2, State(3))?;
92    ///     assert_eq!(expected, result);
93    ///
94    ///     Ok(())
95    /// }
96    /// ```
97    fn execute_until(
98        &self,
99        conf: Configuration<S>,
100        until: impl Fn(&Configuration<S>) -> bool,
101    ) -> Result<Configuration<S>, String>;
102
103    /// Translates and returns a mutated [`Tape`] using the [`TuringMachine::execute`]
104    /// method as the [`Configuration::new_std`].
105    fn translate_std(&self, tape: Tape<S>) -> Result<Tape<S>, String> {
106        let conf = Configuration::new_std(tape)?;
107        let exec = self.execute(conf)?;
108        Ok(exec.into_tape())
109    }
110
111    /// Translates and returns a mutated [`Tape`] using the [`TuringMachine::execute`]
112    /// method as the [`Configuration::new_nrm`].
113    fn translate_nrm(&self, tape: Tape<S>) -> Result<Tape<S>, String> {
114        let conf = Configuration::new_nrm(tape)?;
115        let exec = self.execute(conf)?;
116        Ok(exec.into_tape())
117    }
118}
turing_machine_rs/turing.rs

turing_machine_rs/
turing.rs
