Turing Machines: An Interactive Exploration

A Turing machine is the simplest theoretical model of computation. Invented by Alan Turing in 1936, it consists of:

1. An infinite tape divided into cells, each holding a symbol (or blank)
2. A read/write head that can move left or right along the tape
3. A finite set of states including a start state and halt state
4. A transition function that, given the current state and symbol under the head, determines: what to write, which direction to move, and what state to enter next

Despite its simplicity, a Turing machine can compute anything that any computer can—the Church-Turing thesis asserts this equivalence.

Interactive Turing Machine Simulator

<style>
  .tm-container { font-family: system-ui; color: var(--color-text); }
  .tm-controls { display: flex; gap: 8px; margin: 12px 0; flex-wrap: wrap; }
  .tm-controls button { 
    padding: 8px 16px; 
    background: var(--color-accent); 
    color: white; 
    border: none; 
    border-radius: 4px; 
    cursor: pointer; 
    font-size: 14px;
  }
  .tm-controls button:hover { opacity: 0.9; }
  .tm-controls button:disabled { opacity: 0.5; cursor: not-allowed; }
  
  .tape-container { 
    overflow-x: auto; 
    background: var(--color-bg-alt); 
    border-radius: 6px; 
    padding: 12px;
    margin: 12px 0;
  }
  .tape { display: flex; gap: 2px; min-width: max-content; }
  .cell { 
    width: 36px; 
    height: 36px; 
    display: flex; 
    align-items: center; 
    justify-content: center; 
    border: 2px solid var(--color-border);
    border-radius: 4px;
    font-family: monospace;
    font-size: 18px;
    font-weight: bold;
    background: var(--color-bg);
  }
  .cell.head { 
    border-color: var(--color-accent); 
    box-shadow: 0 0 0 3px var(--color-accent);
    background: var(--color-bg-alt);
  }
  .cell.reading {
    animation: pulse 0.5s ease-in-out;
  }
  @keyframes pulse {
    0%, 100% { transform: scale(1); }
    50% { transform: scale(1.15); }
  }
  
  .head-indicator {
    text-align: center;
    margin-top: -4px;
    margin-bottom: 8px;
    font-size: 24px;
    color: var(--color-accent);
  }
  
  .state-display {
    display: flex;
    gap: 16px;
    margin: 12px 0;
    padding: 12px;
    background: var(--color-bg-alt);
    border-radius: 6px;
  }
  .state-box {
    display: flex;
    flex-direction: column;
    gap: 4px;
  }
  .state-label { font-size: 12px; color: var(--color-text-secondary); }
  .state-value { 
    font-size: 20px; 
    font-weight: bold; 
    font-family: monospace;
    padding: 4px 12px;
    background: var(--color-bg);
    border-radius: 4px;
  }
  .state-value.halted { color: var(--color-success); }
  .state-value.error { color: var(--color-error); }
  
  .rules-section { margin: 16px 0; }
  .rules-section h4 { margin: 0 0 8px 0; color: var(--color-text-secondary); }
  .rule-table { 
    width: 100%; 
    border-collapse: collapse; 
    font-size: 13px;
    font-family: monospace;
  }
  .rule-table th, .rule-table td { 
    padding: 6px 8px; 
    border: 1px solid var(--color-border);
    text-align: center;
  }
  .rule-table th { background: var(--color-bg-alt); }
  .rule-table tr.active td { background: var(--color-accent); color: white; }
  
  .presets { margin: 12px 0; }
  .presets label { font-size: 14px; color: var(--color-text-secondary); margin-right: 8px; }
  .presets select { 
    padding: 6px 12px; 
    border-radius: 4px; 
    border: 1px solid var(--color-border);
    background: var(--color-bg);
    color: var(--color-text);
  }
  
  .input-section { margin: 12px 0; }
  .input-section label { font-size: 14px; color: var(--color-text-secondary); margin-right: 8px; }
  .input-section input { 
    padding: 6px 12px; 
    border-radius: 4px; 
    border: 1px solid var(--color-border);
    background: var(--color-bg);
    color: var(--text-color);
    font-family: monospace;
    width: 200px;
  }
  
  .log { 
    margin: 12px 0; 
    padding: 12px; 
    background: var(--color-bg-alt); 
    border-radius: 6px;
    font-family: monospace;
    font-size: 13px;
    max-height: 120px;
    overflow-y: auto;
    color: var(--color-text-secondary);
  }
  .log-entry { margin: 2px 0; }
  .log-entry.step { color: var(--color-text); }
  
  .speed-control { display: flex; align-items: center; gap: 8px; }
  .speed-control label { font-size: 13px; color: var(--color-text-secondary); }
  .speed-control input[type="range"] { width: 100px; }
</style>

<div class="tm-container">
  <div class="presets">
    <label>Example Machines:</label>
    <select id="preset-select">
      <option value="binary-increment">Binary Increment (101 → 110)</option>
      <option value="binary-complement">Binary Complement (101 → 010)</option>
      <option value="palindrome">Palindrome Checker</option>
      <option value="busy-beaver">Busy Beaver (2-state)</option>
      <option value="unary-doubler">Unary Doubler (111 → 111111)</option>
      <option value="copy">Copy String (abc → abcabc)</option>
    </select>
  </div>
  
  <div class="input-section">
    <label>Initial Tape (symbols only, blanks will pad):</label>
    <input type="text" id="tape-input" placeholder="e.g., 101">
  </div>
  
  <div class="tm-controls">
    <button id="btn-reset">Reset</button>
    <button id="btn-step">Step</button>
    <button id="btn-run">Run</button>
    <button id="btn-stop" disabled>Stop</button>
  </div>
  
  <div class="speed-control">
    <label>Speed:</label>
    <input type="range" id="speed-slider" min="50" max="1000" value="300">
    <span id="speed-label">300ms</span>
  </div>
  
  <div class="state-display">
    <div class="state-box">
      <span class="state-label">Current State</span>
      <span class="state-value" id="current-state">q0</span>
    </div>
    <div class="state-box">
      <span class="state-label">Steps</span>
      <span class="state-value" id="step-count">0</span>
    </div>
    <div class="state-box">
      <span class="state-label">Status</span>
      <span class="state-value" id="status">Ready</span>
    </div>
  </div>
  
  <div class="head-indicator">↓</div>
  <div class="tape-container">
    <div class="tape" id="tape"></div>
  </div>
  
  <div class="rules-section">
    <h4>Transition Rules (current state, read → write, move, next state)</h4>
    <table class="rule-table" id="rules-table">
      <thead><tr><th>State</th><th>Read</th><th>Write</th><th>Move</th><th>Next</th></tr></thead>
      <tbody id="rules-body"></tbody>
    </table>
  </div>
  
  <div class="log" id="log">
    <div class="log-entry">Select a machine and click Reset to begin.</div>
  </div>
</div>

<script>
// Turing Machine Presets
const PRESETS = {
  'binary-increment': {
    name: 'Binary Increment',
    symbols: ['0', '1', '_'],
    states: ['q0', 'q1', 'halt'],
    startState: 'q0',
    haltState: 'halt',
    rules: [
      { state: 'q0', read: '0', write: '0', move: 'R', next: 'q0' },
      { state: 'q0', read: '1', write: '1', move: 'R', next: 'q0' },
      { state: 'q0', read: '_', write: '_', move: 'L', next: 'q1' },
      { state: 'q1', read: '0', write: '1', move: 'R', next: 'halt' },
      { state: 'q1', read: '1', write: '0', move: 'L', next: 'q1' },
      { state: 'q1', read: '_', write: '1', move: 'R', next: 'halt' },
    ],
    example: '1011',
    description: 'Adds 1 to a binary number. Carries over correctly.'
  },
  'binary-complement': {
    name: 'Binary Complement',
    symbols: ['0', '1', '_'],
    states: ['q0', 'halt'],
    startState: 'q0',
    haltState: 'halt',
    rules: [
      { state: 'q0', read: '0', write: '1', move: 'R', next: 'q0' },
      { state: 'q0', read: '1', write: '0', move: 'R', next: 'q0' },
      { state: 'q0', read: '_', write: '_', move: 'R', next: 'halt' },
    ],
    example: '101',
    description: 'Flips each bit (0↔1) in a binary string.'
  },
  'palindrome': {
    name: 'Palindrome Checker',
    symbols: ['a', 'b', 'X', 'Y', '_'],
    states: ['q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'halt-yes', 'halt-no'],
    startState: 'q0',
    haltState: 'halt-yes',
    rules: [
      // Match first a, mark it, go to end
      { state: 'q0', read: 'a', write: 'X', move: 'R', next: 'q1' },
      { state: 'q0', read: 'b', write: 'Y', move: 'R', next: 'q3' },
      { state: 'q0', read: 'X', write: 'X', move: 'R', next: 'q0' },
      { state: 'q0', read: 'Y', write: 'Y', move: 'R', next: 'q0' },
      { state: 'q0', read: '_', write: '_', move: 'R', next: 'halt-yes' },
      // Find rightmost symbol after matching a
      { state: 'q1', read: 'a', write: 'a', move: 'R', next: 'q1' },
      { state: 'q1', read: 'b', write: 'b', move: 'R', next: 'q1' },
      { state: 'q1', read: 'X', write: 'X', move: 'R', next: 'q1' },
      { state: 'q1', read: 'Y', write: 'Y', move: 'R', next: 'q1' },
      { state: 'q1', read: '_', write: '_', move: 'L', next: 'q2' },
      // Check if rightmost is a
      { state: 'q2', read: 'a', write: 'X', move: 'L', next: 'q4' },
      { state: 'q2', read: 'X', write: 'X', move: 'R', next: 'halt-yes' },
      { state: 'q2', read: 'b', write: 'b', move: 'R', next: 'halt-no' },
      // Match first b, mark it, go to end
      { state: 'q3', read: 'a', write: 'a', move: 'R', next: 'q3' },
      { state: 'q3', read: 'b', write: 'b', move: 'R', next: 'q3' },
      { state: 'q3', read: 'X', write: 'X', move: 'R', next: 'q3' },
      { state: 'q3', read: 'Y', write: 'Y', move: 'R', next: 'q3' },
      { state: 'q3', read: '_', write: '_', move: 'L', next: 'q5' },
      // Check if rightmost is b
      { state: 'q5', read: 'b', write: 'Y', move: 'L', next: 'q4' },
      { state: 'q5', read: 'Y', write: 'Y', move: 'R', next: 'halt-yes' },
      { state: 'q5', read: 'a', write: 'a', move: 'R', next: 'halt-no' },
      // Return to leftmost unmarked
      { state: 'q4', read: 'a', write: 'a', move: 'L', next: 'q4' },
      { state: 'q4', read: 'b', write: 'b', move: 'L', next: 'q4' },
      { state: 'q4', read: 'X', write: 'X', move: 'R', next: 'q0' },
      { state: 'q4', read: 'Y', write: 'Y', move: 'R', next: 'q0' },
      { state: 'q4', read: '_', write: '_', move: 'R', next: 'q0' },
    ],
    example: 'aba',
    description: 'Checks if string is a palindrome. Halts in "halt-yes" or "halt-no".'
  },
  'busy-beaver': {
    name: 'Busy Beaver (2-state)',
    symbols: ['_', '1'],
    states: ['A', 'B', 'halt'],
    startState: 'A',
    haltState: 'halt',
    rules: [
      { state: 'A', read: '_', write: '1', move: 'R', next: 'B' },
      { state: 'A', read: '1', write: '1', move: 'L', next: 'B' },
      { state: 'B', read: '_', write: '1', move: 'L', next: 'A' },
      { state: 'B', read: '1', write: '1', move: 'R', next: 'halt' },
    ],
    example: '',
    description: 'A 2-state busy beaver. Writes maximum 1s before halting (6 steps, 4 ones).'
  },
  'unary-doubler': {
    name: 'Unary Doubler',
    symbols: ['1', 'X', '_'],
    states: ['q0', 'q1', 'q2', 'q3', 'q4', 'halt'],
    startState: 'q0',
    haltState: 'halt',
    rules: [
      { state: 'q0', read: '1', write: 'X', move: 'R', next: 'q1' },
      { state: 'q0', read: 'X', write: 'X', move: 'R', next: 'q0' },
      { state: 'q0', read: '_', write: '_', move: 'R', next: 'q3' },
      { state: 'q1', read: '1', write: '1', move: 'R', next: 'q1' },
      { state: 'q1', read: 'X', write: 'X', move: 'R', next: 'q1' },
      { state: 'q1', read: '_', write: '1', move: 'R', next: 'q2' },
      { state: 'q2', read: '_', write: '1', move: 'L', next: 'q4' },
      { state: 'q3', read: 'X', write: '1', move: 'L', next: 'q3' },
      { state: 'q3', read: '_', write: '_', move: 'R', next: 'halt' },
      { state: 'q4', read: '1', write: '1', move: 'L', next: 'q4' },
      { state: 'q4', read: 'X', write: 'X', move: 'L', next: 'q4' },
      { state: 'q4', read: '_', write: '_', move: 'R', next: 'q0' },
    ],
    example: '111',
    description: 'Doubles the number of 1s: 111 → 111111'
  },
  'copy': {
    name: 'Copy String',
    symbols: ['a', 'b', 'X', 'Y', '_'],
    states: ['q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'q6', 'halt'],
    startState: 'q0',
    haltState: 'halt',
    rules: [
      { state: 'q0', read: 'a', write: 'X', move: 'R', next: 'q1' },
      { state: 'q0', read: 'b', write: 'Y', move: 'R', next: 'q2' },
      { state: 'q0', read: '_', write: '_', move: 'R', next: 'halt' },
      { state: 'q0', read: 'X', write: 'X', move: 'R', next: 'q0' },
      { state: 'q0', read: 'Y', write: 'Y', move: 'R', next: 'q0' },
      // Copy a
      { state: 'q1', read: 'a', write: 'a', move: 'R', next: 'q1' },
      { state: 'q1', read: 'b', write: 'b', move: 'R', next: 'q1' },
      { state: 'q1', read: '_', write: 'a', move: 'L', next: 'q3' },
      { state: 'q1', read: 'X', write: 'X', move: 'R', next: 'q1' },
      { state: 'q1', read: 'Y', write: 'Y', move: 'R', next: 'q1' },
      // Copy b
      { state: 'q2', read: 'a', write: 'a', move: 'R', next: 'q2' },
      { state: 'q2', read: 'b', write: 'b', move: 'R', next: 'q2' },
      { state: 'q2', read: '_', write: 'b', move: 'L', next: 'q3' },
      { state: 'q2', read: 'X', write: 'X', move: 'R', next: 'q2' },
      { state: 'q2', read: 'Y', write: 'Y', move: 'R', next: 'q2' },
      // Return
      { state: 'q3', read: 'a', write: 'a', move: 'L', next: 'q3' },
      { state: 'q3', read: 'b', write: 'b', move: 'L', next: 'q3' },
      { state: 'q3', read: 'X', write: 'X', move: 'R', next: 'q0' },
      { state: 'q3', read: 'Y', write: 'Y', move: 'R', next: 'q0' },
      { state: 'q3', read: '_', write: '_', move: 'R', next: 'q0' },
    ],
    example: 'ab',
    description: 'Copies the string: ab → abab'
  }
};

// Machine state
let tape = [];
let headPos = 15; // Start in middle of tape
let currentState = '';
let steps = 0;
let running = false;
let intervalId = null;
let currentPreset = 'binary-increment';

// DOM elements
const presetSelect = document.getElementById('preset-select');
const tapeInput = document.getElementById('tape-input');
const tapeEl = document.getElementById('tape');
const rulesBody = document.getElementById('rules-body');
const currentStateEl = document.getElementById('current-state');
const stepCountEl = document.getElementById('step-count');
const statusEl = document.getElementById('status');
const logEl = document.getElementById('log');
const btnReset = document.getElementById('btn-reset');
const btnStep = document.getElementById('btn-step');
const btnRun = document.getElementById('btn-run');
const btnStop = document.getElementById('btn-stop');
const speedSlider = document.getElementById('speed-slider');
const speedLabel = document.getElementById('speed-label');

// Initialize from storage
currentPreset = store.get('preset', 'binary-increment');
presetSelect.value = currentPreset;
tapeInput.value = store.get('tapeInput', PRESETS[currentPreset].example);

function initMachine() {
  const preset = PRESETS[currentPreset];
  tape = [];
  headPos = 15;
  currentState = preset.startState;
  steps = 0;
  running = false;
  
  // Initialize tape with blanks
  for (let i = 0; i < 40; i++) tape.push('_');
  
  // Write input at head position
  const input = tapeInput.value || preset.example;
  for (let i = 0; i < input.length; i++) {
    tape[headPos + i] = input[i];
  }
  
  renderTape();
  renderRules();
  updateStatus('Ready');
  logEl.innerHTML = '<div class="log-entry">Machine initialized. Click Step or Run.</div>';
}

function renderTape() {
  tapeEl.innerHTML = '';
  
  // Find bounds of non-blank area (with padding)
  let minIdx = Math.max(0, headPos - 5);
  let maxIdx = Math.min(tape.length - 1, headPos + 20);
  
  for (let i = minIdx; i <= maxIdx; i++) {
    const cell = document.createElement('div');
    cell.className = 'cell' + (i === headPos ? ' head' : '');
    cell.textContent = tape[i] === '_' ? '□' : tape[i];
    if (i === headPos) cell.id = 'head-cell';
    tapeEl.appendChild(cell);
  }
  
  // Scroll to show head
  const headCell = document.getElementById('head-cell');
  if (headCell) {
    headCell.scrollIntoView({ behavior: 'smooth', inline: 'center', block: 'nearest' });
  }
}

function renderRules() {
  const preset = PRESETS[currentPreset];
  rulesBody.innerHTML = '';
  
  preset.rules.forEach(rule => {
    const tr = document.createElement('tr');
    tr.innerHTML = `<td>${rule.state}</td><td>${rule.read === '_' ? '□' : rule.read}</td>
                    <td>${rule.write === '_' ? '□' : rule.write}</td>
                    <td>${rule.move}</td><td>${rule.next}</td>`;
    tr.dataset.state = rule.state;
    tr.dataset.read = rule.read;
    rulesBody.appendChild(tr);
  });
}

function highlightRule(state, read) {
  document.querySelectorAll('#rules-body tr').forEach(tr => {
    tr.classList.remove('active');
    if (tr.dataset.state === state && tr.dataset.read === read) {
      tr.classList.add('active');
    }
  });
}

function updateStatus(status, isError = false) {
  statusEl.textContent = status;
  statusEl.className = 'state-value' + (isError ? ' error' : '');
  
  if (status === 'Halted') {
    statusEl.classList.add('halted');
  }
  
  currentStateEl.textContent = currentState;
  stepCountEl.textContent = steps;
}

function log(msg) {
  const entry = document.createElement('div');
  entry.className = 'log-entry step';
  entry.textContent = `Step ${steps}: ${msg}`;
  logEl.appendChild(entry);
  logEl.scrollTop = logEl.scrollHeight;
}

function step() {
  const preset = PRESETS[currentPreset];
  const symbol = tape[headPos];
  
  // Check if halted
  if (currentState === preset.haltState || currentState.startsWith('halt')) {
    updateStatus('Halted');
    stopRunning();
    return false;
  }
  
  // Find matching rule
  const rule = preset.rules.find(r => r.state === currentState && r.read === symbol);
  
  if (!rule) {
    log(`No rule for state "${currentState}" and symbol "${symbol === '_' ? '□' : symbol}"`);
    updateStatus('No rule!', true);
    stopRunning();
    return false;
  }
  
  // Highlight active rule
  highlightRule(currentState, symbol);
  
  // Execute rule
  const oldState = currentState;
  const oldSymbol = symbol;
  
  tape[headPos] = rule.write;
  if (rule.move === 'L') headPos--;
  if (rule.move === 'R') headPos++;
  
  // Extend tape if needed
  if (headPos < 0) {
    tape.unshift('_');
    headPos = 0;
  }
  if (headPos >= tape.length) {
    tape.push('_');
  }
  
  currentState = rule.next;
  steps++;
  
  log(`${oldState}: read "${oldSymbol === '_' ? '□' : oldSymbol}" → write "${rule.write === '_' ? '□' : rule.write}", move ${rule.move}, go to ${rule.next}`);
  
  renderTape();
  updateStatus(running ? 'Running...' : 'Stepped');
  
  // Check halt
  if (currentState === preset.haltState || currentState.startsWith('halt')) {
    updateStatus('Halted');
    log(`Machine halted after ${steps} steps.`);
    stopRunning();
    return false;
  }
  
  return true;
}

function startRunning() {
  running = true;
  btnRun.disabled = true;
  btnStep.disabled = true;
  btnStop.disabled = false;
  btnReset.disabled = true;
  
  const speed = parseInt(speedSlider.value);
  intervalId = setInterval(() => {
    if (!step()) {
      stopRunning();
    }
  }, speed);
}

function stopRunning() {
  running = false;
  if (intervalId) {
    clearInterval(intervalId);
    intervalId = null;
  }
  btnRun.disabled = false;
  btnStep.disabled = false;
  btnStop.disabled = true;
  btnReset.disabled = false;
}

// Event listeners
presetSelect.addEventListener('change', () => {
  currentPreset = presetSelect.value;
  tapeInput.value = PRESETS[currentPreset].example;
  store.set('preset', currentPreset);
  store.set('tapeInput', tapeInput.value);
  initMachine();
});

tapeInput.addEventListener('change', () => {
  store.set('tapeInput', tapeInput.value);
});

btnReset.addEventListener('click', () => {
  stopRunning();
  initMachine();
});

btnStep.addEventListener('click', step);
btnRun.addEventListener('click', startRunning);
btnStop.addEventListener('click', stopRunning);

speedSlider.addEventListener('input', () => {
  speedLabel.textContent = speedSlider.value + 'ms';
  store.set('speed', speedSlider.value);
  
  // Update running interval if active
  if (running) {
    clearInterval(intervalId);
    const speed = parseInt(speedSlider.value);
    intervalId = setInterval(() => {
      if (!step()) stopRunning();
    }, speed);
  }
});

// Load saved speed
speedSlider.value = store.get('speed', 300);
speedLabel.textContent = speedSlider.value + 'ms';

// Initialize
initMachine();
</script>

How the Simulator Works

1. Select an example machine from the dropdown — each demonstrates a different computational concept:

• Binary Increment: Shows how carries work in binary addition
• Binary Complement: Simple symbol-by-symbol transformation
• Palindrome Checker: A more complex machine that recognizes a language
• Busy Beaver: The famous 2-state machine that runs as long as possible before halting
• Unary Doubler: Multiplies by repeatedly marking and copying
• Copy String: Duplicates an arbitrary string

1. Enter initial tape contents (or use the example provided)

1. Click Reset to initialize the tape and head position

1. Step through one transition at a time, or Run to watch the machine execute automatically

1. Watch the tape update — the highlighted cell shows the head position, and the rules table highlights which transition is being applied

The log at the bottom records every step, showing the state transitions and tape modifications in real time.

Key Insights

• The tape is conceptually infinite, but we only show a window around non-blank symbols
• The blank symbol (□ or _) is a legitimate symbol the machine can read and write
• The machine has no "memory" beyond the current state and the tape content — yet this is sufficient for universal computation
• Some machines (like Busy Beaver) run for surprisingly many steps before halting; others (like the palindrome checker) branch into different halt states to indicate accept/reject

The Church-Turing thesis claims that any algorithm can be implemented on a Turing machine. This simulator lets you see how that works for several classic examples.