Crate rstm 

rstm

rstm is a Rust library dedicated to the constructtapen and executtapen 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 vartapeus 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 behavtaper. The library provides a set of abstracttapens and utilities to define and manipulate these components.

Basic Usage

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::{MovingHead, program};

// define an initial state
let initial_state: isize = 0;
// create a program to execute
let program = program! {
    #[default_state(initial_state)]
    rules: {
        (0, 0) -> Right(1, 0),
        (0, 1) -> Stay(-1, 1),
        (1, 0) -> Right(0, 1),
        (1, 1) -> Right(-1, 0),
        (-1, 0) -> Left(<isize>::MAX, 0),
        (-1, 1) -> Left(1, 1),
    };
};
// initialize the machine
let mut tm = MovingHead::tmh(program);
// load the input
tm.extend_tape([0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0]);
// execute the workload
tm.run().expect("failed to execute...");

Modules

actors

actors for modular Turing machine implementations

error

this module defines the Error type alongisde other useful primitives that are used throughout the rules crate.

motion

programs

the program module implements the core Program structure and its associated traits

rules

the rules module implements the Rule structure and its associated traits

state

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

traits

traits used to define common behaviors, operations, and interfaces for Turing machines and their components.

Macros

fsm

The fsm! generates a finite state machine implementation

head

The [head!] macro simplifies the creation of a Head struct by providing a concise syntax for specifying the state and symbol.

head_map

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

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:

ruler

The ruler! generates a finite state machine implementation

ruleset

[ruleset!] is a macro that simplifies the creation of an array of Rules.

s

the [s!] macro is a simple helper macro to create a State instance.

tail

! the [tail!] macro facilitates the creation of a Tail struct ! by providing a concise syntax for specifying the direction, next state, and symbol to write. As with other macros in this module, the variants of the Direction are hygenically imported based on usage, meaning one only needs to specify the variant name ! directly, i.e. Left, Right, or Stay.

Structs

DirectionIter

An iterator over the variants of Direction

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).

HeadStep

HeadStep is a structure responsible for managing the step operation of a moving head in a Turing machine simulation.

InstructionSet

The InstructionSet implementation is a generic structure representing a set of instructions or rules capable of transforming states within a computational model.

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.

Program

The Program implementation is designed to provide a structured representation of a set of rules and an optional initial state for a Turing machine or similar computational model. It encapsulates the rules that dictate the machine’s behavior and the starting point for its execution.

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.

RuleBuilder

RuleBuilder is a utilitarian structure designed to facilitate the construction of new Rule instances through a step-by-step approach. This builder pattern allows for incremental specification of rule components, enhancing code readability and maintainability.

State

The State wrapper is a generic container used to denote objects being used as a state in a Turing machine, finite-state machine, or similar computational model.

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

Enums

Direction

The Direction implementation enumerates the directions the head of a Turing machine is allowed to move, namely: left, right, or stay in place.

Error

Error enumerates the various errors encountered when dealing with rules and their components.

Halt

Inline with the formal definition of a halt state, the Halt implementation extends a stateful object, enabling any given state to be halted.

Constants

DEFAULT_DISPLAY_RADIUS

defines the radius around the head position to be displayed when printing the tape

Traits

Alphabet

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

AlphabetMut

AsHead

Converts to a Head by reference.

AsTail

Converts a type into a Tail by reference.

Decrement

An unary operator defining a decremental operation

DecrementMut

A mutable unary operator defining a self-decrementing operation

Driver

The Driver is the basis for all compatible actors within the system. Each implementation is required to define the type of internal store it will use to manage its data. This abstraction allows for flexibility in the choice of data structures, enabling the actor to adapt to various use cases and performance requirements.

Execute

A trait denoting the ability to execute a given operation, transaction, etc.

ExecuteMut

The ExecuteMut trait is similar to Execute, but it allows for mutable execution of the operation, transaction, etc. This is useful when the operation needs mutable access to the data being operated on.

ExecuteOnce

The ExecuteOnce defines the ability for an object to perform exactly one execution or computation.

Executor

The Executor trait defines the basis for compatible engines within the system.

Halting

The Halting trait establishes an interface for determining whether a given state is in a halted condition. This trait is essential for Turing machine simulations, as it allows for the identification of states that signify the end of computation.

HaltingState

The HaltingState trait is used to define states that are capable of representing halting conditions within a Turing machine simulation. For instance, if our state is of type isize, then we might define <isize>::MAX to represent a halting state.

Handle

The Handle trait

HeadSpace

A HeadSpace is a particular kind of space that deals with the heads of rules.

Increment

An unary operator defining an incremental operation

IncrementMut

A mutable unary operator defining a self-incrementing operation

Instruction

The Instruction trait establishes the base interface for all compatible rules for the automata.

IntoDirection

IntoDirection is a simple conversion trait for consuming types to turn into a Direction.

IntoHead

Consumes the caller to convert it into a Head.

IntoTail

A consuming trait for converting a type into a Tail.

PercentChange

A binary operator defining the percent difference between two values where given input is compared to the caller meaning the caller is said to be the original value whilst the input is said to be the new value.

PercentDifference

RawHead

RawHead is a marker trait used to define an interface for objects capable of being used as a head in the context of Turing machine rules.

RawState

RawState is a sealed marker trait used to define objects used to represent states. The primary benefit of such a trait is preventing cases where the State implementation is used as a state itself: State<State<Q>>.

RawTail

RawTail is a sealed marker trait used to denote objects capable of being used to represent the tail of a rule for a Turing machine.

Read

Read trait defines an interface for objects capable of reading data into a buffer.

ReadBuf

Reader

Reader establishes an interface for objects capable of reading data from internal sources.

RuleSet

The RuleSet trait establishes an interface common to all compatible sets of rules for the framework.

RuleSpace

If a headspace, or configuration space, defines all possible configurations of a system, then a rulespace defines how those configurations can change or evolve over time. In other words, if a c-space is a disconnected point cloud, then a rulespace is a set of rules that connect those points together, defining morphisms between them.

StateExt

The StateExt trait is used to extend the base RawState trait, introducing additional traits and constraints that are commonly required for state representations.

Symbolic

The Symbolic trait is a marker trait used to define types that can be used as symbols in formal languages.

TryExecute

TryExecuteMut

TryExecuteOnce

The TryExecuteOnce trait defines the ability for an object to perform one execution or computation that may fail, returning a Result configured to use the defined error type.

TryStep

A trait defining an unary step operation primarily intended to enable iterable execution patterns from implemented machines.

Write

The Write trait defines an interface for objects that can perform write operations.

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

HaltState

A type alias for a State equipped with the dedicated Halt enum as its inner type.

HeadEntry

a type alias for a Head containing a reference to the state and a mutable reference to the symbol

HeadMap

A type alias for a HashMap where each key is a Head and each value is a Tail.

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

HeadVec

MovingHead

A type alias for an EngineBase instance configured with a moving head model using the Head<Q, usize> structure to maintain the head’s position on the tape.

Result

A type alias for a Result with a custom error type (Error)

RuleArray

a type alias for an array of Rule’s

RuleHashMap

A type alias for a HashMap with usize keys and Rule values.

RuleHashSet

A type alias for a HashSet containing Rule elements.

RuleSlice

A type alias for a slice containing Rule elements.

RuleVec

A type alias for a Vec containing Rule elements.

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.

TailVec

TupleRuleArray

a type alias for an array whose elements are 2-tuples consisting of a Head and a Tail

TupleRuleSlice

a type alias for a slice whose elements are 2-tuples consisting of a Head and a Tail