📼 Turing Machine Simulator

The foundational model of computation — tape, head, states, and transitions

Overview

A Turing machine is the theoretical foundation of all computing. Despite its simplicity — an infinite tape, a read/write head, a finite set of states, and a transition function — it can compute anything any modern computer can.

This implementation provides a clean, generic Turing machine simulator with configurable alphabets, step-by-step tracing, and several built-in machines demonstrating classic algorithms.

Machine Definition

type direction = Left | Right | Stay

type transition = {
  from_state : string;   (* current state *)
  read_sym   : char;     (* symbol under head *)
  to_state   : string;   (* next state *)
  write_sym  : char;     (* symbol to write *)
  move       : direction;(* head movement *)
}

type machine = {
  name          : string;
  states        : string list;
  alphabet      : char list;
  blank         : char;           (* default tape symbol, usually '_' *)
  initial_state : string;
  accept_states : string list;
  reject_states : string list;
  transitions   : transition list;
}

Tape Implementation

type tape = {
  left   : char list;   (* symbols to the left of head, reversed *)
  current: char;        (* symbol under the head *)
  right  : char list;   (* symbols to the right of head *)
  blank  : char;        (* blank symbol for extending *)
}

(* Head movement — extends tape with blanks as needed *)
let move_left tape =
  match tape.left with
  | []     -> { tape with current = tape.blank; right = tape.current :: tape.right }
  | h :: t -> { left = t; current = h; right = tape.current :: tape.right; blank = tape.blank }

let move_right tape =
  match tape.right with
  | []     -> { tape with current = tape.blank; left = tape.current :: tape.left }
  | h :: t -> { left = tape.current :: tape.left; current = h; right = t; blank = tape.blank }

The tape is implemented as a zipper: the current cell is explicit, with two lists representing the left and right sides. This gives O(1) head movement and O(1) read/write while keeping the tape conceptually infinite.

Execution Engine

type config = {
  tape  : tape;
  state : string;
  steps : int;
}

(* Single step: find matching transition, apply it *)
let step machine config =
  let t = List.find_opt (fun t ->
    t.from_state = config.state && t.read_sym = config.tape.current
  ) machine.transitions in
  match t with
  | None -> None  (* halts: no matching transition *)
  | Some t ->
    let tape' = write_tape config.tape t.write_sym |> move tape' t.move in
    Some { tape = tape'; state = t.to_state; steps = config.steps + 1 }

(* Run to completion or max_steps *)
let run ?(max_steps=10000) ?(verbose=false) machine input = ...

Built-in Machines

Machine	Input	Description
Binary Increment	`1011` → `1100`	Adds 1 to a binary number by scanning right-to-left, flipping bits
Unary Addition	`111+11` → `11111`	Adds two unary numbers by erasing the `+` separator
Palindrome Checker	`abcba` → accept	Checks if a string is a palindrome by comparing ends inward
Busy Beaver (3-state)	blank tape	The 3-state busy beaver — writes 6 ones in 14 steps before halting

Verbose Trace Output

(* Binary Increment: 1011 → 1100 *)
Step 0: state=q0  ..._ [1] 0 1 1 _...
Step 1: state=q0  ..._ 1 [0] 1 1 _...
Step 2: state=q0  ..._ 1 0 [1] 1 _...
Step 3: state=q0  ..._ 1 0 1 [1] _...
Step 4: state=q0  ..._ 1 0 1 1 [_]...
Step 5: state=q1  ..._ 1 0 1 [1] _...   ← scan left, flip 1→0
Step 6: state=q1  ..._ 1 0 [1] 0 _...   ← flip 1→0
Step 7: state=q1  ..._ 1 [0] 0 0 _...   ← found 0, flip to 1
Step 8: state=q2  ..._ 1 [1] 0 0 _...   ← done!
Result: ACCEPTED (8 steps) | Tape: 1100

Statistics

(* run_stats returns execution metrics *)
let run_stats machine input =
  (* Returns: steps taken, cells visited, final tape contents,
     accept/reject/timeout status *)

(* Busy Beaver 3-state:
   Steps: 14  |  Cells visited: 9  |  Ones written: 6
   This is provably the maximum for any 3-state, 2-symbol TM *)

OCaml Concepts Demonstrated

Zipper data structure — the tape is a classic zipper, giving O(1) bidirectional traversal
Variant types — direction as Left | Right | Stay
Option-based transitions — List.find_opt returns None for halting (no matching rule)
Immutable state threading — each step produces a new config; the machine is pure
Named parameters — ~max_steps, ~verbose for readable configuration
Pattern matching on lists — tape movement handles empty lists (infinite extension) naturally

Running It

# Compile and run
ocamlfind ocamlopt turing_machine.ml -o turing_machine
./turing_machine

# Demonstrates all four machines with verbose traces and statistics