Home

Malbolge figured out?

Taken out of order:

From Ryan Kusnery's weird languages page:

The day that someone writes, in Malbolge, a program that simply copies its input to it's output, is the day my hair spontaneously turns green. It's the day that elephants are purple and camels fly, and a cow can fit through a needle's eye.

earlier:

I've succeeded in writing a Malbolge program that copies its input to its output. Since some of it is non-printing, here it is uu-encoded...

In addition the page contains a proof of Turing Completeness (of a slight modification of the language), and suggestions on how it could be made harder.
By Jeff Cutsinger at 2005-07-05 18:19 | Fun | other blogs | 12429 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Malbolge programming

I've succeeded at creating a Malbolge 'cat' program which does not exploit the interpreter's bug that allows entering characters above 126. It's shown here: Malbolge entry at the EsoLangs wiki, showing 'cat' as an example. Both Lou Scheffer's version and this one have the same problem: they do not stop at EOF; instead they write character 168 repeatedly when they hit EOF. I've already written one that removes this limitation, stopping on EOF and implementing what is probably the first conditional jump ever written in Malbolge. However it currently needs preloading memory with the program code; I'm currently working on the initialization routine that sets up the memory as needed to make it a complete, usable program (incidentally, the purpose of the second part of the code in the 'cat' program above, the part starting with the 'j' that is alone in a line, is the part that initializes memory as needed by the program).

I'm also working in an article on how to write Malbolge programs, following Lou Scheffer's guidelines and pointing out the caveats I've found in the way. [UPDATE 2005-07-09: The article is finished; see Malbolge programming article at the Esolangs wiki.]

Note that Lou Scheffer's proof of TC is a sketch and it might be invalid. Actual writing of Malbolge programs is expensive in terms of memory used (the program code is sparsely located in memory), so the limitation of 59049 memory words might be insufficient for an universal Turing machine's finite state automaton to be writable. I've designed a joke language to ironize about that; it's called Bitxtreme. Furthermore, Lou Scheffer's sketch of proof on TC uses a language extension to use the I/O stream as an infinite tape; Malbolge itself can't be TC (see the wiki for more details).

-- Pedro Gimeno

By pgimeno at Wed, 2005-07-06 08:59 | login or register to post comments