Turing completeness in 2D

This is Befunge · Expert, lesson 1: Turing completeness in 2D. Medium gave you diamonds, p/g, and a working adder. Expert asks what the machine can compute — and what it costs.

A language is Turing-complete when it can simulate any computable function given enough memory and time. Classic claims for Befunge rest on the stack, the playfield as mutable storage, and an instruction pointer that walks a 2D torus.

Honest caveat for Befunge-93: the playfield is fixed at 80×25 cells. Finite storage alone is not enough for textbook Turing completeness. With unbounded stack word size, researchers have shown Befunge-93 can still encode powerful machines — but the finite grid is a real limit you must name.

Power is not convenience. Encoding a state machine across stack depths and playfield cells is possible; shipping a payroll system in it is a joke with a serious punchline about tool choice.

The three actors: stack (LIFO values), playfield (80×25 ASCII cells, code and data share the same space), IP (position + cardinal direction, wrapping toroidally). Completeness arguments braid all three.

Self-modification (p) turns the playfield into writable tape for control flow, not only data. That is why expert programs feel like hardware: the road rewrites itself.

Wrap is topology, not a bug. Leaving column 79 eastbound reappears at column 0 on the same row. Expert designs either harness wrap or forbid surprise crossings with walls of direction glyphs.

Self-check: can you name one reason Befunge-93 is almost TC and one reason the fixed grid argues otherwise? If both sentences are clear, you own the nuance.

Hold Turing completeness in 2D as a behavior, not a vocabulary flashcard. Ask: what inputs matter, what action runs, what is visible afterward? If you cannot fill those three slots, you are skimming. Write them in a margin before the quizzes.

When something fails around Turing completeness in 2D, change one thing. Read the wrong output. Return to the still. Do not rewrite the whole playfield when one cell is wrong. Calm retries beat dramatic rewrites.

Compare Turing completeness in 2D with the nearest habit you know from C, Python, or Forth — and name the difference out loud. Befunge's teaching value is often the delta: familiar family, different ergonomics.

Open-book checks for Turing completeness in 2D reward careful reading of this page. The right answer is a claim we actually made about Befunge-93. Near-miss choices sound technical; they fail because they invert the lesson.

Before the still, predict IP position, direction, and stack. After the still, compare. That predict-compare loop is how Turing completeness in 2D becomes muscle memory.

Say a one-sentence teaching version of Turing completeness in 2D you could give a friend. If the sentence needs five caveats, your mental model is still foggy — tighten it.

Keep a scratch note for Turing completeness in 2D: one worked example, one failure you fixed, one sentence of definition. That tiny notebook beats highlighting the same paragraph five times.

Wrong answers on Turing completeness in 2D quizzes are teachers too. Read the explain line. Relate it back to the still. A corrected misconception sticks harder than a lucky first guess.

Host-teacher note for Turing completeness in 2D: I will not rush you, but I will not dilute the subject either. Read once for the story, once for the mechanism, once with the still under your finger. Three passes beat one skim.

Edge inventory for Turing completeness in 2D: list one normal case, one boundary case, and one misuse. Boundaries and misuses are where quizzes live and where playfield bugs breed.

Transfer test for Turing completeness in 2D: explain it to a skeptical friend who only knows Python. If they can predict the still's effect from your explanation, you own it.

Practice drill for Turing completeness in 2D: change one cell in the still by a small delta, recompute the expected stack and IP by hand, then confirm. Single-delta drills expose off-by-ones faster than rereading.

Invariant for Turing completeness in 2D: state precondition and postcondition as stack shape plus IP direction. If either side is vague, the idiom is not ready to nest.

Numeric drill on Turing completeness in 2D: pick three small inputs and fill a table of resulting stacks by hand. Tables catch wrap and pop-order mistakes a single example hides.

Naming for Turing completeness in 2D: label lanes TRUE/FALSE/JOIN on graph paper even though the playfield has no labels. Update when lanes rotate; stale labels lie.

Stop condition for Turing completeness in 2D: say what makes the path halt or rejoin. If you cannot, you do not control it. @ is native halt — design for it.

Minimal still for Turing completeness in 2D: delete commands until the teaching point breaks, then put one back. Remember the minimal still, not the longest golf.

Teach-back for Turing completeness in 2D: explain the still to an empty chair with only a stack sketch. Hesitation marks the exact gap to restudy.

Negative space for Turing completeness in 2D: list what the idiom does not do — no implicit pops, no free direction memory, no automatic rejoin. Negatives prevent false expectations.

Pointer chant for Turing completeness in 2D: after each opcode in the still, say the direction and top-of-stack aloud. Embarrassment is cheaper than an hour lost on a drifted IP.

# TC: stack+playfield+IP; 80x25 grid is finite

>67*@

Trace >67*@: IP goes east, pushes 6 then 7, multiplies to 42, halts. Tiny, finite, honest. Expert work builds denser machines on the same three actors.

Pitfalls: claiming unbounded tape without naming the 80×25 limit; equating TC with “good for production”; forgetting the IP direction is part of machine state; treating wrap as optional.

Power framed. Next: treat p/g as first-class program design, not a parlor trick.