### bAdkOde is Turing Complete

#### by vivin

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:**

+++ +++ +++ + [ > +++ +++ + > +++ +++ +++ + > +++ > + <<< < - ] >++ . >+. +++ +++ +. . +++ . >++ . <<+ +++ +++ +++ +++ ++. >. +++ . --- --- . --- --- --. >+.

**helloworld.bad**

>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

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

#!/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.

[…] been able to provide a direct translation of Brainfuck into bAdkOde, which proves the Turing Completeness of […]

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.