Malbolge
プログラミング言語Malbolgeが世に出たとき、理解することが非常に難しく、最初に書かれたプログラムが出現するのに2年を要した。しかもそのプログラムは人間によって書かれたものではなく、Andrew Cookeが設計しLISPで実装したビーム探索アルゴリズムにより生成したものだった。
2000年8月24日、Anthony Youhasは彼のブログでMalbolgeを打ちのめし解決の鍵を極めたと宣言し、様々な語句を表示する3つのMalbolgeプログラムコードによりその証拠とした。しかし、どのような技法を用いたかは明らかにはしなかった。
後にLou Schefferは、Malbolgeはプログラミング言語というより暗号システムとして見るべきであり、暗号システムとして見た場合のMalbolgeにはいくつかの脆弱性があると指摘した。また、これらの脆弱性を突くことでMalbolgeプログラムを書くことができるとし、例として入力された文字を出力するプログラムを示した。
OlmsteadはMalbolgeが線形拘束オートマトンであると考えていた。無限ループが初めて発表されるまでに何年も要しており、Malbolgeにおける実用的なループのインプリメント可能性に関し、さらに興味深い議論がある。
Malbolgeのプログラム難読化への応用可能性に着目した名古屋大学の酒井正彦らにより、3段階の中間言語やSATソルバを用いてMalbolgeプログラムを生成する手法が提案されている。これらの研究成果を用いて、while文や配列、再帰関数などを含むC言語のサブセットをMalbolgeプログラムにコンパイルすることが可能となっている。