Malbolgeは1998年にBen Olmsteadによって開発された、パブリックドメインの難解プログラミング言語である。名前は、ダンテの神曲地獄篇における地獄の第8圏であるマーレボルジェ(Malebolge)にちなんで名付けられた。

Malbolgeはチューリング完全であるが、実用言語ではない。Malbolgeの異常な点は、最悪の、すなわち最も扱いにくく難解であるプログラミング言語となるべく設計されたことである。MalbolgeはINTERCAL、機械語、Brainfuckの最悪な部分を組み合わせたものであるという。しかし、理解を困難にするために用いたトリックのいくつかはごく単純化することができる。

 Malbolgeでのプログラミング 
プログラミング言語Malbolgeが世に出たとき、理解することが非常に難しく、最初に書かれたプログラムが出現するのに2年を要した。しかもそのプログラムは人間によって書かれたものではなく、Andrew Cookeが設計しLISPで実装したビーム探索アルゴリズムにより生成したものだった。

2000年8月24日、Anthony Youhasは彼のブログでMalbolgeを打ちのめし解決の鍵を極めたと宣言し、様々な語句を表示する3つのMalbolgeプログラムコードによりその証拠とした。しかし、どのような技法を用いたかは明らかにはしなかった。

後にLou Schefferは、Malbolgeはプログラミング言語というより暗号システムとして見るべきであり、暗号システムとして見た場合のMalbolgeにはいくつかの脆弱性があると指摘した。また、これらの脆弱性を突くことでMalbolgeプログラムを書くことができるとし、例として入力された文字を出力するプログラムを示した。

OlmsteadはMalbolgeが線形拘束オートマトンであると考えていた。

Malbolgeのプログラム難読化への応用可能性に着目した名古屋大学の酒井正彦らにより、3段階の中間言語やSATソルバを用いてMalbolgeプログラムを生成する手法が提案されている。これらの研究成果を用いて、while文や配列、再帰関数などを含むC言語のサブセットをMalbolgeプログラムにコンパイルすることが可能となっている。

 Malbolgeで書いたHello, worldプログラム 
次のMalbolgeプログラムは"Hello, world"を出力する。

<nowiki>
(=<`:9876Z4321UT.-Q+*)M'&%$H"!~}|Bzy?=|{z]KwZY44Eq0/{mlk**
hKs_dG5[m_BA{?-Y;;Vb'rR5431M}/.zHGwEDCBA@98\6543W10/.R,+O<
</nowiki>

 設計 
Malbolgeは三進仮想マシンであるMalbolgeインタプリタ用の機械語である。

標準のインタプリタと公式の仕様が完全には一致していない。コンパイラは33–126の範囲外のデータにおいて実行を停止させるという違いがある。これは当初はコンパイラのバグとされていたが、Ben Olmsteadはこれを意図した動作であり、実際には「仕様のバグ」であるとした。

 レジスタ 
Malbolgeにはa、c、dの3つのレジスタがある。プログラムの開始時点では、3つのレジスタの値はすべて0である。

aはアキュムレータ (Accumulator) の略であり、メモリへの書き込み命令や標準入出力に使われる。cはコード (Code) ポインタであり、現在の命令を指すプログラムカウンタである。dはデータ (Data) ポインタである。各命令後に自動的にインクリメントされるが、これが指す場所はデータ操作コマンドにしか使われない。

 ポインタの表記 
dはメモリアドレスを表す。[d]はレジスタ間接、すなわちそのアドレスに格納された値を表す。[c]についても同様。

 メモリ 
仮想マシンは59,049 のメモリ空間を持ち、それぞれ10桁の三進数を格納することができる。各メモリ空間には0から59048までのメモリアドレスが割り当てられ、0から59048までの値をとることができる。この上限を超えてインクリメントした場合、0に戻る。

この言語ではデータと命令が同じメモリ空間を使用する。これはx86アーキテクチャなどのハードウェアの仕組みに影響されている。

Malbolgeのプログラムが始まる前に、メモリの初めの部分はプログラムで埋められる。プログラム中のホワイトスペースはすべて無視され、そのほかはすべて下記の命令のいずれかで始まらなければならない。これはプログラミングをより難しくするためのものである。

メモリの残りは前2つのアドレスに対するcrazy演算（後述）で埋められる ([m] = crz [m - 2], [m - 1])。この方法で埋められたメモリは12アドレスごとに繰り返しのパターンになる。

Ørjan JohansenはMalbolgeの精神をできる限り維持したうえでチューリング完全な言語を作りたいと考え、2007年にメモリ制限の無いバージョンであるMalbolge Unshackledを開発した。それ以外のルールは変わっていないため、メモリ制限に達していない通常のMalbolgeのプログラムもすべて完全に動く。

 命令 
Malbolgeには8つの命令がある。どの命令を実行するかを決めるために、[c]の値にcの値を加え、94で割った余りを用いる。計算結果と実行する命令の対応は下表のとおり。

+ 命令 命令 説明 4 [d]の値をcに代入する。この命令の実行後にcをインクリメントするため、次に実行されるのは ([d] + 1 (modulo 59049)) 番地の命令である。 5 aの値をASCII文字として画面に出力する。 23 入力された文字のASCIIコードをaに代入する。改行は10、ファイル終端は59048を代わりに代入する。 39 [d]の値を1桁回転させる（0002111112が2000211111になる）。結果を[d]とaに代入する。 40 [d]の値をdに代入する。 62 [d]の値とaの値のcrazy演算（後述）をする。結果を[d]とaに代入する。 68 何もしない。 81 Malbolgeプログラムを終了する。 （上記以外） 68と同じ（何もしない）。上記以外の値はプログラムのロード直後には許されないが、実行中には許可される。

各命令が実行された後、[c]を暗号化（後述）する。これにより暗号化される命令は、ジャンプ命令が実行された場合はジャンプ先の命令、そうでない場合は実行された命令である。暗号化により、次に同じ番地に処理が戻ってきても違う処理がされる。暗号化の後、cとdが1増え、次の命令が実行される。

 crazy演算 
入力の三進数における桁ごとに、下表を用いて結果を求める。例として、crz 0001112220, 0120120120は1001022211である。

+ crazy演算 crz 入力2 0 1 2 入力1 0 1 0 0 1 1 0 2 2 2 2 1

暗号化
各命令の実行後、cをインクリメントする前に、[c]の値を ([c] mod 94) に置き換える。その後、結果を以下に示す等価な2つの方法でする。

 方法1 下記において、結果に対応する文字のASCIIコードを[c]に代入する。
 0000000000111111111122222222223333333333444444444455555555556666666666777777777788888888889999
 0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123
 ----------------------------------------------------------------------------------------------
 9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb

 方法2 下表において、結果に対応する暗号を[c]に代入する。

+ 暗号表 結果 暗号 結果 暗号 結果 暗号 結果 暗号 結果 暗号 0 57 19 108 38 113 57 91 76 79 1 109 20 125 39 116 58 37 77 65 2 60 21 82 40 121 59 92 78 49 3 46 22 69 41 102 60 51 79 67 4 84 23 111 42 114 61 100 80 66 5 86 24 107 43 36 62 76 81 54 6 97 25 78 44 40 63 43 82 118 7 99 26 58 45 119 64 81 83 94 8 96 27 35 46 101 65 59 84 61 9 117 28 63 47 52 66 62 85 73 10 89 29 71 48 123 67 85 86 95 11 42 30 34 49 87 68 33 87 48 12 77 31 105 50 80 69 112 88 47 13 75 32 64 51 41 70 74 89 56 14 39 33 53 52 72 71 83 90 124 15 88 34 122 53 45 72 55 91 106 16 126 35 93 54 90 73 50 92 115 17 120 36 38 55 110 74 70 93 98 18 68 37 103 56 44 75 104

Lou SchefferによるMalbolgeの暗号解析において、以下に示す6種類の置換サイクルが示されている。

 33 ⇒ 53 ⇒ 45 ⇒ 119 ⇒ 78 ⇒ 49 ⇒ 87 ⇒ 48 ⇒ 123 ⇒ 71 ⇒ 83 ⇒ 94 ⇒ 57 ⇒ 91 ⇒ 106 ⇒ 77 ⇒ 65 ⇒ 59 ⇒ 92 ⇒ 115 ⇒ 82 ⇒ 118 ⇒ 107 ⇒ 75 ⇒ 104 ⇒ 89 ⇒ 56 ⇒ 44 ⇒ 40 ⇒ 121 ⇒ 35 ⇒ 93 ⇒ 98 ⇒ 84 ⇒ 61 ⇒ 100 ⇒ 97 ⇒ 46 ⇒ 101 ⇒ 99 ⇒ 86 ⇒ 95 ⇒ 109 ⇒ 88 ⇒ 47 ⇒ 52 ⇒ 72 ⇒ 55 ⇒ 110 ⇒ 126 ⇒ 64 ⇒ 81 ⇒ 54 ⇒ 90 ⇒ 124 ⇒ 34 ⇒ 122 ⇒ 63 ⇒ 43 ⇒ 36 ⇒ 38 ⇒ 113 ⇒ 108 ⇒ 39 ⇒ 116 ⇒ 69 ⇒ 112 ⇒ 68 ⇒ 33 ...
 37 ⇒ 103 ⇒ 117 ⇒ 111 ⇒ 120 ⇒ 58 ⇒ 37 ...
 41 ⇒ 102 ⇒ 96 ⇒ 60 ⇒ 51 ⇒ 41 ...
 42 ⇒ 114 ⇒ 125 ⇒ 105 ⇒ 42 ...
 50 ⇒ 80 ⇒ 66 ⇒ 62 ⇒ 76 ⇒ 79 ⇒ 67 ⇒ 85 ⇒ 73 ⇒ 50 ...
 70 ⇒ 74 ⇒ 70 ...

これらのサイクルを使うことで、毎回違う動作をするループを作り出し、最終的には反復動作を指せることができる。Lou Schefferはこのアイデアを用いて、ユーザの入力をそのまま出力するプログラムを作った。