Reverse Turing Machine

Algorithm for running Turing Machines in reverse (to generate inputs rather than interpret them).

Traditionally, Turing Machines are run forwards: you start at an initial state (e.g. start) with a full tape. The tape is then consumed until a final state is reached (e.g. valid/invalid), at which point you have your result.

Running in reverse means the opposite: you start at a final state (e.g. valid) with an empty tape. The tape is then populated until an initial state is reached (e.g. start), at which point execution stops, and you have your input.

Why do this? To automatically derive input generators from predicates (has applications in testing frameworks).

Exploring the repository

This repository is written in Scala (using Cats).

• Turing machine ADT

  • Machine (contains the machine rules)

  • Machine Tape (contains input/output symbols)

  • Machine State (either Accept, Reject or a user-defined intermediate state)

  • Machine Configuration (contains the machine rules, tape and state)

• Algorithms

  • Forward execution (i.e. validating inputs).

  • Reverse execution (i.e. generating inputs).

• Examples:

  • Type-1 Grammar (i.e. context-sensitive)

  • Type-2 Grammar (i.e. context-free)

  • Type-3 Grammar (i.e. regular)

Note: these algorithms have been optimised, so forgive the occasional bit of non-FP code!

Getting started

The scalacheck tests assert the set of inputs generated by our algorithm match the set of inputs generated by a hand-written generator for all 3 example predicates in the test suite.

sbt test

Using the algorithm is simple:

1. Write a turing machine (Machine[S, I, O]) -- this is the tedious part.

2. Call machine.generate() to generate a sequence of inputs.

3. Done!

License

This software is licensed under the MIT license.