Crate rstm 

rstm

rstm is a Rust library dedicated to the construction and execution of Turing Machines. The crate is designed to be flexible and easy to use while preserving the abstract nature of the models.

Features

The crate employs the use of various feature flags for modularity and to keep the core lightweight.

Overview

The core of the library is built around the concept of a Turing Machine, which consists of a tape, a head that reads and writes symbols on the tape, and a set of rules that dictate the machine’s behavior. The library provides a set of abstractions and utilities to define and manipulate these components.

Examples

For more examples, please refer to the examples directory in the repository.

Creating and executing a simple Turing Machine with a Moving Head

   use rstm::prelude::{Program, TMH};

   fn main() -> rstm::Result<()> {
       // initialize the logger
       tracing_subscriber::fmt()
           .with_max_level(tracing::Level::DEBUG)
           .with_target(false)
           .with_timer(tracing_subscriber::fmt::time::uptime())
           .init();
       tracing::info!("Welcome to rstm!");
       // define some input for the machine
       let input = [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0];
      // initialize the state of the machine
       let initial_state: isize = 0;
       // define the ruleset for the machine
       let program: Program<isize, usize> = rstm::program! {
           #[default_state(initial_state)]
           rules: {
               (0, 0) -> Right(1, 0);
               (0, 1) -> Left(-1, 1);
               (1, 0) -> Right(0, 1);
               (1, 1) -> Right(-1, 0);
               (-1, 0) -> Left(<isize>::MAX, 0);
               (-1, 1) -> Left(1, 1);
           };
       };
       // create a new instance of the machine
       let tm = TMH::new(initial_state, input.to_vec());
       // execute the program
       dbg!(tm).execute(program).run()?;
       Ok(())
   }

Modules

actors

The actors module establishes a framework for defining and managing Turing machines

error

The error module defines the core Error type used throughout the library and provides a convenient alias for Result types.

head

prelude

programs

The programs module provides various structures and utilities for defining and managing Turing machine programs, including rules, rule spaces, and program execution.

rule

state

The state module provides abstractions and implementations for managing state within the rstm framework.

tail

The Tail of a rule defines the reaction of the actor under specific conditions. Specifically, it defines the next state, the symbol to write, and the direction to move

tape

Idealized Turing machines consider a tape, or memory, that is infinite in both directions. This tape is a one-dimensional array of symbols manipulated by the tape head according to some set of pre-defined rules.

traits

types

The core types used throughout the library such as the Direction enum

utils

useful utilities for managing and creating Turing machines and related constructs

Macros

program

The [program!] macro facilitates the creation of new Program instances using familiar syntax

rule

The [rule!] macro enables the definition of a single, Turing compatible rule using the following syntax:

rulemap

a macro to create a HashMap of rules for a Turing machine. The macro takes a list of rules in the form of

rules

[rules!] is a macro that simplifies the creation of an array of Rule instances for a Turing machine. The macro adheres to the syntax outlined in the [rule!] macro, treating each “statement” as an individual rule:

Structs

Head

The Head of a Turing machine is defined to be a two-tuple consisting of a state and a symbol. Our implementation is generic over both the state and symbol types, allowing for flexibility in their representation(s).

LearnedRule

A LearnedRule is an extension of the basic Rule structure, incorporating a confidence metric to quantify the reliability or certainty of the rule within the scope of a learning context. This is particularly useful in scenarios where rules are derived from data or experience, allowing for a more nuanced application of rules based on their confidence levels.

Rule

The Rule implementation is a concrete representation of a single instruction, or rule, within a given Turing machine program. It encapsulates the necessary components to define the behavior of the Turing machine when it encounters a specific state and symbol.

State

State is a generalized state implementation, representing the state of a system or object.

Tail

The Tail of a rule in a Turing machine

Enums

Direction

Direction enumerates the various directions a head can move, namely: left, right, and stay.

Error

The Error implementation describes the various errors that can occur within the library

Traits

Alphabet

Alphabet describes a finite set of symbols used to construct a formal language.

AsDirection

The AsDirection trait provides a convience method for converting a type into a Direction.

AsHead

Converts to a Head by reference.

AsTail

Converts a type into a Tail by reference.

Decrement

Decrement is a trait that provides a common interface for decrementing values; i.e., subtracting one from a value.

DecrementAssign

DecrementAssign is a trait that provides a common interface for decrementing values in place.

Directive

The Directive trait is used to define the expected behaviors of all tail-like objects within the system

Increment

Increment is a trait that provides a common interface for incrementing values; i.e., adding one to a value.

IncrementAssign

IncrementAssign is a trait that provides a common interface for incrementing values in place.

Incremental

Incremental is a trait that provides a common interface for incrementing and decrementing values.

Instruction

The Instruction trait defines the expected behaviors of a particular rule within a Turing machine program.

IntoDirection

The IntoDirection trait provides a convience method for converting a type into a Direction.

IntoHead

Consumes the caller to convert it into a Head.

IntoTail

A consuming trait for converting a type into a Tail.

RawState

RawState is a trait describing objects capable of being used as states in our library. The trait contains a single associated trait, the context, or inner value of the state.

RawSymbol

The RawSymbol trait establishes the minimum requirements for a type to be used as a symbol within a Turing machine.

Scope

The Scope trait establishes a common interface for all head-like objects;

Symbol

The Symbol trait extends the RawSymbol to define the expected behaviors of a symbol used within a Turing machine.

Symbolic

Symbolic is a marker trait used to signal a type that can be displayed.

Functions

get_range_around

returns a range, as a 2-tuple, around a given position within the bounds of some length and with some radius

Type Aliases

HeadMut

a type alias for a Head containing mutable references to its state and symbol

HeadRef

a type alias for a Head containing immutable references to its state and symbol

Result

A type alias for a Result with an error type of Error

TailMut

A type alias for a Tail containing mutable references to the next state and symbol.

TailRef

A type alias for a Tail containing immutable references to the next state and symbol.