Malbolge - AbsoluteAstronomy.com

Malbolge is a public domain

Public domain

Works are in the public domain if the intellectual property rights have expired, if the intellectual property rights are forfeited, or if they are not covered by intellectual property rights at all...

esoteric programming language

Esoteric programming language

An esoteric programming language is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke...

invented by Ben Olmstead in 1998, named after the eighth circle of hell in Dante

Dante Alighieri

Durante degli Alighieri, mononymously referred to as Dante , was an Italian poet, prose writer, literary theorist, moral philosopher, and political thinker. He is best known for the monumental epic poem La commedia, later named La divina commedia ...

's Inferno
Inferno (Dante)
Inferno is the first part of Dante Alighieri's 14th-century epic poem Divine Comedy. It is followed by Purgatorio and Paradiso. It is an allegory telling of the journey of Dante through what is largely the medieval concept of Hell, guided by the Roman poet Virgil. In the poem, Hell is depicted as...

, the Malebolge

Malebolge

In Dante Alighieri's Inferno, part of the Divine Comedy, Malebolge is the eighth circle of Hell. Roughly translated from Italian, Malebolge means "evil ditches". Malebolge is a large, funnel-shaped cavern, itself divided into ten concentric circular trenches or ditches. Each trench is called a bolgia...

.

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.

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

Beam search

In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements...

algorithm designed by Andrew Cooke and implemented in Lisp

Lisp programming language

Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...

.

Later, Lou Scheffer posted a cryptanalysis

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...

of Malbolge and provided a program to copy its input to its output.

Olmstead believed Malbolge to be a linear bounded automaton

Linear bounded automaton

In computer science, a linear bounded automaton is a restricted form of nondeterministic Turing machine.-Operation:Linear bounded automata satisfy the following three conditions:...

. 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

99 Bottles of Beer

"99 Bottles of Beer" is a traditional song in the United States and Canada. It is popular to sing on long trips, as it has a very repetitive format which is easy to memorize, and can take a long time to sing. In particular the song is frequently sung by children on long bus trips, such as class...

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!

Hello world program

A "Hello world" program is a computer program that outputs "Hello world" on a display device. Because it is typically one of the simplest programs possible in most programming languages, it is by tradition often used to illustrate to beginners the most basic syntax of a programming language, or to...

", with full capitalization and exclamation mark at the end.



  ('&%:9]!~}|z2Vxwv-,POqponl$Hjig%eB@@>}=
  `CB]V?Tx

Simplified workings of Malbolge

Malbolge is machine language for a ternary

Ternary numeral system

Ternary is the base- numeral system. Analogous to a bit, a ternary digit is a trit . One trit contains \log_2 3 bits of information...

virtual machine

Virtual machine

A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...

, the Malbolge interpreter

Interpreter (computing)

In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language...

. To aid in the writing of Malbolge programs

Computer program

A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...

that run properly, the way the standard interpreter works will be described below.

Registers

Malbolge has three registers

Processor register

In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...

, 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

Program counter

The program counter , commonly called the instruction pointer in Intel x86 microprocessors, and sometimes called the instruction address register, or just part of the instruction sequencer in some computers, is a processor register that indicates where the computer is in its instruction sequence...

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 (3¹⁰) memory locations that can each hold a ten-digit ternary number

Ternary numeral system

Ternary is the base- numeral system. Analogous to a bit, a ternary digit is a trit . One trit contains \log_2 3 bits of information...

. 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

Opcode

In computer science engineering, an opcode is the portion of a machine language instruction that specifies the operation to be performed. Their specification and format are laid out in the instruction set architecture of the processor in question...

. 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 ASCII The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text... 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

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
crz		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

Modulo operation

In computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...

94. Then, the result is encrypted

Encryption

In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...

with one of the following two equivalent methods

Substitution cipher

In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters , pairs of letters, triplets of letters, mixtures of the above, and so forth...

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.
Malbolge Unshackled is a Turing-complete 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.

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

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

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

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