EMT - Turing Machine Executor

Welcome to the EMT documentation!

Here you can get more information on the app and on its source code.

This documentation can be subdivided in three parts:

1. Preliminary definitions on which this software is based
2. User manual
3. Code documentation

Navigate the first two sections using the following ToC.

• Preliminary Definitions
  • The Turing Machine
    • Formal Definition
  • The Turing Machine’s Executor
• Definition
• The Software
  • How to Use EMT
    • Preliminary
    • Downloading and Starting
    • Using EMT
      • Command Line Arguments

Preliminary Definitions

The Turing Machine

Formal Definition

One of the main classes of this app is the class Machine, that is the Turing Machine representation.

A Turing Machine M is defined as a 7-tuple:

M = (Q, S, λ, I, δ q₀, F)

Where:

• Q is a finite, non-empty set of states
• S is a finite, non-empty set of symbols called alphabet
• λ ∈ S is the blank symbol of the alphabet
• I = S ∖ { λ } is a subset of symbols that are allowed to appear in the input tape
• δ = (Q ∖ F) × S ↛ Q × S × { L, R } is a partial function called the transition function, where L is left shift, R is right shift. If δ is not defined on the current state and the current tape symbol, then the machine halts.
• q₀ ∈ Q is the initial state of the machine
• F ⊆ Q is a non-empty subset of Q that contains the final states of the machine: the initial tape is accepted by M if it halts in a state of F.

The Turing Machine’s Executor

Definition

A Turing Machine’s Executor is an automaton (that may or may not be a machine) that, given an input tape, executes step by step the program of a Turing Machine. For this reason, an executor E can be defined as a pair E=(M, I), where M is a Turing Machine and I is a sequence of characters that are in the “input” alphabet of the machine M.

The Software

How to Use EMT

Preliminary

Make sure that you have installed Python 3.7+ and that its location is available in the Path variable of your system. To check for it, run the following command in your favorite console:

python --version

Downloading and Starting

You can install EMT using PyPI by running the pip command (skip to step 2) or from the source code (start from step 1).

1. Download the latest release and unzip it.

2. Open your favorite console in the folder that contains the unzipped files and run

    pip install turing-machine-executor
    # OR
    python setup.py install
   

3. Type the following command to start the executor:

    emt
   

   Or, as an alternative:

    turing-machine-executor
   

Using EMT

The executor will prompt you to insert the machine using this method:

1. It will ask for the alphabet of the machine.
   1. NOTE: the first symbol that you insert will be considered as the blank (λ) symbol (see the Turing Machine’s definition for more information).
   2. :warning: WARNING: duplicates are not managed in any way. The Executor behaviour is unpredicted.
2. It will ask for the list of states
   1. NOTE: the first state that you insert will be considered as the initial state (see the Turing Machine’s definition for more information).
   2. NOTE: duplicates will be ignored (if a state is inserted more than once, only the first one inserted will be considered).
3. Once all the states are inserted, it will ask to mark the halting states.
   1. Note that the machine will stop as soon as an halting state is reached.
4. It will ask for the machine’s program in the following way: for each combination of symbol and state, it will ask for a triplet (s, d, q), where:
   • s is the symbol that will be written in the place of the once read
   • d is the direction that the machine will follow
   • q is the new state that the machine will reach after the movement
     • If q is an halting state, the machine will be stopped and the executor will print the output
   • NOTE: if the input is empty, then the combination sybol-state will be ignored. Use this information with caution.
5. It will ask for an input tape to execute the program.
   1. NOTE: do not insert the tape using spaces: each space will be considered as a character of the input.

Command Line Arguments

Here is a list of arguments and options with which EMT can be launched.

-h, --help

Prints an help message.

-v, --version

Prints EMT's version.

-a, --all

If this option is active, the machine will not print only the input and the output, but it will print every step that it does to reach the output (by default this option is disabled).