Why eight commands are enough

What "Turing complete" means

In 1936 Alan Turing described a very simple imaginary machine: a tape of squares, a head that reads and writes one square at a time, and a fixed table of rules. He argued that whatever can be worked out by following exact rules can be worked out by such a machine [4]. Nothing found since has been able to compute more. Laptops, phones and supercomputers are faster, and can compute exactly the same things.

A programming language is called Turing complete when it can do everything such a machine can do. Then it can also do everything any other language can do, because each can imitate the other. Python, C and JavaScript are Turing complete. So is brainfuck.

Müller made the claim in the README of 1993: the language "can compute every solvable mathematical problem (if we ignore the array size limit and the executable size limit)" [5]. Both halves of that sentence matter, and the second half is the subject of The proofs, and what they assume.

Why so little is enough

To imitate a Turing machine a language needs three things: a memory without a fixed end, a way to change it step by step, and a way to do different things depending on what it finds there. Brainfuck has exactly these and little else. The tape is the memory. + - < > change it. The loop is both "repeat" and "decide".

The program below decides: it prints 1 if the letter you type is an a, and 0 for anything else. Type a letter, press Play, and watch cell 1, which starts as 1 and is set back to 0 only if the loop in the middle runs:

The program takes 97, the code of "a", off the character it read. If the result is 0 the letter was an "a". Then comes the decision: cell 1 is set to 1, and a loop on cell 0 sets it back to 0. That loop runs only when cell 0 is not 0. So a loop that runs at most once is an "if". With "if", "repeat" and a memory you can build comparison, arithmetic, tables and everything else. The patterns section shows the pieces, each on its own page. The "if" of this program is the pattern If non-zero.

Two of the eight commands are not needed for this at all. . and , only let a program talk to the outside. The six others carry the whole power, and they match the six symbols that Corrado Böhm used in 1964 for his language P′′ [3] [6]. Böhm proved then that this is enough [6].

The proofs, and what they assume

A proof of Turing completeness shows how to imitate something already known to be Turing complete. For brainfuck there are several, and they differ in what they need to be unlimited (the table below).

The pattern in the table is the important part. With a tape that never ends, small cells are enough: even cells of one bit will do, as the language Boolfuck shows [7]. With cells that can hold any number, three cells are enough. But something must be unlimited.

So is a real implementation Turing complete?

Strictly, no. An implementation with 30,000 cells of one byte has a fixed, finite number of possible states. It is a very large finite machine, not a Turing machine. Müller's proviso says exactly that: "if we ignore the array size limit" [5].

The same is true of every computer ever built. Each has a fixed amount of memory. We call them general-purpose because the memory is large enough for the task at hand and more can be added. For brainfuck the fair statement is the same: the language is Turing complete, and an implementation can run any computation that fits on its tape. Implementations whose tape grows as needed come as close as a real machine can.

What it does not mean

Not: fast

Turing completeness counts no steps. A brainfuck program may need a million steps for what another language does in one. See What brainfuck teaches about real computers.

Not: easy

That a program exists does not help you find it.

Not: able to do everything a computer does

Computing and doing are different. A brainfuck program reads characters and prints characters. It cannot open a file, show a picture or use a network, because the language has no command for it. It can compute what should be in the file or the picture, if something else does the rest.

Not: predictable

Turing showed that no method can decide, for every program, whether it will ever stop [4]. That holds for every Turing-complete language, so it holds for brainfuck with an unlimited tape. There is no tool that can look at any brainfuck program and say whether it ends.

Being Turing complete is not rare either: most programming languages are. What makes brainfuck special is how little it needs and how plainly you can see it.

The Turing tarpit

In 1982 the computer scientist Alan Perlis published a list of short remarks on programming. Number 54 reads [8]:

It reads as a warning to people who design languages and systems: being able to do anything in principle is worth little if every useful thing is hard. He wrote it eleven years before brainfuck existed.

Since then the phrase has become a name. Small languages that are Turing complete with as few parts as possible are called "Turing tarpits" [9] [10], and brainfuck is the usual example. The difference is that these languages walk into the tar-pit on purpose. What Perlis warned against, they are made to explore: how little is needed, and what it is like to work with only that.

What brainfuck teaches about real computers

A real processor is closer to brainfuck than to the languages people write in. That is why the language is good for learning what happens underneath.

Memory is a row of numbered cells

A computer's memory is a long row of bytes, each with a number: its address. Variables with names are a convenience that a compiler turns into addresses. In brainfuck you do that work yourself: you decide which cell holds what.

A pointer is a position

The pointer is the one address the machine is looking at. Getting to data means moving there, and moving costs steps. Keeping things that are used together close together makes a program faster, on a brainfuck tape and in a real machine.

Everything is numbers

A letter is a number, and so is a truth value. What a number means is decided by the program that uses it.

Arithmetic goes round

A cell has a largest value, and one more than that is 0. Real processors count in the same way, with 32 or 64 bits instead of 8.

Control is a jump with a test

A processor has no "while" and no "if". It has "go to another place in the program if this number is zero". The two brackets are exactly that.

Using a number can destroy it

A loop that adds cell 0 to cell 1 leaves cell 0 empty. To keep the number you make a second copy at the same time and move it back. Real machines copy for the same reason; they only make it look free.

Everything has a cost

Multiplying is adding again and again, and adding is counting. In brainfuck you see every step.

The program below multiplies two numbers with a loop. Under the cells are the number of steps of the run, counted one command at a time and with simple loops merged. Make the numbers larger and watch both counts:

One command at a time, eight times eight takes 105 steps, and sixteen times eight about twice as many; the merged count hardly moves. The loop has a simple shape, and a program that runs brainfuck can recognise the shape and do the whole multiplication in one operation. The result is identical. This is the main idea behind every fast implementation: see Implementations.

How large the costs get is easy to underrate. The chat models of this site need division, rounding and table look-ups many millions of times. Done by plain counting, one division with rounding took 1.2 to 1.5 million steps; built from loops of the simple shape it takes about 100 measured [11]. Even so, one word piece of an answer from brnfck-smollm2-135m costs 1.6 to 1.9 billion steps measured [11].

Limits

• This is an explanation, not a proof. The proofs are in the sources named in the table of proofs.
• We did not read Böhm's paper of 1964, Rogozhin's of 1996 or Turing's of 1936. We rely on the descriptions cited.
• The three-cell result is reported from the Esolang wiki alone.

Read next

• ImplementationsHow the steps are carried out, and how the slow ones are made fast.
• Writing real programsHow people actually build things from these parts.
• PatternsDeciding, copying, comparing: the building blocks, runnable.

Notes and sources

Where a source is a community wiki or the author's own account, the entry or the text says so.

1. Frans Faase, "BF is Turing-complete": the proof page on iwriteiam.nl. Opened 11 October 2026.
2. Daniel B Cristofani, utm.b: the universal Turing machine on brainfuck.org. Its comments name the machine it implements: Yurii Rogozhin, "Small universal Turing machines", Theoretical Computer Science 168(2) (1996), 215 to 240, which we did not open. Opened 11 October 2026.
3. Esolang wiki, "Brainfuck": the wiki article on brainfuck. A community wiki; we use it for conventions and for its list of results, and name it where it is our only source. Opened 11 October 2026.
4. Wikipedia, "Halting problem": the Wikipedia article on the halting problem. Our source for the statement of Turing's result (A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 1936 to 1937), which we did not open. Opened 11 October 2026.
5. Urban Müller, brainfuck-2.lha, Aminet, dev/lang, dated 9 June 1993: the package page on Aminet. We read the files in the archive: README, bfc.asm (the compiler), bfi.c (the interpreter) and the six example programs. Sizes and dates are those of the archive listing. Opened 11 October 2026.
6. Wikipedia, "P′′": the Wikipedia article on P′′. Our source for Corrado Böhm, "On a family of Turing machines and the related programming language", ICC Bulletin 3 (1964), 185 to 194, and for C. Böhm and G. Jacopini, "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules", Communications of the ACM 9(5) (1966), 366 to 371. We did not open the two papers themselves. Opened 11 October 2026.
7. Esolang wiki, "Boolfuck": the wiki article on Boolfuck. Opened 11 October 2026.
8. Alan J. Perlis, "Epigrams on Programming", ACM SIGPLAN Notices 17(9), September 1982, read in the copy at Yale: the epigrams at cs.yale.edu. Opened 11 October 2026.
9. Esolang wiki, "Esoteric programming language": the wiki article on esoteric languages. Opened 11 October 2026.
10. Michael Mateas and Nick Montfort, "A Box, Darkly: Obfuscation, Weird Languages, and Code Aesthetics", Proceedings of the 6th Digital Arts and Culture Conference, IT University of Copenhagen, 1 to 3 December 2005, pages 144 to 153: the paper on nickm.com (PDF). Opened 11 October 2026.
11. This site's own project. Counts and measurements are on How it works: the numbers and How do I know it is real?; the earlier work we know of is under Has this been done before?. Opened 11 October 2026.