Skip to content
All apps

Turing machine

About this app

Follow a tape, read/write head and transition table through binary increments, unary addition, palindrome tests and Busy Beaver examples, one rule at a time.

With explain mode: an AI tutor walks you through the app, points out what matters in the scene and answers your questions.

What a Turing machine is

The Turing machine is Alan Turing's 1936 model of everything that can be computed. It consists of an infinite tape of symbols, a head that reads and writes one cell at a time, and a finite transition table. Each rule says: in state q, reading symbol x, write y, move the head left or right and switch to state q′. When the machine reaches the halting state, the computation is finished. According to the Church–Turing thesis, every algorithmically solvable problem can be solved this way.

What the app shows

At the top runs the tape with the head, and above the head the current state, such as seek, carry or HALT. Next to it is the transition table with a row per state and a column per symbol read; the rule that applies right now lights up. A counter shows the steps. Four ready-made programs are available: binary increment, unary addition, palindrome checker and busy beaver. An info panel explains the selected program.

Try it yourself

Pick a program, set a slow speed and advance rule by rule with the step button, or let the machine run. With binary increment you see the head run to the end and carry the 1 to the left. The busy beaver shows how many ones a machine with very few states can write before it halts.

Frequently asked questions

What are the parts of a Turing machine?
An infinitely long tape divided into cells holding symbols, a read/write head, a finite set of states and a transition function. For every pair of state and symbol read, it defines what is written, where the head moves and which state comes next.
What is a busy beaver?
A busy beaver is a Turing machine with n states that starts on a blank tape, eventually halts and writes more ones or takes more steps than any other halting machine of that size. The busy beaver function grows faster than any computable function and is itself not computable.
Why is the Turing machine so important?
It makes the notion of “computable” precise. Anything a modern computer can do, a Turing machine can do in principle, only more slowly. Using it, Turing showed that some questions, such as whether an arbitrary program halts (the halting problem), cannot be decided by any algorithm.
Which programs run in the app?
Binary increment (add 1 to a binary number), unary addition, a palindrome checker and a busy beaver. You can run each one step by step or automatically at an adjustable speed and see which rule applies.

Subject: Computer science

More from Computer science

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps