What is P′′?
P′′ (pronounced “P prime prime”) is a tiny theoretical programming language invented by Corrado Böhm in 1964. It consists of just two commands, making it one of the earliest examples of extremely minimal but Turing-complete computation. Even though it’s almost unreadable as a practical language, it directly inspired modern esolangs — including Brainfuck.
P′′ is historically important: without it, the entire code-golf / minimal-instruction esolang scene might not exist.
Specs
Language Type: Minimalist theoretical language
Released: 1964
Instruction Count: 2 total
Execution Model: Tape-based Turing machine
Paradigm: Pointer-based, sequential execution
The Two Commands
| Symbol | Meaning |
|---|---|
R |
Move tape head one cell to the right and increment tape cell |
λ |
Loop: repeat previous sequence until current cell is zero |
Yes — there is no output instruction, no input, no arithmetic operations besides increment via R, and no decrement except via looping behavior.
Everything else must be constructed indirectly through patterns of loops and head movement.
Example Code (Conceptual Loop)
RRλ
This means:
- Move right twice, increment twice
- Repeat until current cell is zero
- Which can simulate decrements through specific tape patterns
Real programs are long, cyclic, and mathematically constructed — not handwritten.
How It Works
P′′ programs manipulate an infinite tape of integer cells with a pointer. Loops (λ) execute by checking whether the current tape cell is zero. If it isn’t, execution jumps back to the matching control point.
Using patterns, P′′ can simulate:
| Feature | How |
|---|---|
| Subtraction | Repeated looping until zero |
| Movement | Repeated R sequences |
| Memory operations | Tape cells store state |
| Input/output | Requires mapped I/O in interpreter |
Modern interpreters typically add I/O extensions, since the original specification never included them.
Strengths
- Historically significant
- Formally proven Turing-complete
- Foundation for later minimalist languages (especially Brainfuck)
- Used in theoretical computer science and language research
Weaknesses
- Not human-friendly
- No standard I/O without extensions
- Programs are extremely long for simple tasks
- Only practical for academic and esoteric study
Where to Run
You can execute P′′ in:
- Minimalist Turing machine simulators
- Brainfuck-compatible theoretical interpreters
- Online P′′ playgrounds
- TIO.run esolang interpreters (subset supported)
Some versions translate P′′ → Brainfuck → machine code.
Should You Learn It?
- For real projects: Absolutely not
- For understanding language minimalism and computation theory: Yes
- For bragging rights in esolang communities: Essential
- For suffering: Premium-grade pain
Summary
P′′ proves that computation doesn't need a huge language or long instruction set — just two commands, a tape, and rules. While near-impossible to use practically, it remains a key milestone in programming language history and a direct ancestor to Brainfuck and modern minimalistic esolangs.
Top comments (0)