🧠 Turing Machine Simulator

📘 Description

This project implements a deterministic single-tape Turing Machine simulator using Python.
It allows users to define, simulate, visualize, and test Turing machines in a structured and educational way.

The simulator performs the following tasks:

1. Defines a Turing Machine using a clear dictionary-based formalism
   (states, alphabets, transitions, initial and final states).
2. Simulates step-by-step execution of the machine on a given input word.
3. Determines acceptance or rejection of the input based on halting states.
4. Stores machines, results, and execution traces in a persistent JSON database.
5. Generates a graphical representation of the Turing machine using Graphviz (SVG).
6. Provides a Graphical User Interface (GUI) to interact with machines easily.

The goal is to model and visualize the computation process of Turing Machines, as studied in
Theory of Computation / Automata Theory courses.

---

⚙️ Example

Language recognized:
Unordered strings with the same number of a and b
L = { w ∈ {a,b}* | #a(w) = #b(w) }

Example machine definition:

machine_def = {
    "name": "a^n b^n unordred",
    "states": ["q0", "q2", "q3", "q4", "qf"],
    "input_alphabet": ["a", "b"],
    "tape_alphabet": ["a", "b", "X", "#"],
    "blank_symbol": "#",
    "initial_state": "q0",
    "final_states": ["qf"],

    "transitions": {
        "q0,a": ["q2", "X", "R"],
        "q0,b": ["q3", "X", "R"],
        "q0,X": ["q0", "X", "R"],
        "q0,#": ["qf", "#", "N"],
        ...
    },
}

Accepted inputs:
"", "ab", "ba", "aabb", "abab"

Rejected inputs:
"a", "abb", "aaabb"

🖼️ The simulator automatically generates an automaton diagram such as:
tm_a_n_b_n_unordred_xxxxxxxx.svg

---

🧩 Main Features

• 🔁 Step-by-step Turing Machine simulation
• ✅ Automatic ACCEPT / REJECT decision
• 📜 Full execution trace (state, head position, read/write, move)
• 💾 Persistent database (Database.json) for:
  • machine definitions
  • tested words
  • cached results
  • execution traces
• 🖼️ Graphviz visualization of Turing machines (SVG format)
• 🖥️ Graphical User Interface (GUI):
  • Select existing machines
  • Import / export machines
  • Test input words interactively

---

🧮 Supported Machine Types

Language	Example
Same number of a and b (unordered)	abab, bbaa
Ordered language aⁿbⁿ	aabb, aaabbb
Same number of 0 and 1	0101, 1100
Even number of 1	1100, 101010
Custom user-defined machines	via Python or JSON

---

🛠 Requirements

• Python 3.9+
• Graphviz installed and added to system PATH
  → Graphviz Download
• Tkinter (usually included with Python)

Install Python dependency:

pip install graphviz

---

▶️ Run the Program

python turing.py

The GUI will open automatically.

---

🧠 How It Works (Conceptually)

• The tape is simulated using a dynamic structure to represent an infinite tape.
• Missing transitions cause the machine to halt and reject.
• Final states cause the machine to halt and accept.
• A safety bound prevents infinite loops during simulation.
• Automaton graphs are generated directly from the transition function.

---

🧾 Educational Context

This project was developed as part of coursework on:

• Turing Machines
• Formal Languages
• Theory of Computation
• Automata Simulation and Visualization

It demonstrates:

• Formal machine modeling
• Algorithmic simulation
• State-based computation
• Graphical representation of abstract machines.