Turing Machine Simulator

An app for simulating single-tape Turing machines in the browser.

It supports both deterministic Turing machines (DTMs) and nondeterministic Turing machines (NTMs)

Features

• Single-tape TM simulator with tape extending in both directions
• Fixed 21-cell viewport that follows the head
• Deterministic and nondeterministic transition programs
• Pure TypeScript execution core with no React dependencies
• Manual stepping and step-back history for DTMs
• Manual branch exploration for NTMs
• BFS-based NTM search with accepting-path replay
• Configurable accept and reject state sets
• Live parser with inline syntax errors
• Built-in presets:
  • Binary increment
  • Palindrome checker
  • Binary addition
  • Substring matcher NTM (00 or 11)
• Save/load .tm files including metadata
• Light and dark mode

Local Development

Install dependencies:

npm install

Start the dev server:

npm run dev

Build for production:

npm run build

Run tests:

npm test

Transition Syntax

Write one transition per line:

STATE, SYMBOL -> NEXT_STATE, WRITE_SYMBOL, DIRECTION

Rules:

• STATE and NEXT_STATE can be any strings.
• SYMBOL and WRITE_SYMBOL must be single characters.
• Use B for blank.
• DIRECTION can be:
  • L for left
  • R for right
  • S for stay
• Lines starting with # are treated as comments.

Example:

q0, 1 -> carry, 0, L
carry, B -> done, 1, R

Deterministic vs Nondeterministic Machines

A program is treated as deterministic if every (state, symbol) pair maps to exactly one action.

A program is treated as nondeterministic if any (state, symbol) pair maps to two or more actions.

Example of a nondeterministic rule set:

start, 0 -> start, 0, R
start, 0 -> check0, 0, S

The UI shows a live Deterministic or Nondeterministic badge based on the parsed transition map.

How Execution Works

Deterministic machines

At each step, the machine:

1. Reads the symbol under the head.
2. Looks up the transition for (state, symbol).
3. Writes the new symbol.
4. Moves the head.
5. Enters the next state.

If no transition exists for the current (state, symbol), the machine accepts.

Nondeterministic machines

At each step, the machine may have multiple possible next transitions.

The simulator supports two NTM workflows:

• Manual exploration: choose one branch at a time
• BFS search: explore branches breadth-first until an accepting path is found, all branches reject, or the search budget is exhausted

If a transition is missing for a branch in an NTM, that branch rejects.

Accept and Reject States

By default:

• Accept states: ACCEPT, ACCEPTED
• Reject states: REJECT, REJECTED

You can override these in the UI.

Behavior:

• Saved and displayed state names preserve the casing you typed.
• Runtime matching is case-insensitive.
• State names can be separated by commas, new lines, spaces, or any mix of them.
• If the same state appears in both lists, reject takes precedence.

Example:

• If HALT_OK is listed in Accept states, entering HALT_OK accepts.
• If ACCEPT is listed in Reject states, then ACCEPT rejects because the override is applied directly.

UI Controls

Shared controls

• Reset: restore the machine to the current initial tape and initial state
• Delay: auto-run or replay delay in milliseconds
• Save: download the current machine as a .tm file
• Load: load a previously saved .tm file
• Scroll Left / Scroll Right: manually move the visible tape viewport
• Back to Head: recenter the viewport on the current head position and resume follow-head behavior

Deterministic controls

• Step Forward: execute one transition
• Step Back: restore the previous full configuration snapshot
• Run: auto-step until the machine halts
• Pause: stop auto-run

Nondeterministic controls

• Step Forward: advance one exploration step
• Step Back: restore the previous full branch snapshot
• Run: launch BFS search
• Pause: pause accepting-path replay
• Max explored configs: limit the total BFS dequeue count before timeout

If an NTM step has multiple possible next actions, the simulator shows an inline choice panel below the tape.

NTM Search Model

NTM Run uses breadth-first search (BFS), not depth-first search.

This matters because BFS:

• finds shallow accepting paths earlier
• avoids getting stuck deep in one branch while missing a short accepting branch elsewhere

Possible outcomes of NTM Run:

• accepted: an accepting branch was found
• rejected: all explored branches rejected
• timeout: the search exceeded Max explored configs

If an accepting branch is found, the simulator replays that accepting path step by step. During replay, you can use Explore from here to switch back into manual branch exploration at the current replayed configuration.

Limitations of Nondeterministic Search

NTMs can grow very quickly.

Important practical limits:

• Branch counts can explode even for small-looking programs.
• BFS may become slow or memory-heavy.
• timeout is inconclusive; it does not prove reject.
• Manual history and replay store full tape snapshots, not diffs.

So for larger NTMs, the Max explored configs budget is important.

Presets

The project ships with these presets:

• Binary increment
• Palindrome checker
• Binary addition
• Substring matcher — accepts if input contains 00 or 11

The substring matcher preset is nondeterministic and is covered by a unit test.

Save Format

Saved .tm files include metadata comments plus the transition program.

Example:

# initialState: q0
# initialTape: 1011
# acceptStates: ACCEPT, ACCEPTED
# rejectStates: REJECT, REJECTED

q0, 1 -> carry, 0, L
carry, B -> done, 1, R

Older transition-only files without metadata are still supported when loading.

TODO / Future Versions

• Step complexity visualizer
• Two-stack machine
• Church-Turing playground: lambda calculus reducer

Feedback

If you have feedback, suggestions, or bug reports, reach out at yashramani002@yahoo.com.