turing_machine_rs::program

Struct Program

Source 
pub struct Program<S: Symbol> { /* private fields */ }
Expand description

Program is a vector-based struct with a limited API for changing and extending but no API for removing and shrinking. The Program for the Turing machine has a constant size that equals to (STATES.count() - 1) * (ALPHABET.count()).

If you want to extend the program, you can use the Extend::extend method, but you should be sure that this program can accept all these instructions.

§Example

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));
    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(())
}

Implementations§

Source§

impl<S: Symbol> Program<S>

Source

pub fn new(alphabet: Vec<S>, l_state: State) -> Self

Constructs a new Program with the vector Vec<S> and the last state State.

Program has a limited size by definition, so it can only hold (STATES.count() - 1) * (ALPHABET.count()) Instructions.

Examples found in repository?
examples/nice_test.rs (line 13)
11fn main() -> Result<(), String> {
12    let alphabet = vec!['t', 'e', 's', 'n', 'i', 'c', 'e', '_'];
13    let mut program = Program::new(alphabet, State(4));
14    program.extend([
15        (1, 't', 2, 'n', Move::Right),
16        (2, 'e', 3, 'i', Move::Right),
17        (3, 's', 4, 'c', Move::Right),
18        (4, 't', 0, 'e', Move::None),
19        // Revers
20        (1, 'n', 2, 't', Move::Right),
21        (2, 'i', 3, 'e', Move::Right),
22        (3, 'c', 4, 's', Move::Right),
23        (4, 'e', 0, 't', Move::None),
24    ])?;
25    let machine = Classic::new(program, '_')?;
26
27    let test = Tape::from("test");
28    let nice = machine.translate_nrm(test.clone())?;
29    println!(
30        "{} {}!",
31        String::from_iter(nice.as_vec()),
32        String::from_iter(test.as_vec())
33    );
34    Ok(())
35}
More examples
Hide additional examples
examples/binary_addition.rs (line 12)
11fn main() -> Result<(), String> {
12    let mut program = Program::new(vec![' ', '0', '1', '+'], State(8));
13    program.extend([
14        // Sub 1, also init zero check
15        (1, ' ', 0, ' ', Move::None),
16        (1, '0', 1, '0', Move::Left),
17        (1, '1', 2, '0', Move::Right),
18        (1, '+', 6, '+', Move::Right),
19        // Subs part
20        (2, ' ', 3, ' ', Move::Left),
21        (2, '0', 2, '1', Move::Right),
22        // 2, '1' -> Impl
23        // 2, '+' -> Err
24        //
25        // Find + on left
26        // 3, ' ' -> Err
27        (3, '0', 3, '0', Move::Left),
28        (3, '1', 3, '1', Move::Left),
29        (3, '+', 4, '+', Move::Left),
30        // Add 1
31        (4, ' ', 5, '1', Move::Right),
32        (4, '0', 5, '1', Move::Right),
33        (4, '1', 4, '0', Move::Left),
34        // 4, '+' -> Err
35        //
36        // Find + on rigth
37        // 5, ' ' -> Imp
38        (5, '0', 5, '0', Move::Right),
39        (5, '1', 5, '1', Move::Right),
40        (5, '+', 6, '+', Move::Right),
41        // Zero check
42        (6, ' ', 8, ' ', Move::Left),
43        (6, '0', 6, '0', Move::Right),
44        (6, '1', 7, '1', Move::Right),
45        // 6, '+' -> Err
46        //
47        // Find last num
48        (7, ' ', 1, ' ', Move::Left),
49        (7, '0', 7, '0', Move::Right),
50        (7, '1', 7, '1', Move::Right),
51        // 7, '+' -> Err
52        //
53        // Clear + and after
54        // 8, ' ' - Imp
55        (8, '0', 8, ' ', Move::Left),
56        // 8, '1' - Imp
57        (8, '+', 0, ' ', Move::Right),
58    ])?;
59    let machine = Classic::new(program, ' ')?;
60
61    // Change and try to run this example!
62    let lhs = "10101";
63    let rhs = "111";
64    // -----------------------------------
65    let tape = Tape::from(format!("{}+{}", lhs, rhs));
66
67    let res = machine.translate_std(tape)?;
68    println!("{} + {} = {}", lhs, rhs, String::from_iter(res.as_vec()));
69
70    Ok(())
71}
examples/hyper_machine.rs (lines 20-29)
11fn main() -> Result<(), String> {
12    use nrm_machines::*;
13
14    let stand = new_stand_machine();
15    let zerofy = new_zerofy_machine();
16    let l_shift = new_left_shift_machine();
17    let r_shift = new_right_shift_machine();
18    let trans = new_trans_machine();
19
20    let mut program = Program::new(
21        vec![
22            stand.clone(),
23            zerofy.clone(),
24            l_shift.clone(),
25            r_shift.clone(),
26            trans.clone(),
27        ],
28        State(9),
29    );
30    // This is simplest implementation of `change choose second to choose third` machine
31    program.extend([
32        // Find l_shift
33        (1, r_shift.clone(), 1, r_shift.clone(), Move::Right),
34        (1, trans.clone(), 1, trans.clone(), Move::Right),
35        (1, zerofy.clone(), 1, zerofy.clone(), Move::Right),
36        (1, l_shift.clone(), 2, stand.clone(), Move::Left),
37        // Clear until r_shift
38        (2, zerofy.clone(), 2, stand.clone(), Move::Left),
39        (2, trans.clone(), 2, stand.clone(), Move::Left),
40        (2, r_shift.clone(), 3, r_shift.clone(), Move::Right),
41        //
42        // Set second r_shift
43        (3, stand.clone(), 4, r_shift.clone(), Move::Right),
44        // Set first trans
45        (4, stand.clone(), 5, trans.clone(), Move::Right),
46        // Set first zerofy
47        (5, stand.clone(), 6, zerofy.clone(), Move::Right),
48        // Set first l_shift
49        (6, stand.clone(), 7, l_shift.clone(), Move::Right),
50        // Set second trans
51        (7, stand.clone(), 8, trans.clone(), Move::Right),
52        // Set second zerofy
53        (8, stand.clone(), 9, zerofy.clone(), Move::Right),
54        // Set second l_shift and stop execution
55        (9, stand.clone(), 0, l_shift.clone(), Move::None),
56    ])?;
57
58    let hyper_machine = Classic::new(program, stand.clone())?;
59    let choose_second = Tape::new([
60        r_shift.clone(),
61        trans.clone(),
62        zerofy.clone(),
63        l_shift.clone(),
64    ]);
65    let result_choose_third = hyper_machine.translate_nrm(choose_second)?;
66
67    let expected_choose_third = Tape::new([
68        r_shift.clone(),
69        r_shift.clone(),
70        trans.clone(),
71        zerofy.clone(),
72        l_shift.clone(),
73        trans.clone(),
74        zerofy.clone(),
75        l_shift.clone(),
76    ]);
77
78    assert_eq!(expected_choose_third, result_choose_third);
79    println!("If you're reading this, hyper machine successful transform choose second machine");
80
81    let tape = Tape::from("0101101110");
82    let mut conf = Configuration::new_nrm(tape.clone())?;
83    for machine in result_choose_third.as_vec() {
84        conf = machine.execute(conf).unwrap();
85        conf.state = State(1)
86    }
87    println!(
88        "Choose third machine translate {} into {}",
89        String::from_iter(tape.as_vec()),
90        String::from_iter(conf.tape().as_vec())
91    );
92
93    Ok(())
94}
95
96// This module just contains several nrm machines
97mod nrm_machines {
98    use super::*;
99
100    pub fn new_stand_machine() -> Classic<char> {
101        let mut program = Program::new(vec!['0', '1'], State(1));
102        program
103            .extend([(1, '0', 0, '0', Move::None), (1, '1', 0, '1', Move::None)])
104            .unwrap();
105        Classic::new(program, '0').unwrap()
106    }
107
108    pub fn new_zerofy_machine() -> Classic<char> {
109        let mut program = Program::new(vec!['0', '1'], State(4));
110        program
111            .extend([
112                (1, '0', 2, '0', Move::Right),
113                (2, '0', 3, '0', Move::Left),
114                (2, '1', 2, '1', Move::Right),
115                (3, '0', 0, '0', Move::None),
116                (3, '1', 4, '0', Move::None),
117                (4, '0', 3, '0', Move::Left),
118            ])
119            .unwrap();
120        Classic::new(program, '0').unwrap()
121    }
122
123    pub fn new_left_shift_machine() -> Classic<char> {
124        let mut program = Program::new(vec!['0', '1'], State(2));
125        program
126            .extend([
127                (1, '0', 2, '0', Move::Left),
128                (2, '0', 0, '0', Move::None),
129                (2, '1', 2, '1', Move::Left),
130            ])
131            .unwrap();
132        Classic::new(program, '0').unwrap()
133    }
134
135    pub fn new_right_shift_machine() -> Classic<char> {
136        let mut program = Program::new(vec!['0', '1'], State(2));
137        program
138            .extend([
139                (1, '0', 2, '0', Move::Right),
140                (2, '0', 0, '0', Move::None),
141                (2, '1', 2, '1', Move::Right),
142            ])
143            .unwrap();
144        Classic::new(program, '0').unwrap()
145    }
146
147    pub fn new_trans_machine() -> Classic<char> {
148        let mut program = Program::new(vec!['0', '1'], State(19));
149        program
150            .extend([
151                (1, '0', 2, '0', Move::Right),
152                (2, '0', 3, '0', Move::None),
153                (2, '1', 2, '1', Move::Right),
154                (3, '0', 4, '0', Move::Left),
155                (4, '0', 7, '0', Move::None),
156                (4, '1', 5, '0', Move::None),
157                (5, '0', 6, '0', Move::Left),
158                (6, '0', 7, '1', Move::None),
159                (6, '1', 6, '1', Move::Left),
160                (7, '0', 16, '1', Move::None),
161                (7, '1', 8, '1', Move::Left),
162                (8, '0', 18, '0', Move::Right),
163                (8, '1', 9, '0', Move::None),
164                (9, '0', 10, '0', Move::Right),
165                (10, '0', 11, '1', Move::None),
166                (10, '1', 10, '1', Move::Right),
167                (11, '1', 12, '1', Move::Left),
168                (12, '1', 13, '0', Move::None),
169                (13, '0', 14, '0', Move::Left),
170                (14, '0', 15, '1', Move::None),
171                (14, '1', 14, '1', Move::Left),
172                (15, '0', 7, '0', Move::None),
173                (15, '1', 7, '1', Move::None),
174                (16, '1', 17, '1', Move::Left),
175                (17, '0', 19, '0', Move::Right),
176                (17, '1', 15, '0', Move::None),
177                (18, '0', 0, '0', Move::None),
178                (18, '1', 18, '1', Move::Right),
179                (19, '1', 0, '0', Move::None),
180            ])
181            .unwrap();
182        Classic::new(program, '0').unwrap()
183    }
Source

pub fn alphabet(&self) -> &Vec<S>

Returns an Vec alphabet reference.

Zero cost method.

Source

pub fn get(&self, head: &Head<S>) -> Result<Option<&Instruction<S>>, String>

Returns [Ok(Some)] when Head is in the program, [Ok(None)] when Head is not in the program and [Err(String)] when Head State is large then the Program last state.

Source

pub fn l_state(&self) -> State

Returns State the program last state.

Source

pub fn insert( &mut self, inst: Instruction<S>, ) -> Result<Option<Instruction<S>>, String>

Inserts Instruction in the Program.

Returns [Err(String)] when Head State equals to 0, Head or [Tail] symbols are not in the Program alphabet or the Program last state is less then Head or crate::instruction::Tail states.

Otherwise returns another [Ok(Some(Instruction))] when the Head already is in the Program and set inserting Instruction or [Ok(None)] when the Instruction is not in the Program.

The Option is very useful in the collision check.

Trait Implementations§

Source§

impl<S: Clone + Symbol> Clone for Program<S>

Source§

fn clone(&self) -> Program<S>

Returns a duplicate of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<S: Debug + Symbol> Debug for Program<S>

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<S: Symbol> Display for Program<S>

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<S: Symbol, I> Extend<I> for Program<S>
where I: IntoIterator<Item = (usize, S, usize, S, Move)>,

Source§

fn extend(&mut self, iterable: I) -> Result<(), String>

Extends the Program by tuples of (usize, Symbol, usize, Symbol, Move) the first two elements are going to Head and the last three are going to crate::instruction::Tail.

Returns [Ok(())] when the Program is extended successfully and the [Err(String)] otherwise.

§Warning

When the Instruction can be inserted into the Program the extending interrupt.

Source§

impl<S: PartialEq + Symbol> PartialEq for Program<S>

Source§

fn eq(&self, other: &Program<S>) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl<S: Symbol> With<Program<S>> for Program<S>

Source§

fn with(&self, other: &Program<S>) -> Result<Program<S>, String>

Returns a new Program by merging this program with another according to these rules:

  1. All crate::instruction::Tail parts of Instructions for this Program will changes their States to self.l_state if crate::instruction::Tail State equals to 0.
  2. All Head parts of Instructions for another Program will increase (or shift) their States by self.l_state.
  3. All crate::instruction::Tail parts of Instructions for another program will also increase (or shift) by self.l_state but only if crate::instruction::Tail State not equals to 0.
  4. A new Program l_state is set to self.l_state + other.l_state.
Source§

type Output = Result<Program<S>, String>

Output type may have several variantions accoriding to the needs.
Source§

impl<S: Eq + Symbol> Eq for Program<S>

Source§

impl<S: Symbol> StructuralPartialEq for Program<S>

Auto Trait Implementations§

§

impl<S> Freeze for Program<S>

§

impl<S> RefUnwindSafe for Program<S>
where S: RefUnwindSafe,

§

impl<S> Send for Program<S>
where S: Send,

§

impl<S> Sync for Program<S>
where S: Sync,

§

impl<S> Unpin for Program<S>
where S: Unpin,

§

impl<S> UnwindSafe for Program<S>
where S: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T> ToString for T
where T: Display + ?Sized,

Source§

fn to_string(&self) -> String

Converts the given value to a String. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
Source§

impl<T> Symbol for T
where T: Clone + Debug + Display + Eq + PartialEq,