5 releases
0.0.4 | Sep 9, 2024 |
---|---|
0.0.3 | Aug 23, 2024 |
0.0.2 | Jul 29, 2024 |
0.0.1 | Jul 23, 2024 |
0.0.0 | Jul 22, 2024 |
#335 in Math
46 downloads per month
160KB
4.5K
SLoC
rstm
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.
Getting Started
From the source
Start by cloning the repository
git clone https://github.com/FL03/rstm.git
cd rstm
cargo build --all-features --workspace
Run an example
cargo run -f F --example {actor}
Usage
Rulesets
To faciliate the creation of rules for the machine, the crate provides a ruleset!
macro. The macro mimics the
structure of the transition function $\delta$ defined by "On topological dynamics of Turing machines" by Petr Kůrka.
$$\delta : Q\times{A}\rarr{Q\times{A}\times{(0, \pm{1})}}$$
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
Rules
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.
Example usage
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),
];
Examples
Executing a program using an Actor
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(())
}
Contributing
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.
Dependencies
~0.7–1.4MB
~31K SLoC