Turing Machine Compilator

Introdution

Turing Machine (TM) - an abstract performer (abstract computing machine). It was proposed by Alan Turing in 1936 to formalize the concept of an algorithm.

The Turing Machine is an extension of the finite state machine and, according to the Church-Turing thesis, is able to simulate all performers (by setting transition rules) that somehow implement the process of stepwise calculation in which each step of the calculation is quite elementary.

That is, any intuitive algorithm can be implemented using some Turing machine.

A turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions. A TM is expressed as a 7-tuple (Q, T, B, ∑, δ, q0, F) where:

• Q is a finite set of states
• T is the tape alphabet (symbols which can be written on Tape)
• B is blank symbol (every cell is filled with B except input alphabet initially)
• ∑ is the input alphabet (symbols which are part of input alphabet)
• δ is a transition function which maps Q × T → Q × T × {L,R}. Depending on its present state and present tape alphabet (pointed by head pointer), it will move to new state, change the tape symbol (may or may not) and move head pointer to either left or right.
• q1 is the initial state
• F is the set of final states. If any state of F is reached, input string is accepted.

Syntax of compilator

# You can write your comment here

# At the beginning you must write initializations:
ALPHABET = {X_1, ... ,X_N}; # X_1, ... ,X_N - are symbols of TM Alphabet
EMPTY = {X_i};              # X_i - is empty (blank) symbol of ALPHABET
START_STATE = {q1};         # q1 - is initial state of TM
STOP_STATE = {q0};          # q0 - is last (halt) state of TM

# After initializations, you can wrote TM code commands:
qi,X_i -> qj,X_j,R;         # The syntax is: CURRENT_STATE,CURRENT_SYMBOL -> NEXT_STAGE,ACTION,MOVE;

Here you can find an examples of code in this syntax.

Visualisator

Here is an example of visualisation for Turing Machine, which checks balancing bracket sequence:

Here you can find more visualisations of different turing machines.

Installation of Turing_Machine

Make sure you have installed Python 3.

Clone repository:

• Run git clone https://github.com/tivole/Turing_Machine.git to clone repository.
• Run cd Turing_Machine/src to change directory.

Install requirements:

• Run pip install -r requirements.txt to install required libraries.

Now you can use Turing_Machine.

Usage of Compilator and Visualisator

1. Write your TM code in turing_code.txt
2. Write your INPUT sequnce in input.txt
3. Run in terminal: python3 main.py

References

1. Turing's paper
2. The Church-Turing Thesis