Crate rstm 

rstm

Welcome to rstm, a flexible framework for creating and executing Turing machines (TM) in Rust.

Background

Turing machines are abstract models of computation initially proposed by Alan Turing in 1936. These models work by considering an infinite tape (memory) divided evenly into uniform cells capable of storing a single value that is mutated by the head of the machine according to some set of rules.

Rules

Rules or instructions for TMs can be defined as a 5-tuple consisting of:

1. Current State: The current state of the machine.
2. Current Symbol: The symbol currently being read by the head.
3. Next State: The state to transition to after executing the rule.
4. Write Symbol: The symbol to write on the tape at the current head position.
5. Shift: The direction to move the head (left, right, or stay).

Here, we break the rule into two distinct components for clarity:

• Head: defines the current state and symbol
• Tail: defines the shift direction, next state, and write symbol

Basic Usage

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

MovingHead Example

This example demonstrats how to initialize and run a 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

This module provides the ProgramBase implementation along with its associated aliases, supporting traits, and more.

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 defines a lazy stepper for a Turing machine configured with a so-called moving head.

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.

ProgramBase

The ProgramBase struct is used to define a generic program capable of being executed by a Turing machine or similar computational model. It consists of an optional initial state, a set of rules (or instructions) used to indicate how the machine should respond under different circumstances, and a marker to associate the generic parameters with the struct.

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

The Halt implementation is a binary enum designed to represent either a halting state or a stepping state within a Turing machine or similar computational model.

Constants

DEFAULT_DISPLAY_RADIUS

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

Traits

AsHead

Converts to a Head by reference.

AsTail

Converts a type into a Tail by reference.

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.

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.

HeadRepr

The HeadRepr trait extends the RawHead trait with standard initialization routines.

HeadSpace

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

Instruction

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

InstructionMut

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.

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.

RawHeadMut

The RawHeadMut trait extends the RawHead trait by providing mutable access to

RawRuleset

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

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.

RawTailMut

The RawTailMut provides mutable access to the components of a tail.

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.

TailRepr

The TailRepr trait extends the RawTail trait with standard initialization routines.

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.

Program

a type alias for a ProgramBase using a Vec as the ruleset

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