Brain:D

Brain:D is a Brainfuck derivative made by User:Areallycoolusername. It's made to make a person's life miserable.

Brainfuck	Brain:D
+	D
-	DD
>	DDD
<	DDDD
.	DDDDD
,	DDDDDD
[	DDDDDDD
]	DDDDDDDD
No equivalent	:

As shown above, all the code is the same except for the fact that they've all become Ds. Another command has also been added, which just signifies the start of the program. The Brain:D syntax is as follows:

(Starting token)(Code tokens)

With that being said, a hello world program, one of the most tedious programs you'll ever make in this language, is shown below.

:D D D D D D D D DDDDDDD DDD D D D D DDDDDDD DDD D D DDD D D D DDD D D D DDD D DDDD DDDD DDDD DDDD DD DDDDDDDD DDD D DDD D DDD DD DDD DDD D DDDDDDD DDDD DDDDDDDD DDDD DD DDDDDDDD DDD DDD DDDDD DDD DD DD DD DDDDD D D D D D D D DDDDD DDDDD D D D DDDDD DDD DDD DDDDD DDDD DD DDDDD DDDD DDDDD D D D DDDDD DD DD DD DD DD DD DDDDD DD DD DD DD DD DD DD DD DDDDD DDD DDD D DDDDD DDD D D DDDDD

Spaces are ignored, but they're included for clarity. If spaces weren't allowed, the program would look like:

:DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

This hello world example was made in Python since coding it in actual Brain:D would take too long. Basically, Brain:D is meant to mess you up. The thing about this language is that in theory, you could type in a colon and as many Ds as you want, and there would be output.

Computational complexity

The behavior of Brain:D is ill-defined and thus the computational class is unknown. Programs in Brain:D have an ambiguous parse tree (see below for the number of valid parses for a given number of D). A universal search algorithm could feasibly execute all possible parses of a given Brain:D program, meaning that Brain:D is computable and Turing complete. If instead of all possible valid parses being executed, only one program is executed (or equivalently, only one calculated result is output) then Brain:D may be uncomputable depending on what criterion is used to decide which possible parse to execute. Conditions like "what the programmer intended" is uncomputable and Turing complete, but always using the parse consisting of just + is computable and not complete.

Nonetheless, in terms of decidability, Brain:D is a trivial language; for any number of 'D' tokens, there is a corresponding always-halting Brainfuck program consisting solely of '+' tokens.

Number of parses

We can count the number of legal Brainfuck programs encoded by a Brain:D program. Since every Brain:D program is represented by its number of 'D' tokens, our counting will be a function f from natural numbers to natural numbers. The first few values of f are computed directly from stars-and-bars reasoning:

f(0) = 1
f(1) = 1
f(2) = 1 + 1 = 2
f(3) = 1 + 2 + 1 = 4
f(4) = 1 + 3 + 3 + 1 = 8
f(5) = 1 + 4 + 6 + 4 + 1 = 16
f(6) = 1 + 5 + 10 + 10 + 5 + 1 = 32

We can see powers of two and intuit that they emerge because there are two ways to include f(n) into f(n + 1), either placing a '+' at the beginning or at the end. The pattern continues until f(14) = 8192. After that, we include the following recurrence for matching brackets:

f(n + 15) = 2 × f(n + 14) + f(n)

That is, if we have at least n + 15 tokens, then we have the stars-and-bars counting plus an additional possible parse which is surrounded by brackets and contains an inner program of n tokens. The following Python quickly computes values of f with inline memoization:

def f(n, _cache=[1]+[2**x for x in range(14)]):
     while n >= len(_cache): _cache.append(2 * _cache[-1] + _cache[-15])
     return _cache[n]

>>> [f(x) for x in range(25)]
[1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16385, 32771, 65544, 131092, 262192, 524400, 1048832, 2097728, 4195584, 8391424]
>>> f(100)
635509676146796754536324531712

See also

• Quantum Nothing is mostly equivalent to Brain:D if the interpretation that all possible parses of the program are executed in parallel is correct