The library is currently in the early stages of development and is still settling in on a feel for the api.
Welcome to rstm
! This crate provides a simple and easy-to-use interface for creating and executing Turing machines. The crate is designed to be flexible and extensible, allowing developers to create and execute a wide range of Turing machines. Furthermore, the crate focuses on efficiency and leverages feature-gating to reduce overhead.
Start by cloning the repository
git clone https://github.com/FL03/rstm.git
cd rstm
cargo build --all-features --workspace
cargo run -f F --example {actor}
To faciliate the creation of rules for the machine, the crate provides a ruleset!
macro. The macro mimics the
structure of the transition function
The syntax of the macro is as follows:
ruleset![
(state, symbol) -> Direction(next_state, next_symbol),
...
]
The macro expands into a Vec<Rule>
where Rule
is structure consisting of two other structures, namely: Head<Q, S>
and the Tail<Q, S>
. Each of these structures is a direct representation of the two sides of the transition function defined above
pub struct Rule<Q, S> {
pub head: Head<Q, S>,
pub tail: Tail<Q, S>,
}
where Head
and Tail
are defined as follows:
pub struct Head<Q, S> {
pub state: Q,
pub symbol: S,
}
pub struct Tail<Q, S> {
pub direction: Direction,
pub state: Q,
pub symbol: S,
}
Note: the macro is hygenic, meaning developers will not need to import the Direction
enum nor its variants in order to use the macro.
The following example demonstrates the use of the ruleset!
macro to define a set of rules for a three-state, two-symbol Turing machine.
use rstm::ruleset;
// define the ruleset for the machine
let rules = ruleset![
(0, 0) -> Right(1, 0),
(0, 1) -> Stay(-1, 1),
(1, 0) -> Left(0, 1),
(1, 1) -> Right(-1, 0),
(-1, 0) -> Right(0, 0),
(-1, 1) -> Right(1, 1),
];
extern crate rstm;
use rstm::{ruleset, Actor, Program, State};
fn main() -> Result<(), Box<dyn std::error::Error>> {
tracing_subscriber::fmt().with_target(false).init();
// initialize the tape data
let alpha = vec![0u8; 10];
// initialize the state of the machine
let initial_state = State::<isize>::default();
// define the ruleset for the machine
let rules = ruleset![
(0, 0) -> Right(1, 0),
(0, 1) -> Right(-1, 1),
(1, 0) -> Right(0, 1),
(1, 1) -> Right(-1, 0),
(-1, 0) -> Left(0, 0),
(-1, 1) -> Left(1, 1),
];
// create a new program from the ruleset
let program = Program::from_iter(rules);
// create a new instance of the machine
let tm = dbg!(Actor::new(alpha, initial_state, 0));
// execute the program
tm.execute(program).run()?;
Ok(())
}
Pull requests are welcome. Any improvements or modifactions should first be disccussed using a pull-request and/or by opening an issue. Additionally, please make sure to update tests as appropriate and to adhear to the feature gates.