BrainSwitch

BrainSwitch

Paradigm(s)	imperative
Designed by	User:AndrewBayly
Appeared in	2026
Memory system	Cell-based
Dimensions	one-dimensional
Computational class	Turing complete
Reference implementation	reference interpreter (JavaScript, runs in-browser)
Influenced by	Brainfuck
File extension(s)	.bsw

BrainSwitch is a Brainfuck derivative in which the meanings of + and - swap whenever the current cell holds a prime number. Every other instruction is identical to Brainfuck's. This one change is small to state and unusually disruptive in practice: to know what + will actually do, the programmer must already know, at that exact point in execution, whether the current cell's value is prime — and since every arithmetic instruction can change that fact, this knowledge has to be tracked through the entire execution history of a cell, not just its current state.

Language overview

BrainSwitch runs on the same memory model as Brainfuck: a tape of byte cells (0–255, wrapping on overflow and underflow), unbounded in both directions, all initialized to zero, with a single data pointer.

The commands:

Command	Meaning
>	Move the data pointer right.
<	Move the data pointer left.
+	If the current cell is prime, decrement it; otherwise, increment it.
-	If the current cell is prime, increment it; otherwise, decrement it.
.	Output the current cell as an ASCII character.
,	Input a byte and store it in the current cell.
[	Jump past the matching ] if the current cell is 0.
]	Jump back to the matching [ if the current cell is nonzero.

All characters other than ><+-.,[] are comments and are ignored — with one practical wrinkle worth flagging for anyone writing BrainSwitch by hand: since . and , are live instructions, ordinary prose comments can't contain a period or a comma without accidentally inserting I/O operations into the program.

The [ and ] brackets are ordinary zero/nonzero tests on the raw cell value — primality has no bearing on them. This turns out to matter a great deal for the language's computational class.

Primality convention

0 and 1 are not prime. 2, 3, 5, 7, 11, ... are prime, using the standard definition. The 54 primes in the byte range (0–255) are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
241, 251

255 (the top of the byte range) is composite (3×5×17), so an overflow from 255 always wraps to 0 the ordinary way; the wrap and the primality check don't interact.

Input/output and end-of-file behavior are left implementation-defined, in keeping with Brainfuck convention; a common choice (used by the reference interpreter) is for an unread , past the end of input to leave the current cell as 0.

The core difficulty

Because 2 is prime, naively counting upward with repeated + from a fresh cell does not do what a Brainfuck programmer would expect:

++++

Cell value 0 (not prime) → + increments → 1 Cell value 1 (not prime) → + increments → 2 Cell value 2 (prime) → + decrements → 1 Cell value 1 (not prime) → + increments → 2

The cell oscillates forever between 1 and 2; a run of + can never climb past 2 on its own. Escaping the trap means picking, at each step, whichever of + or - currently means "increment" — which depends on the value the previous step left behind. A hand-verified sequence that reliably counts from 0 up to 10:

++--+-+-++

(+, +, then -, - once the cell hits 2, then alternating based on primality the rest of the way — 0→1→2→3→4→5→6→7→8→9→10.)

Because every value from 0 up to whatever target you want has a statically-known, fixed primality pattern, any specific, fixed target value can always be reached this way by precomputing the right operator sequence offline. What's genuinely hard is reaching a value that isn't known until runtime (see below), since that would require testing a cell's primality during execution, and BrainSwitch has no primitive for that — only the zero/nonzero test that [ and ] already provide.

Printing arbitrary numbers in decimal remains, as far as is currently known, unsolved in BrainSwitch, for exactly this reason: it would require reliably reaching a value that depends on program input.

Computational class

BrainSwitch is Turing-complete. The cleanest proof is a reduction from Boolfuck, which operates on a tape of single bits and is itself known to be Turing-complete by reduction from Brainfuck.

The idea: restrict every cell used in the simulation to hold only 0 or 1. Since neither value is ever prime, this fact is knowable at translation time, with no runtime primality test required — which sidesteps the difficulty described above entirely.

One subtlety is worth being explicit about. It's tempting to say "0 and 1 are never prime, so + is a safe bit-flip" — but that's not quite right. On a cell holding 1, plain + increments it to 2, immediately leaving the safe range (and 2 is prime, so the very next operation on that cell starts swapping unexpectedly). A true bit-flip has to be conditional: increment if the cell is 0, decrement if it's 1. That can't be a single instruction; it needs a short subroutine using BrainSwitch's zero-test brackets to branch.

Conveniently, such a subroutine already exists and needs no adaptation: it's the standard gadget used to compile Boolfuck's + (an unconditional bit-flip) down to plain Brainfuck, given on the Brainbool page's Boolfuck–to–Brainfuck conversion table:

>+<[->-<]>[-<+>]<

Every cell this gadget ever touches — the data bit and one scratch cell — holds only 0 or 1 at every point during its execution, so it behaves identically whether run as plain Brainfuck or as BrainSwitch; the prime-swap simply never triggers. This was checked directly against a BrainSwitch interpreter: applied to a 0 cell it produces 1 (scratch cell returned to 0); applied to a 1 cell it produces 0 (scratch cell returned to 0); applied five times in a row to a fresh cell it alternates 1, 0, 1, 0, 1 with the scratch cell clean after every application. It was also checked composed inside a loop body and chained across multiple interleaved cells, with the same clean result.

With that gadget available, a full reduction from Boolfuck is mechanical:

• Represent each Boolfuck cell as a pair of BrainSwitch cells, (data, scratch).
• Boolfuck < / > → BrainSwitch << / >> (stride 2, to skip the scratch cell).
• Boolfuck [ / ] → unchanged. They are pure zero-tests, and BrainSwitch never lets primality affect bracket semantics.
• Boolfuck + (bit-flip) → the gadget above.
• I/O is not needed for the Turing-completeness argument itself and can be omitted; giving it full byte-level fidelity would mean packing/unpacking bits into bytes, which looks solvable using the same "precompute a fixed operator sequence for a statically-known target value" trick used for the decimal-digit problem above, but hasn't been built.

Chaining reductions: a Turing machine reduces to Brainfuck (classical result); Brainfuck reduces to Boolfuck (see Boolfuck#Computational_class); Boolfuck reduces to BrainSwitch (above). Hence BrainSwitch is Turing-complete.

A separate variant — swapping < and > instead of + and -, keyed on whether the pointer position is prime rather than the cell value — was considered during design and abandoned. It was believed to break Turing-completeness, and was found to be unworkable in practice regardless: Brainfuck has no if/else construct, which makes prime-aware navigation difficult to implement even for finite, bounded tasks.

Examples

The prime trap

A minimal illustration of the core difficulty: starting from a fresh cell, this oscillates between 1 and 2 forever and never climbs any higher.

++++

Counting reliably to ten

A hand-verified escape from the trap above, using the fact that every value from 0 to 10 has a fixed, precomputable primality:

++--+-+-++

Cat program

Since . and , never touch primality, ordinary I/O idioms carry over from Brainfuck unchanged:

,[.,]

Printing binary counter

A genuine, unbounded binary counter that prints its own value in binary (1, 10, 11, 100, ...) after every increment, verified correct against true (unpadded, untruncated) binary representations for tens of thousands of consecutive counts. It represents the number as a chain of growing "blocks" extending across the tape, one block per bit, each holding: whether the block exists yet, the cached ASCII code for '1', the cached ASCII code for '0', and the bit's current value. Caching the ASCII codes at the moment each block is created — rather than rebuilding them via a reliable-increment sequence on every print, the way a naive implementation would — is what makes printing after every single increment practical rather than prohibitively slow.

+[<<<<<<[-<<<<<<]<[<<<+<+>>>>-]<<<<[>>>>+<<<<-]+>[<->-]<[>>>>+<++--+-+-+++-+-+++-+-+++-+++++-+-+++++-+++-+-+++-+<++--+-+-+++-+-+++-+-+++-+++++-+-+++++-+++-+-+++-<<-]>>>>>+>>>>>>-[+>>>>>>-]+<<<<<<<[<<<<<<]>>>>>>[>[<<<<+<+>>>>>-]<<<<<[>>>>>+<<<<<-]>[>>.<<-]>>>>[<<<<<+>+>>>>-]<<<<[>>>>+<<<<-]+<[>-<-]>[>.<-]>>>>>>>>>]>>++--+-+-++.---+-+-++-<]

Since almost every character in a BrainSwitch program is a live instruction (only whitespace and letters are safe as comments, and even then not near a stray . or ,), programs built by this kind of construction tend to arrive with no inline commentary at all; the accompanying prose has to carry the explanation instead of the source.

History

BrainSwitch sits alongside BrainFreeze as a Brainfuck variant exploring a single, deliberately disruptive constraint: where BrainFreeze imposes a spatial constraint (a 2D path), BrainSwitch imposes a semantic one (primality-dependent operation meaning). Both are Turing-complete, and both make otherwise-trivial Brainfuck idioms substantially harder to write.

Related languages

• Brainfuck — the base language; BrainSwitch changes only the meaning of + and -.
• Boolfuck — used as the target of the Turing-completeness reduction above.
• Brainbool — source of the Boolfuck-to-Brainfuck bit-flip gadget reused (unmodified) in the reduction.
• BrainFreeze — a sibling language applying a different kind of constraint (2D movement) to the same base.