Lesson 4 of 4 — Turing machines

Mechanical Moves

Before a step is “elementary”, it is mechanical: read one symbol, write one symbol, move one cell, change state. The machine below runs Turing programs — lists of five-part commands, the notation my computability students write their first machines in — and every exercise asks what the machine will do before it does it. The running-time lesson takes the number of these moves as its starting definition and then trades them for elementary steps; this is the lesson where you can watch them.

Six exercises, about ten minutes. Progress is saved in this browser.

About the tool. In my computability course the students use Varphi, a description language and debugger for Turing machines built by my student Hassan El-Sheikha under my supervision and described in two WCCCE papers (2025, 2026); its documentation is at docs.varphi-lang.com. This page is a browser-sized cousin: the same conventions and the same habit of stepping a configuration at a time, with a fraction of the features.

The conventions

Numbers are unary. The input n is written as n + 1 ones (so that 0 has a shape), several inputs are separated by single blanks, and the head starts on the leftmost 1. The output is whatever number of 1s is left on the tape when the machine halts. A command is five parts:

commandq1 1 q2 1 R — in state q1 reading 1: go to q2, write 1, move R.

startstate q1, head on the leftmost 1.

haltentering q0. If no command matches the current state and symbol, the machine jams: it stops with no output.

symbols1 and the blank b. Nothing else.

The machine

Edit the program, set the inputs, then step or run. The log shows each configuration the way the course writes them: state, then tape, with the symbol under the head marked.

Program

Inputs (comma-separated)

What a program is

The machine has no arithmetic, no loops and no variables. It has a state, and a rule for every state-and-symbol pair it expects to meet. Everything it “knows” is which state it is in; everything it “sees” is one cell. That is enough to add, multiply, search, and run every program on this site — only slowly, and with every step out in the open where it can be counted.

That last part is why the running-time lesson points here. It defines the cost of a run as the number of mechanical moves the machine needs and then counts elementary steps instead, because nobody counts moves for a real program. Here the moves are the whole story: each one is on the screen, and the counter beside the state badge is T(P, x) itself.

Exercise bank

Four kinds of exercise, checked by actually running the machine. A solved card stays solved but keeps working.

PredictParameter playBreak itQuiz

Progress 0 of 6