Turing completeness

Turing completeness means Brainfuck can simulate any computable function given enough tape and time, with usual unbounded-memory caveats. Eight ops suffice with loops and tape.

Completeness is not convenience. Algorithms become encodings of state machines on cells. Do not confuse theoretical power with practical fitness.

Use Brainfuck for what it teaches; pick other tools to ship. Expert judgment starts here.

Sketch how you would encode a finite automaton on cells — even informally — to feel the claim.

Turing completeness means Brainfuck can simulate any computable function given enough tape and time, with usual caveats about unbounded memory. Eight ops suffice with loops and tape.

Completeness is not convenience. Algorithms become encodings of state machines on cells. Proof sketches later formalize simulation ideas.

Practical takeaway: do not confuse theoretical power with practical fitness. Use the right tool; keep Brainfuck for what it teaches.

Formal semantics pin down configurations: tape, pointer, program counter, I/O. Small-step rules explain each command. Brackets need matching definitions.

Use formalism to settle dialect arguments: write the rule for EOF you mean. Proofs later depend on this clarity.

You do not need heavy notation to benefit — even a careful plain-language state transition table is a formal practice.

Deepening turing (1): pin down input cells, output cells, and pointer home for this idiom. Write those three facts above the still. Trace values 1 and 2 until the postcondition is obvious without an interpreter.

Workbench on turing (2): every bracket is a while on a named cell. Name the control cell; drive it to zero on purpose. Infinite loops usually mean pointer drift. Re-balance moves before new arithmetic.

Portability for turing (3): document cell width, EOF, and left-edge assumptions in a header. Fixtures that need wrap fail on unbounded cells. Add a probe still for the dialect you wrote against.

Composition for turing (4): after the happy path, force failure modes — wrong home, off-by-one, unbalanced moves — and catalog symptoms. Recognition beats restarting from blank paper in larger katas.

Reading turing (5): rewrite the still with spaces and English labels, then densify again. Accidental plus or bracket characters in labels teach comment hygiene the hard way.

Assessment for turing (6): predict a tape after a short run, or name which cell a loop tests. If you can teach the still with a five-cell diagram in two minutes, you can pass the lesson cleanly.

Invariant for turing (7): state precondition and postcondition as cell equalities plus a pointer index. If either side is vague, the idiom is not ready to nest.

Numeric drill on turing (8): pick three small inputs and fill a table of resulting tapes by hand. Tables catch wrap mistakes a single example hides.

Naming for turing (9): rename cells to role words in comments — counter, acc, temp, flag, src, dst. Update when roles rotate; stale names lie.

Bracket hygiene for turing (10): indent bodies even though whitespace is ignored. Match pairs with a stack while reading dense one-liners.

Emit-as-debug for turing (11): park known letter emits at phase boundaries while building; remove markers when fixtures pass.

Stop condition for turing (12): say what makes the loop end. If you cannot, you do not control it. Zero is native false — design for it.

Caller contract for turing (13): document clobbered cells and final pointer home like an ABI. Ignoring ABI creates heisenbugs across katas.

Minimal still for turing (14): delete commands until the teaching point breaks, then put one back. Remember the minimal still, not the longest golf.

Edge cases for turing (15): try zero inputs, try one, try a value near 255 on byte cells. Boundaries reveal wrap and loop mistakes early.

Refactor note for turing (16): after it works, rename temps and rebalance moves for readability before you nest this idiom inside a larger program.

Teach-back for turing (17): explain the still to an empty chair with only a five-cell diagram. Hesitation marks the exact gap to restudy.

History of practice for turing (20): the first time you get this wrong, write the mistaken tape beside the correct tape. The diff is the lesson. Keep a scrap log of diffs for this topic.

Scaling turing (21): once the tiny example works, scale counters to 5 and 7 before you leap to ASCII sizes. Medium numbers catch off-by-ones without drowning you in pluses.

Interleave for turing (22): alternate one minute of tracing with one minute of typing the still from memory. Retrieval practice beats passive rereading for command sequences.

Negative space for turing (23): list what the idiom does not do — no implicit moves, no implicit clears, no decimal printing. Negatives prevent false expectations.

Fixture seed for turing (24): invent one expected output string or final cell vector. Even a private fixture makes later golf honest instead of theatrical.

Pointer chant for turing (25): after each opcode in the still, say the index aloud. Embarrassment is cheaper than an hour lost on a drifted home.

Algebra ban for turing (26): do not commute moves past mutations on paper. Expand, then simplify only with a completed trace underneath.

Legend freeze for turing (27): before changing code, freeze the cell role map. If the map must change, update comments in the same edit or you will debug ghosts.

Two-interpreter rule for turing (28): when possible, run the still on a second dialect. Divergence teaches width and EOF faster than essays.

Exit ticket for turing (29): write one quiz question you wish this lesson had asked, with the answer. Teaching the topic is proof of learning.

# TC: tape+[] enough to encode machines

Human reminder sitting beside real stills in your notes.

Next: self-interpreters.