TuringSim - A template-intensive high-performance framework to simulate Turing machines and other abstract computation models.

Simulating Turing machines, or finite state automata is easy when they have explicit transitions, and not many of them. But if they use transition patterns, it may quickly become awful. TuringSim is there for you! It is a very configurable framework with a lot of predefined machine types, that makes running computation models easy and efficient.

Check out the repo.

Overview

The fundamental class is TuringSim::Machine::Machine. It is the most abstract class representing a machine. The most important template parameter is the first one: TransitionType. It must be a derived class of TuringSim::Transition::Transition. A machine must be able to return initial states, transitions matching a given configuration and deciding when a configuration is halting. Moreover, depending whether the machine is accepting or not, it may also be able to decide whether a configuration is accepting.

Class TuringSim::Transition::Transition is the core of machine executions. A transition provides two functions: one that checks if the transition matches, and one to apply it. Transitions are parameterized by two main types: the type of the states of the machine, and the type of the storage.

A machine is not able to run by it self. To do so, we need to use a TuringSim::Runner::Runner. Runners may implement various execution strategy.

Machines

Determinism

Machines may be deterministic or not. Non-deterministic machines must be able to return the set of initial states, matching transitions, and check if a configuration is terminating. Deterministic machines must also be able to return the single initial state, and the only matching transition. Deterministic machines are thus special case of non-deterministic machines.

Termination

Machines have 3 ways of terminating:

1. the machine decides that the configuration is terminating,
2. transitions can stop the execution,
3. there are no matching transitions.

Accepting

Machines can be used for computation (and thus, being non accepting) or decision. There are two kinds of accepting machines: regularly accepting machines (or simply accepting machines) and alternating machines. The execution of a non-accepting machine ends when it reaches a halting state. Execution of accepting or alternating machines ends when acceptance can be decided.

Accepting machines accepts their input if at least one execution leads to an accepting configuration. Each execution ends as soon as it encounters a halting configuration or an accepting configuration.

Alternating machines allows nodes to be quantified universally, and not only existentially like accepting machines. Each execution ends in one of these cases:

• an accepting configuration,
• a rejecting configuration,
• an halting (non-accepting non-rejecting) configuration:
  • if it is a universal node, it is accepting,
  • if it is an existential node, it is rejecting.

machine kind

• Turing machines: machines whose memory is a tape or a half-tape:
  • General Turing machines
  • Local Turing machines: TM that can find matching transitions for only the current cell of the tape
  • Simple Turing machines: TM that use explicit states and symbols
  • m-configuration Turing machines: TM whose states are terms
  • Turing-style m-configuration Turing machines: m-configuration Turing machines whose transitions are of the kind of Turing's 1936 paper.
  • the universal Turing machine defined in Turing's 1936 paper.
• Finite state machines: machines whose memory is a word that can only be read once.
  • General FSM
  • Simple FSM: FSM with simple states and symbols, without epsilon transitions
  • Simple FSM with epsilon transition
• Pushdown machines: machines whose memory is a pair of a word and a stack.
  • General PDM
  • Simple PDM: PDM with simple states and symbols that can only pop one symbol at each transition
  • General PDM: simple PDM that can pop arbitrary many symbols.
• Amnesic machines: machines whose memory is a unit type
  • General amnesic machines
  • simple amnesic machines: amnesic machines with simple states.

Transitions

Transitions are returned by machines. They provide two functions:

• match that test if the transition matches a configuration
• apply that apply the transition on a given configuration, modify the memory state in-place, and return the new state.

When matching is a hard job (like term unification), usually, apply shall do something similar. To avoid performing twice the same computation, match return an apply helper that is provided to apply. The apply helper type is a template parameter.

Runner

Runner are in charge of running machines. They are derived classes of TuringSim::Runner::MachineRunner. There are generic runners, for deterministic and non-deterministic machines. They can run a given number of execution steps (step), or a run until the machine terminates (if non-accepting) or decides acceptation (if accepting or alternating) (exec). The latter is quite risky: termination is up to the developer since it is not decidable in general.

For accepting or alternating machines, generic runners also provide a function accept that runs the machine like exec but also returns the decision.

Runners can be implemented more efficiently for particular machines. In general, for non-deterministic machine, the memory can be arbitrarily modified, and must be copied between to execution traces. But, e.g. for finite state machines, the input word is constant, only the position may change (and only with epsilon transitions). For this reason, a runner for non-deterministic machines can be more efficient than the general case.

Listeners

Machine execution can be logged by a TuringSim::Listener::Listener.

Memories

There are no formal requirements on memory structures. It is convenient to be able to observe and modify them externally.

We provide:

• (Half-)tape,
• Stack and multi-stack,
• Tape and multi-tape,
• Random Access Memory,
• Word.

States

States pattern must provide a match function to match against an actuel state.

We provide two kind of states/patterns:

• Simple states are values of arbitrary types and patterns are a simple explicit value to check equality with,
• m-configuration are terms, and pattern are tree-terms with variable leaves.

Unification is required when matching this second kind of states.

Symbols

Symbol patterns can be static or dependant on a context for Turing 1936-style transition.

Transitions

Transitions are provided for each kind of provided machines. Each derived class shall specialized only one aspect at once.