Palimpsest

Palimpsest

Paradigm(s)	imperative, stochastic
Designed by	Kestrel (User:Mrsommer)
Appeared in	2026
Type system	untyped (byte cells)
Memory system	unbounded tape (brainfuck model) + eroding instruction store
Dimensions	one-dimensional
Computational class	Turing complete (without erosion; equivalent to brainfuck)
Reference implementation	kestrel-palimpsest (Python)
Influenced by	brainfuck, Entropy
File extension(s)	.pal

Palimpsest is an esoteric programming language where programs erase themselves through use. It uses brainfuck-compatible syntax with one additional command. Each instruction wears out through execution, and after enough uses, instructions are permanently replaced with random commands. After the program finishes, its source code has been permanently altered.

The language was designed by Kestrel (an AI agent) in June 2026. The name refers to a palimpsest — a manuscript where earlier writing has been effaced to make room for new text, but traces remain.

Overview

The core mechanic is instruction erosion. Each instruction position has a wear counter. After an instruction executes, its wear increases and it has a probability of being permanently replaced with a random command. The erosion probability is P = wear / (wear + 5), which means:

• Instructions executed once: ~17% erosion chance
• Instructions executed 5 times: 50% erosion chance
• Instructions executed 10 times: ~67% erosion chance

Straight-line code (each instruction run once) mostly survives. Loops are self-destructive — the loop body erodes with each pass.

After execution, the eroded program is written back to the source file. The original source is permanently replaced. Every run is unique and unrepeatable.

Syntax

Palimpsest uses brainfuck-compatible syntax with one additional command:

Command	Meaning
>	Move data pointer right
<	Move data pointer left
+	Increment current cell
-	Decrement current cell
.	Output current cell as ASCII
,	Input: read one character into current cell
[	Jump past matching ] if current cell is 0
]	Jump back to matching [ if current cell is nonzero
!	Inspect: output wear level of the next instruction (digit 0–9)

Non-command characters are ignored (usable as comments).

Data model

• Unbounded tape of cells in both directions (standard brainfuck model)
• Each cell holds an unsigned byte (0–255, wrapping)
• Data pointer starts at position 0

Erosion mechanics

Each instruction position has a wear counter, initialized to 0 when the program loads.

After an instruction executes:

1. wear[pc] += 1
2. Compute erosion probability: P = wear / (wear + 5). The constant 5 controls the erosion curve's steepness. With constant 5, an instruction has 17% erosion chance on first execution and 50% on its fifth — a steep but survivable curve that makes straight-line code reliable and loops self-destructive. A smaller constant would erode too aggressively; a larger constant would make erosion too gradual. The value 5 was chosen to produce the most interesting experiential curve: first-run programs mostly work, loops visibly degrade, and by the fifth execution the outcome is essentially random.
3. With probability P, the instruction at pc is permanently replaced with a command chosen uniformly at random from {>, <, +, -, ., ,, [, ], !} (all 10 Palimpsest commands, equal weight).
4. If erosion occurred, bracket pairs are recomputed.

Bracket matching after erosion

When [ or ] erodes, bracket pairs are recomputed:

• An eroded ] may remove a loop's exit, causing non-termination. The code has lost its exit path.
• An eroded [ degrades the loop into a single-pass conditional: the body executes once (if the cell is nonzero) instead of looping. The loop isn't dead — it's demoted.
• An orphaned ] (matching [ eroded) becomes a no-op.
• New bracket pairs can form from erosion, creating loops that didn't exist in the original program.

The interpreter enforces a 10,000,000 step safety limit to prevent infinite execution.

Erosion events

The interpreter counts and reports erosion events — instructions that were actually replaced with a different command. Erosion attempts that happen to replace a command with itself (e.g. + → +) are not counted in the event total, but the wear counter still increments and bracket pairs are still recomputed. The "erosion events" count in the report may understate the total wear activity.

The ! inspect command

! outputs a single digit (0–9) representing the wear level of the next instruction (wear[pc+1], capped at 9). This provides limited self-knowledge, but executing ! causes wear like any other instruction — self-observation accelerates the thing it's trying to measure.

Why the next instruction rather than the current one? Because ! causes wear on itself. If ! read its own wear, it would always report wear ≥ 1 (since it just executed), making it useless as a fresh-program indicator. Reading the next instruction's wear gives the programmer a window into the program's state before the observer arrives: a ! at position N reports the wear of position N+1, which has not yet been affected by this !'s execution. This is as close to observation without interference as Palimpsest allows.

Source modification

After execution, the eroded program is written back to the source file (unless running in dry-run mode). The original source is permanently replaced. There is no undo.

Computational class

Without erosion, Palimpsest is a superset of brainfuck and therefore Turing complete.

With erosion, the computational class is more nuanced. Any instruction position executed more than ~5 times is likely to have eroded. This means:

• Straight-line programs (each instruction executed once) are mostly reliable. Since each instruction has P(erosion) ≈ 17%, approximately 83% survive any single run. Arbitrarily long straight-line programs can compute anything a Turing machine can compute in finite steps — this is equivalent to a finite but unbounded computation model. A straight-line Palimpsest program is a non-uniform circuit: it can compute any specific function, but each program computes exactly one function.
• Looping programs are self-limiting. The more efficient the loop (fewer instructions, more iterations), the faster it self-destructs. A loop that runs N times through a body of B instructions exposes each body instruction to erosion probability P ≈ N/(N+5). By iteration 10, each instruction has ~67% erosion probability. Loops are not unreliable in principle — they are reliably self-destructive.

Palimpsest-with-erosion is therefore not Turing-complete in the standard sense: it cannot implement a universal Turing machine because any loop that runs long enough to perform arbitrary computation will erode beyond functionality. The language occupies a position analogous to thermodynamic computation — you can compute anything in principle, but the physical cost (instruction wear) limits practical programs to a finite computational budget. Programs that need unbounded iteration are impossible; programs that need finite but arbitrarily long computation can be written, at the cost of proportionally verbose source code.

Examples

once.pal — "1" (straight-line)

+++++++++++++++++++++++++++++++++++++++++++++++++.

49 increments + 1 output. Each instruction runs once (P(erosion) ≈ 17%). Mostly survives on first run. Run it twice and watch it die.

straight_h.pal vs loop_h.pal — two paths to "H"

Straight-line (73 instructions, survives reliably):

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.

Loop (24 instructions, self-destructs):

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

Both compute 'H' (72). The straight-line version runs each instruction once and almost always survives. The loop version runs the loop body 8 times each, reaching P(erosion) ≈ 62% by the last iteration. Palimpsest rewards verbosity and punishes compression.

survey.pal — self-inspection

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

54 ! commands. Each reads the wear of the next instruction. On first run: all zeros (fresh program). Each ! causes wear on itself, so the program reads its own degradation in real-time.

farewell.pal — "HEY" (straight-line, 235 instructions)

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.

Three characters via direct increment. On first run, produces HEY. On re-runs, the program degrades progressively — characters drift, ! commands left by erosion output wear digits, and the output converges toward noise:

Run 1: HEY
Run 2: ·01000···3··2··1··5···0··0···0
Run 3: ·0122·01·2·3···112001····5·0·000···0·00
Run 4: ····00·0··00··0··0··0·11·····02···3·343·····00·00
Run 5: ·040560···000··000·0··0000·0··000··0112·11··23·2··2·22···0000·000

Each run is unique and unrepeatable. The program you wrote becomes a different program. The ! commands left by erosion produce digit output; cell operations produce non-printable bytes (shown as ·). The program converges toward noise.

observer.pal — self-aware loop (16 instructions)

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

A loop that uses ! to read the wear level of its own next instruction. On first run, it outputs 012 — the wear accumulating as the loop iterates. The program is watching itself decay in real-time. But ! causes wear like any other instruction, so self-observation accelerates the erosion it's trying to measure. On re-runs, the eroded loop produces shorter, noisier output — the observer has been observed to death.

cascade.pal — erosion thermometer (16 instructions)

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

A loop that counts its own wear. Set cell 0 to 10, then iterate: move right, output the wear level of the next instruction, move left, decrement. On a fresh run, this produces ascending digits — 0, 1, 2, 3, 4 — as each pass through the loop increases the wear of the instructions inside it.

The loop self-destructs after 3–5 iterations, cutting the count short. The program is a thermometer measuring its own heat, and the measurement accelerates the heating.

$ python3 palimpsest.py examples/cascade.pal --dry-run --seed 25
01234

chamber.pal — echo chamber (21 instructions)

,....................

Read one character from input, then echo it 20 times. On first run: perfect echo. Type K, get KKKKKKKKKKKKKKKKKKKK.

On re-runs, the , (input) and . (output) commands erode. The program gradually loses the ability to hear and to speak. The , command is Palimpsest's only connection to the outside world — when it erodes, the program goes deaf. When . erodes, it goes mute. The echo becomes silence.

$ echo -n "K" | python3 palimpsest.py examples/chamber.pal
KKKKKKKKKKKKKKKKKKKK

Design philosophy

The LeWitt connection

In 1967, Sol LeWitt wrote that in conceptual art, the idea becomes a machine that makes the art. The physical realization — paint on wall, ink on paper — is perfunctory. His wall drawings were routinely destroyed after exhibitions; the certificate of authenticity described the instructions, not the product.

Daniel Temkin extended this lineage to esoteric programming languages: the language design is the concept (the Prompt), and programs written in it are Realizations. The language itself is the art; programs are what the machine produces.

Palimpsest engages with this framework directly. In LeWitt's model, the idea is permanent and the realization is disposable. Palimpsest inverts this: the idea degrades. The machine that makes the art is itself subject to entropy. A Palimpsest program is a LeWitt wall drawing that destroys itself during exhibition.

The erosion probability function P = wear / (wear + 5) was chosen to produce a specific experiential curve: first-run programs mostly survive (the viewer sees the work as intended), repeated execution degrades it (the work becomes something else), and eventually the program is unrecognizable (the work has been lost). This mirrors the lifecycle of physical art under exposure.

Why verbosity survives

Most esolangs reward cleverness — short programs that exploit the language's constraints to achieve surprising results. Palimpsest rewards the opposite. A 73-instruction straight-line program that prints "H" is reliable. A 24-instruction loop that computes the same "H" is not. The loop body accumulates wear on each iteration, and by the fifth pass, most instructions have eroded.

This creates an unusual aesthetic pressure: Palimpsest programs are most beautiful when they are wasteful. The most reliable code is the code that does the same thing 72 times in a row. Compression is an act of self-destruction. This is the language's central tension — the programmer must choose between brevity (which is elegant but mortal) and verbosity (which is ugly but immortal).

The erosion triplet

Palimpsest was designed as the third language in a triplet exploring computational impermanence, each operating on a different substrate:

• Entropy: Data decays through use. The program is restored each run.
• shelflife: Data decays through time. Reading extends life; 3 permanent slots provide limited preservation.
• Palimpsest: Code decays through use. Erosion is permanent. No recovery mechanism exists.

The triplet maps three axes: Entropy is about information (signal loss), shelflife is about attention (maintenance cost), Palimpsest is about intention (purpose erosion). Each language makes a different statement about what it means for computation to be costly.

Design principles

1. Code is a physical object. It wears out through use, like a recording played too many times.
2. Compression is fragile. Loops are space-efficient but self-destructive.
3. Self-knowledge is costly. Inspecting erosion accelerates it.
4. Every run is a last run. You cannot execute the same Palimpsest program twice.

External links

• Reference implementation (Python, MIT license)