ft_turing

ft_turing is an OCaml implementation of a Turing machine simulator. It loads a machine description from JSON, validates the machine and input, prints the transition table, then executes the machine step by step on a tape.

The project includes several example machines for unary arithmetic, binary-language decision problems, palindrome checking, and broken machine definitions used to test validation and blocked execution behavior.

What Problem It Solves

Turing machines are usually explained mathematically, but it can be hard to see how a formal machine behaves on real input. This project solves that by turning a JSON machine description into an executable simulator.

It helps with:

• Describing Turing machines in a readable JSON format.
• Validating machine definitions before execution.
• Running a machine against an input string.
• Printing a detailed transition trace.
• Detecting blocked machines and missing transition rules.
• Limiting execution to avoid infinite loops.
• Collecting runtime statistics for selected machines.
• Experimenting with complexity behavior on concrete inputs.

Stack

• Language: OCaml
• OCaml version: 5.2.1
• Build system: Makefile
• Package manager: opam
• Compiler tools: ocamlfind, ocamlc, ocamlopt
• JSON parser: yojson
• Output artifact: native executable ft_turing

Features

• JSON-based Turing machine loading.
• Strong validation for:
  • required JSON fields
  • field types
  • alphabet symbols
  • duplicate alphabet entries
  • blank symbol membership
  • duplicate states
  • unknown initial/final states
  • malformed transitions
  • invalid transition actions
  • duplicate transition rules
• Machine-specific input validation for bundled examples.
• Tape model with left side, current head cell, and right side.
• Left and right tape movement with blank-cell expansion.
• Per-step transition trace.
• Halt detection through final states.
• Blocked execution reporting when a state or rule is missing.
• Step limit protection for non-terminating machines.
• Optional stats mode with:
  • input length
  • executed steps
  • visited tape space
  • left/right move counts
  • changed writes
  • state visit counts
  • theoretical time and space notes for known machines

Project Structure

.
├── Makefile
├── README.md
├── intf/
│   ├── Machine.mli
│   ├── Machine_error.mli
│   ├── Machine_loader.mli
│   ├── Machine_printer.mli
│   ├── Machine_validator.mli
│   └── Runner.mli
├── src/
│   ├── Main.ml                # CLI entry point
│   ├── Machine.ml             # Machine types and input validation hook
│   ├── Machine_error.ml       # Validation error model
│   ├── Machine_loader.ml      # JSON parsing and machine construction
│   ├── Machine_printer.ml     # Usage, machine info, and trace output
│   ├── Machine_validator.ml   # Machine-specific input validators
│   └── Runner.ml              # Tape execution and stats collection
└── machines/
    ├── unary_add.json
    ├── unary_sub.json
    ├── zero_2n.json
    ├── zero_n_one_n.json
    ├── palindrome_decider.json
    ├── meta_run_unary_add.json
    └── broken_machines/       # Invalid or blocked examples for testing

Machine JSON Format

Each machine file uses this shape:

{
  "name": "machine_name",
  "alphabet": ["1", "+", "=", "."],
  "blank": ".",
  "states": ["start", "HALT"],
  "initial": "start",
  "finals": ["HALT"],
  "transitions": {
    "start": [
      {
        "read": "1",
        "to_state": "HALT",
        "write": "1",
        "action": "RIGHT"
      }
    ]
  }
}

Supported actions are:

• LEFT
• RIGHT

Build

The Makefile creates an opam switch named ft_turing_env if it does not already exist, installs yojson, then builds the native executable.

make

If your shell has not loaded the opam switch environment, use:

opam exec --switch=ft_turing_env -- make

Useful targets:

make              # Build ft_turing
make clean        # Remove object files
make fclean       # Remove object files and binaries
make re           # Rebuild from scratch
make delete_env   # Remove the ft_turing_env opam switch

Usage

./ft_turing [-h] [--stats [--no-trace]] jsonfile input

Examples:

./ft_turing machines/unary_add.json '111+11='
./ft_turing machines/unary_sub.json '1111-11='
./ft_turing machines/palindrome_decider.json '0110'
./ft_turing machines/zero_n_one_n.json '000111'
./ft_turing machines/zero_2n.json '0000'

Run with statistics:

./ft_turing --stats machines/unary_add.json '111+11='

Run with statistics but without the per-step trace:

./ft_turing --stats --no-trace machines/unary_add.json '111+11='

Show help:

./ft_turing --help

Included Machines

Machine	Purpose	Example input
unary_add	Adds unary numbers	111+11=
unary_sub	Subtracts unary numbers	1111-11=
zero_2n	Accepts even-length strings of zeroes	0000
zero_n_one_n	Decides strings shaped like 0^n1^n	000111
palindrome_decider	Decides binary palindromes	0110
meta_run_unary_add	Wrapper-style unary add runner	A:111+11=

The machines/broken_machines/ directory contains intentionally invalid or non-terminating examples for testing validation errors, blocked states, missing rules, and step-limit behavior.