Malbolge

Malbolge

Malbolge is a public domain esoteric programming language invented by Ben Olmstead in 1998, named after the eighth circle of hell in Dante's Inferno, the Malebolge.

The peculiarity of Malbolge is that it was designed to be the most difficult and esoteric programming language. However, several of the tricks used to make understanding it difficult can be simplified away.

Contents

Programming in Malbolge

Malbolge was so difficult to understand when it arrived that it took two years for the first Malbolge program to appear. The program was not even written by a human being: it was generated by a beam search algorithm designed by Andrew Cooke and implemented in Lisp.[citation needed]

Later, Lou Scheffer posted a cryptanalysis of Malbolge and provided a program to copy its input to its output.[1]

Olmstead believed Malbolge to be a linear bounded automaton. There is a more interesting discussion about whether one can implement sensible loops in Malbolge — it took many years before the first non-terminating one was introduced. A correct 99 Bottles of Beer program, which deals with non-trivial loops and conditions, was not announced for eight years; the first correct one was by Hisashi Iizawa in 2007.

"Hello world" in Malbolge

This Malbolge program displays "Hello world!", with full capitalization and exclamation mark at the end.

 ('&%:9]!~}|z2Vxwv-,POqponl$Hjig%eB@@>}=<M:9wv6WsU2T|nm-,jcL(I&%$#"
 `CB]V?Tx<uVtT`Rpo3NlF.Jh++FdbCBA@?]!~|4XzyTT43Qsqq(Lnmkj"Fhg${z@>

Simplified workings of Malbolge

Malbolge is machine language for a ternary virtual machine, the Malbolge interpreter. To aid in the writing of Malbolge programs that run properly, the way the standard interpreter works will be described below.

Notes

  • The standard interpreter and the official specification do not match perfectly.
  • This is a simplified explanation of the interpreter source code: it obviates useless encryption and subtraction steps and introduces an assembly language.

Registers

Malbolge has three registers, a, c, and d. When a program starts, the value of all three registers is zero. c is special: it points to the current instruction.

Pointer notation

d can hold a memory address; [d] is the value stored at that address. [c] is similar.

Memory

The virtual machine has 59049 (310) memory locations that can each hold a ten-digit ternary number. Each memory location has an address from 0 to 59048 and can hold a value from 0 to 59048. Incrementing past this limit wraps back to zero.

Before a Malbolge program starts, the first part of memory is filled with the program. All whitespace in the program is ignored and, to make programming more difficult, everything else in the program must start out as one of the instructions below.

The rest of memory is filled by using the crazy operation (see below) on the previous two addresses ([m] = crz [m - 2], [m - 1]). Memory filled this way will repeat every twelve addresses (the individual ternary digits will repeat every three or four addresses, so a group of ternary digits is guaranteed to repeat every twelve).

Instructions

Malbolge has eight instructions. Malbolge figures out which instruction to execute by taking the value at [c], adding the value of c to it, and taking the remainder when this is divided by 94. The final result tells the interpreter what to do:

Instructions
Value of
([c] + c) % 94
Instruction represented Explanation
4 jmp [d] + 1 The value at [d], plus one, is where Malbolge will jump to and start executing instructions.
5 out a Prints the value of a, as an ASCII character, to the screen.
23 in a Inputs a character, as an ASCII code, into a. Newlines or line feeds are both code 10. An end-of-file condition is code 59048.
39 rotr [d]
mov a, [d]
Rotates the value at [d] by one ternary digit (0002111112 becomes 2000211111). Stores the result both at [d] and in a.
40 mov d, [d] Copies the value at [d] to d.
62 crz [d], a
mov a, [d]
Does the crazy operation (see below) with the value at [d] and the value of a. Stores the result both at [d] and in a.
68 nop Does nothing.
81 end Ends the Malbolge program.
Any other value does the same as 68: nothing. These other values are not allowed in a program while it is being loaded, but are allowed afterwards.

After each instruction is executed, the guilty instruction gets encrypted (see below) so that it won't do the same thing next time, unless a jump just happened. Right after a jump, Malbolge will encrypt the innocent instruction just prior to the one it jumped to instead. Then, the values of both c and d are increased by one and the next instruction is executed.

Crazy operation

[citation needed]For each ternary digit of both inputs, use the following table to get a ternary digit of the result. For example, crz 0001112220, 0120120120 gives 1001022211.

Crazy operation
crz Input 2
0 1 2
Input 1 0 1 0 0
1 1 0 2
2 2 2 1

Encryption

After an instruction is executed, the value at [c] (without anything added to it) will be replaced with itself mod 94. Then, the result is encrypted with one of the following two equivalent methods.

Method 1

Find the result below. Store the ASCII code of the character below it at [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

Method 2

Find the result below. Store the encrypted version at [c].

Encryption table
Result Encrypted Result Encrypted Result Encrypted Result Encrypted Result Encrypted
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

Cycles in the encryption

Lou Scheffer's cryptanalysis of Malbolge mentions six different cycles in the encryption. They are listed here:

  • 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 ...

These cycles can be used to create loops that do different things each time and that eventually become repetitive. Lou Scheffer used this idea to create a Malbolge program (included in his cryptanalysis linked below) that repeats anything the user inputs.

Variants

Malbolge is not Turing-complete, due to its memory limits. Several attempts have been made to create Turing-complete versions of Malbolge.

  • Malbolge-T is a theoretical version of Malbolge, which resets the input/output stream upon reaching the end, allowing for unbounded programs. Malbolge programs would be valid in Malbolge-T.[2]
  • Malbolge Unshackled is a Turing-complete[citation needed] variation, allowing for programs of any length. However, due to command variations to allow for values above 257, valid Malbolge programs will not necessarily run correctly in Malbolge Unshackled.[3]

See also

References

  1. ^ Programming in Malbolge. Lscheffer.com (2007-12-11). Retrieved on 2011-11-21.
  2. ^ "Introduction to Malbolge, Proving formal Turing completeness". http://www.lscheffer.com/malbolge.shtml#Turing. 
  3. ^ Malbolge Unshackled - Esolang. Esolangs.org (2010-11-24). Retrieved on 2011-11-21.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Malbolge — est un langage de programmation du domaine public inventé par Ben Olmstead en 1998, nommé d après le huitième cercle de l enfer dans L Enfer de Dante, le Malebolge. La particularité de Malbolge est qu il a été conçu pour être le pire (le plus… …   Wikipédia en Français

  • Malbolge — эзотерический язык программирования, придуманный Беном Олмстедом в 1998 году. Язык разработан с целью быть максимально сложным для написания программ. Получил своё название от Malebolge, восьмого круга ада Данте. Содержание 1 Программирование на… …   Википедия

  • Malbolge — ist eine esoterische Programmiersprache, 1998 entwickelt von Ben Olmstead. Benannt wurde sie nach dem achten Kreis der Hölle aus Dantes Divina Commedia. Malbolge ist gemeinfrei. Die Besonderheit von Malbolge besteht darin, dass sie als… …   Deutsch Wikipedia

  • Malbolge — es un lenguaje de programación esotérico de dominio público desarrollado por Ben Olmstead en 1998. Se llamó así por el octavo círculo del infierno en La Divina Comedia, escrito por Dante. Malbolge es peculiar porque se diseñó para ser el lenguaje …   Wikipedia Español

  • Malbolge — es un lenguaje de programación esotérico de dominio público desarrollado por Ben Olmstead en 1998. Se llamó así por el octavo círculo del infierno en La Divina Comedia, escrito por Dante. Malbolge es peculiar porque se diseñó para ser el lenguaje …   Enciclopedia Universal

  • Baator — For the capital of Mongolia, see Ulaanbaatar. In the Dungeons Dragons fantasy role playing game, Baator, also known as the Nine Hells of Baator or the Nine Hells, is a lawful evil aligned plane of existence. It is one of a number of alignment… …   Wikipedia

  • Lords of the Nine Hells — The Lords of the Nine Hells are fictional characters in the Dungeons Dragons roleplaying game. The lords outlined in this article are the highest ranking devils in the Nine Hells of Baator. They include the Dark Eight the eight generals of the… …   Wikipedia

  • Hag Countess — Game background Title(s) Former Lord of the Sixth Home plane Nine Hells Power level Archdevil Alignment Lawful Evil Superior Asmodeus …   Wikipedia

  • Baator — Neuf Enfers de Baator Dans le jeu de rôle médiéval fantastique Donjons et dragons, Baator, (aussi appelé les Neuf Enfers de Baator ou les Neuf Enfers) est un plan extérieur d alignement loyal mauvais. C est l un des nombreux plans extérieurs… …   Wikipédia en Français

  • Neuf Enfers De Baator — Dans le jeu de rôle médiéval fantastique Donjons et dragons, Baator, (aussi appelé les Neuf Enfers de Baator ou les Neuf Enfers) est un plan extérieur d alignement loyal mauvais. C est l un des nombreux plans extérieurs faisant partie de la… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”