Malbolge Language

The first programming language designed specifically to be difficult to use. The web site is here:

http://www.lscheffer.com/malbolge.shtml

There is some doubt as to Malbolge's TuringCompleteness. The author believes it to be Turing-complete, using the rotate operator to perform computations and self-modifying code for conditional execution. However, the GeneticAlgorithms used to produce the first Malbolge HelloWorld never resulted in a program that didn't halt. Most programs written randomly in a Turing-complete language suffer from the HaltingProblem, and so this casts doubt on Malbolge's Turing-completeness.

See also: BefungeLanguage and EsotericProgrammingLanguage


An article about Malbolge programming: http://esolangs.org/wiki/Malbolge_programming -- MarkusSrank

Proof that Malbolge is not TuringComplete is simple.

According to the documentation, the Malbolge programming model includes a fixed-size memory of 59049 (3^10) words, each word can hold 3^10 different states. There is NO other memory than that. By definition, then, Malbolge implements a FiniteStateMachine. The number of possible states is large (3^10)^(3^10), but finite. The fact that it permits self-modifying code doesn't change the fact that it's a finite state machine.

In order to be TuringComplete, a programming language must operate under the assumption that an infinite amount of memory is available. (True, real computer hardware is always a FiniteStateMachine, infinite memories being impossible to build, but no TuringComplete language limits memory in its programming model).

As a consequence: Were I to implement a (non-validating) parser for XML (a well-known example of a context free grammar); it would always be possible for me to construct an XML document of sufficient complexity that no Malbolge implementation; no matter how much memory may be installed on the underlying computer, could parse. TuringComplete languages would only be limited by the amount of physical memory (RAM, disk, etc.); and any limitations encountered could be bypassed by installing more.

While iteration and selection constructs are generally considered necessary for TuringCompleteness; they are not sufficient. An infinite random-access store is also required.


True, but not terribly relevant. When one speaks of "TuringComplete" in practical terms, one almost always makes the assumption that very large = infinite, for the very practical reason that real computers don't have infinite memory. Otherwise, you would have to claim that AssemblyLanguage is not Turing-complete, which is true in a strict sense but not terribly useful. Since high-level languages are implemented on top of assembly/machine language, you'd then have to claim that programming language implementation is Turing complete, as you can't emulate a Turing machine on a finite state machine.

Malbolge gives an address space of close to 600k trits, which is more than early (AppleTwo/Commodore) PCs. People managed reasonable approximations of Turing-complete languages on those.

And were you to implement a non-validating parser for XML in any language, it is always possible to construct an XML document of sufficient complexity that no mainstream OS, no matter how much physical memory is installed on the underlying machine, can parse. Simply make it 4 gigs long.


By this definition, what languages are turing complete? C isn't... there's no arbitrary-precision pointer type, so no way to address more than 2^32 or 2^64 or some other finite number of bytes of memory... Java, I suppose, is, making it MorePowerfulThanCee?! Can someone take a shot at a formal definition of EffectivelyTuringComplete?? -- AdamBerger

There's one nitpicky formally precise answer, and there's another answer that is more helpful for practical purposes.

Precisely speaking, to be TuringEquivalent requires unbounded memory. This is not infinite, it's finite but of arbitrary size; nothing prevents doubling it.

If the definition of C says that pointers can never be more than 32 bits (although it does not say this), then technically, C would not be TuringEquivalent, while if the definition of C leaves the width of pointers implementation-dependent, then technically it would be TuringEquivalent - even though any given implementation will always have some such limit.

Practically speaking, however, it doesn't matter if a language or physical/virtual machine has a strict upper limit on memory, as long as that limit is large enough for all practical purposes.

A UniversalTuringMachine is universal because it can simulate any other Turing machine, regardless of how many states, how many symbols, etc. Obviously no realizable machine can formally be a UniversalTuringMachine, because there are an infinite number of TuringMachines that require more resources to simulate than are available to any realizable machine.

Pragmatically, there are limits to what we can implement, so that theoretical issue doesn't matter in practice. The question is whether something is universal for the uses to which we might put it.

Above it is claimed that Malbolge is merely equivalent to a finite state machine because a memory limitation is built-in to the language definition. This is strictly true, but pragmatically probably false.

In theory, any finite TuringMachine can be simulated by a finite state machine, yes, but in general it requires an exponential number of states to do so. So that equivalency is formally true, but untrue in practice because we usually can't afford to use an exponential number of states to do things.

Note also that typical TuringMachines tend to require exponential time and/or space resources for algorithms that are linear on real world computers - there is already a huge important gap between theory and practice in this regard (this is all well known theoretically, I'm not talking about a deficiency in the formal treatments). Yet it is reasonable for many purposes to treat TuringMachines and Pentiums as equivalent; it depends on what you're talking about.

So in practice, it is much more to the point to regard a finite TuringMachine as just a TuringMachine that happens to have a limited resource, not to regard it as a basic finite state machine.

So pragmatically, if the memory size is the only issue (I don't know the language, there may be other issues; maybe Malbolge also requires exponential memory for something that C only requires linear memory for), Malbolge is TuringEquivalent as much as any actual implementation of C.

Therefore, the claim at top of page that Malbolge is not TuringEquivalent is a nitpick, rather than truly informative about the language. If a non-academic asks if something is TuringEquivalent, usually what is really desired is to know if one can write the usual algorithms in it: eight queens, a mail program, a wiki, etc. So far as I know, these things may all be possible in Malbolge.


OK, I make a suggestion of a new variant to make Malbolge TuringComplete. There is a new register called B, which is an infinite stack of numbers, and 2 new commands:

The first 82 words of the memory are actively stored in reference by the stack. Each section is 82 words long, and the first 82 words of the memory is the same as that section. For example, () stores 82 words (for normal malbolge), and (23,5,112,112,1211,9051) also stores 82 words, which will be copy memory later.

What is stored in different part started in program, can be given by different section of the file indicated by @@@ and list and $$$ at end of the list of numbers. Separator by 6 and numbers are base 7 using these characters: +190875 [Example: @@@$$$ program @@@+657+7$$$ program]

Is this going to work?
CategoryProgrammingLanguage

EditText of this page (last edited January 23, 2014) or FindPage with title or text search