MiniTM

MiniTM is a compact C++20 command-line Turing machine simulator. It parses .tm machine definitions, places an input string on an unbounded tape, and runs until the machine accepts, rejects, reaches a missing transition, or hits a step limit.

What Is A Turing Machine?

A Turing machine is a formal model of computation. It has a tape of symbols, a head that reads and writes one tape cell at a time, and a finite set of states. Each transition says which symbol to write, whether the head should move left, right, or stay in place, and which state to enter next.

Features

• Plaintext .tm machine files with metadata and transition rules.
• Single-tape simulation with a configurable blank symbol.
• Exact transition lookup with * wildcard fallback rules.
• Interactive step traces with optional tape windows and head markers.
• Human-readable final reports or JSON output.
• Parser diagnostics with line numbers, source snippets, and caret positions.
• No runtime dependencies beyond the C++ standard library.

Build

make

This builds the tm executable with C++20 and warnings enabled.

To remove generated files:

make clean

Usage

Usage: tm [options] <machine.tm> <input>

Options:
  --help                 Show this help text
  --step                 Pause before each transition and print a trace
  --window <cells>       In --step mode, show N cells around the head
  --max-steps <steps>    Stop before exceeding this transition count (default: 10000)
  --json                 Print the final result as JSON

Run a machine:

./tm examples/unary_increment.tm 111

Example output:

input: 111
final tape: 1111
final state: halt_accept
halt reason: accepted
steps: 4

Use "" as the input argument when the initial tape should be empty.

Common Commands

./tm --help
./tm examples/unary_increment.tm 111
./tm examples/binary_flip.tm 101001
./tm examples/erase.tm 111
./tm examples/binary_increment.tm 1011
./tm examples/reject_on_zero.tm 1101
./tm examples/three_cell_palindrome.tm 101
./tm --step examples/unary_increment.tm 111
./tm --step --window 10 examples/unary_increment.tm 111
./tm --max-steps 500 examples/unary_increment.tm 111
./tm --json examples/unary_increment.tm 111

--step prints the current step, state, head position, and tape rendering, then waits for Enter before executing the next transition.

--window N can only be used with --step. It bounds step-mode tape rendering to N cells on each side of the head and includes position labels plus a head marker.

--json prints the final result as JSON with input, final_tape, final_state, halt_reason, and steps fields. It cannot be combined with interactive --step mode.

Test

make test

The test target builds and runs one test executable per module, then cleans the generated binaries and object files.

Machine File Format

Machine files use metadata lines followed by transition lines:

blank: _
start: scan
accept: halt_accept
reject: halt_reject

scan 1 -> 1 R scan
scan _ -> 1 S halt_accept

Required metadata:

blank: <single character>
start: <state>
accept: <state>
reject: <state>

The start, accept, and reject states must be present and distinct.

Transition format:

<current_state> <read_symbol> -> <write_symbol> <direction> <next_state>

Each read and write symbol is exactly one character. State names and symbols are whitespace-delimited tokens.

Supported directions:

L  move left
R  move right
S  stay

Wildcards

* is reserved for wildcard transitions. A read symbol of * is used only when no exact transition exists for the current state and tape symbol. A write symbol of * preserves the symbol that was read instead of writing a literal asterisk.

Example wildcard scan:

scan * -> * R scan

* cannot be used as the blank symbol.

Comments And Tokens

Blank lines are ignored. Lines beginning with # are comments, and inline comments are supported after #. Because # always starts a comment, it cannot be used as a tape symbol or state name.

Transition lines are identified by the standalone -> token, so : may be used as a tape symbol or state name.

Examples

Unary increment:

./tm examples/unary_increment.tm 111

Final tape:

1111

Binary flip:

./tm examples/binary_flip.tm 101001

Final tape:

010110

Erase:

./tm examples/erase.tm 111

Final tape:

_

Binary increment:

./tm examples/binary_increment.tm 1011

Final tape:

1100

Reject on zero:

./tm examples/reject_on_zero.tm 1101

Halt reason:

rejected

Three-cell palindrome check:

./tm examples/three_cell_palindrome.tm 101

Halt reason:

accepted

Halt Behavior

MiniTM reports one of these halt reasons:

accepted
rejected
no transition
step limit reached

accepted and rejected happen when the current state matches the configured accept or reject state. no transition means the machine had no rule for the current state and tape symbol. step limit reached means execution stopped before exceeding --max-steps.

Error Examples

Missing file:

error: could not open file: examples/missing.tm

Invalid CLI argument:

error: invalid --max-steps value 'nope': expected a positive integer

Invalid machine file:

error: line 7: invalid transition direction 'X'
  scan 1 -> 1 X scan
              ^

Duplicate transition:

error: line 8: duplicate transition for state 'scan' and symbol '1'; first defined on line 7
  scan 1 -> 0 S halt_reject
  ^

Limitations

MiniTM currently supports deterministic, single-tape machines with single-character tape symbols. It does not support multi-tape machines, graphical displays, or external machine-definition includes.