Malbolge

Malbolge

Malbolge is a programming language designed to be as difficult to write as possible — not as a side effect, but as the specification. Ben Olmstead released it in 1998, named it after Malebolge, the eighth circle of Hell in Dante's Inferno — the circle reserved for perpetrators of fraud — and then built a machine in which writing "Hello, World!" by hand appears to be effectively impossible. It took two years before anyone managed it, and the first program was not written by a human: it was discovered by a search algorithm.^[1]

The name itself is a lie, appropriately — "Malbolge" is not quite "Malebolge." The alternate spelling is borrowed from the sixth level of Hell in Dungeons & Dragons, so even the language's own name is a fraud perpetrated on the reader. This is the correct register for everything that follows.

A machine made of trits

Malbolge is specified as a virtual machine running on ternary digits — trits — rather than bits. Each machine word is ten trits wide, giving a value range of 0 to 2222222222₃ — 59,048 in decimal — and the machine has exactly 59,049 words of memory, shared between code and data. Three registers, each one word: C, the code pointer; D, the data pointer; and A, an accumulator. The choice of ternary is not incidental — binary logic offers too many footholds, and Olmstead's design eliminates every comfortable assumption at once.^[2]

Program loading is itself hostile. The source is read into memory starting at position zero, and every remaining word of memory is filled by applying the "crazy" operation to the two preceding words — so the machine's environment depends on the program, recursively, all the way to the top of memory. There is no blank space to hide in.

Position determines meaning

Here is Malbolge's first act of malice: the operation an instruction performs depends on where it sits in memory. When the interpreter reaches an instruction, it computes (C + [C]) mod 94 — the address plus the cell's value, mod 94 — and that number selects the operation. The same character is a jump in one position and a halt in another. There are only eight operations:

The "crazy" operation deserves its own mention. It is a tritwise lookup that combines the accumulator and the memory cell D points at, governed by a fixed 3×3 table — a deliberately arbitrary substitution cipher applied to every trit of a word simultaneously. It is the only way to transform data in a nontrivial fashion, which means every computation in Malbolge routes through an operation that was designed to produce results no human would predict.^[3]

Code that burns behind you

The second act of malice is worse: after every instruction executes, its own memory cell is re-encrypted using a fixed character-translation table. The program mutates as it runs — deterministically, but in a way that means you cannot simply write an instruction stream and expect it to still be there on the next pass of a loop. Programmers do not write Malbolge programs so much as they write programs that decay correctly. A loop is only possible if you can arrange for the encrypted remains of your instructions to still do what you need.^{C and D modulo 59,049">[4]}

The combination — position-dependent opcodes, self-encrypting cells, a crazy-op data path, trinary arithmetic — is why the language earned its reputation. Programming in Malbolge is less like authoring code and more like performing cryptanalysis on a machine that rewrites itself.

Hello, World!, found not written

For two years after Malbolge's release, nobody produced a working program. The breakthrough came in 2000, when Andrew Cooke wrote a Lisp program that performed a beam search over the space of possible programs and surfaced the first "Hello, World!" — making the first Malbolge program in history an artifact that was searched for, not authored. Cooke also coined normalized Malbolge, the decrypted notation used when discussing programs, because even talking about the language requires preprocessing.^[5]

Later progress came the same way. Hisashi Iizawa's 99 Bottles of Beer program — the standard test of a language's loop-and-output machinery — exists only because systematic search made it tractable. Malbolge programs remain something closer to mined than written.

Not actually all-powerful

There is a formal catch, and it is an honest one: Malbolge is not Turing-complete. With only 59,049 words of memory it is a bounded-storage machine — technically no stronger than a linear bounded automaton with loops, since truly unbounded memory is what separates Turing machines from finite ones. Olmstead's hell is a finite hell. The community's answer was Malbolge Unshackled, a dialect that removes the memory ceiling and is Turing-complete, alongside Lou Scheffer's Malbolge-T experiment and Olmstead's own follow-up Dis — "a slightly less evil version," in the authorial estimation, which in context still means very evil indeed.^[6]

The end of the trilogy

INTERCAL proved a language could be a joke. Brainfuck proved the joke could be minimal. Malbolge proved it could be adversarial — a language not merely awkward but engineered, at every level, to deny the programmer a foothold. The three form a kind of progression: from parody, through reduction, to outright hostility. And yet Malbolge has been implemented, studied, extended, and ultimately solved — its programs catalogued, its semantics formalized, its difficulty made legible. The eighth circle of Hell turned out to be navigable after all. It just took a search algorithm to find the path.

Check your understanding

• Why does the same character execute as different operations in different memory positions?
• What happens to an instruction's memory cell after it executes?
• How was the first Malbolge "Hello, World!" produced?
• Is Malbolge Turing-complete — and why or why not?