In my previous post, I suggested that bAdkOde might be Turing Complete by writing a quine. One of the ways to actually prove Turing Completeness is to try and write an interpreter for another Turing-Complete language in bAdkOde. Another approach involves providing a direct translation from another Turing-Complete language into bAdkOde. Here, I prove the Turing Completeness of bAdkOde by providing a direct translation from Brainfuck into bAdkOde.

__Assumptions__

- The
*a*register is our memory pointer. - We initialize the
*a*register to 0.

__Proof__

We translate Brainfuck to bAdkOde using the following mappings or rules:

*>*maps to*+1a**<*maps to*-1a**+*maps to*+1[a**-*maps to*-1[a**.*maps to*"[a**,*maps to*?[a**[*maps to*{![a**]*maps to*}*

__Conclusion__

Since we can completely translate or map Brainfuck, an already Turing-Complete language into bAdkOde, we can say that bAdkOde is also Turing Complete.

__Translated example__

**helloworld.bf:**

[sourcecode]

+++ +++ +++ +

[

> +++ +++ +

> +++ +++ +++ +

> +++

> +

<<< < -
]
>++ .

>+.

+++ +++ +.

.

+++ .

>++ .

<<+ +++ +++ +++ +++ ++.
>.

+++ .

--- --- .

--- --- --.

>+.

[/sourcecode]

**helloworld.bad**

[sourcecode]

>0a+1[a+1[a+1[a +1[a+1[a+1[a +1[a+1[a+1[a +1[a

{![a

+1a +1[a+1[a+1[a +1[a+1[a+1[a +1[a

+1a +1[a+1[a+1[a +1[a+1[a+1[a +1[a+1[a+1[a +1[a

+1a +1[a+1[a+1[a

+1a +1[a

-1a-1a-1a -1a -1[a

}

+1a+1[a+1[a "[a

+1a+1[a"[a

+1[a+1[a+1[a +1[a+1[a+1[a +1[a"[a

"[a

+1[a+1[a+1[a "[a

+1a+1[a+1[a "[a

-1a-1a+1[a +1[a+1[a+1[a +1[a+1[a+1[a +1[a+1[a+1[a +1[a+1[a+1[a +1[a+1[a"[a

+1a"[a

+1[a+1[a+1[a "[a

-1[a-1[a-1[a -1[a-1[a-1[a "[a

-1[a-1[a-1[a -1[a-1[a-1[a -1[a-1[a"[a

+1a+1[a"[a

[/sourcecode]

Here's a quick perl script that I whipped up, to translate Brainfuck to bAdkOde:

[sourcecode language="perl"]

#!/usr/bin/perl

use strict;

my $terminator = $/;

undef $/;

my $bf =

$bf =~ s/[^<>\[\]\.,\+\-\s\n]//g;

$/ = $terminator;

my $i = 0;

print ">0a";

while($i < length($bf)) {
my $bf_instruction = substr($bf, $i, 1);
if($bf_instruction eq '>') {

print "+1a";

}

elsif($bf_instruction eq '<') {
print "-1a";
}
elsif($bf_instruction eq '+') {
print "+1[a";
}
elsif($bf_instruction eq '-') {
print "-1[a";
}
elsif($bf_instruction eq '.') {
print "\"[a";
}
elsif($bf_instruction eq ',') {
print "?[a";
}
elsif($bf_instruction eq '[') {
print "{![a";
}
elsif($bf_instruction eq ']') {
print "}";
}
else {
print $bf_instruction;
}
$i++;
}
[/sourcecode]
__Additional proof__

Since there exist self-interpreters for Brainfuck (i.e., Brainfuck interpreters written *in* Brainfuck), and since it has been shown that there exists a valid translation from Brainfuck to bAdkOde, it follows that it is possible to write a Brainfuck interpreter in bAdkOde. This provides additional proof for the Turing Completeness of bAdkOde.

you mustve aced computational theory

@sheehan

Haha, I think I actually got a B because I slacked off during finals. But I do like some aspects of computational theory! ðŸ™‚ Eh… I’m a nerd, what can I say? Heh.