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.

Couldn't one produce a non-halting Malboge program by filling up memory with NOPs? Such a program would simply loop through memory forever. At any rate, the above argument is a RedHerring. The existence of programs that don't halt is a necessary but not sufficient condition for a TuringMachine; it's easy to produce FSM's that never halt (a FSM with a single state, with an epsilon-transition to itself, will suffice). The HaltingProblem states that it is impossible to determine in finite time (in general) whether a TuringMachine will halt or not; not that TuringMachine's can have non-halting programs. With a FSM, a TuringMachine can examine a FSM and determine if the FSM will halt or not, in finite time.

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.

Wait a minute. You could make similar arguments about C, yet C is regarded as TuringEquivalent. The unboundedness of TuringMachines usually translates in practice into "big enough limits to get things done".
- The definition of CeeLanguage doesn't limit the size of memory available to C programs. One can always get more with malloc(); one can further get more memory by use of recursion to create additional stack frames (though recursion without malloc might get you a pushdown automaton, not a TuringMachine). One could argue that memory available to C programs is limited by "sizeof (void *)"; one could counter-argue that this is an implementation detail and not a fundamental limitation of the language. For other high-level languages (where the size of pointers is not exposed via a sizeof operator), even this argument fades away. With Malbolge; memory is fixed. You've got 3^10 words; and not a single word more. At any rate, I suspect we're picking nits here. :) I agree on the nitpicking, disagree on the details of the nit... sizeof(void*) can be chosen by an implementation, but MUST be finite. Therefore, C has exactly the same memory limitations as Malbolge... a different finite number was chosen, but it's not possible in either to have an arbitrary number of states. -- AdamBerger. But as you say, that's the case for any given implementation of C, not "Platonic" C itself.

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:

X = Push value of A onto B stack.
? = Discard pop 1 value from B stack.

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