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

  1. The a register is our memory pointer.
  2. We initialize the a register to 0.

Proof

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

  1. > maps to +1a
  2. < maps to -1a
  3. + maps to +1[a
  4. maps to -1[a
  5. . maps to “[a
  6. , maps to ?[a
  7. [ maps to {![a
  8. ] 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:

+++ +++ +++ +
[
    > +++ +++ +
    > +++ +++ +++ +
    > +++
    > +
    <<< < -
&#93;
>++ .
>+.
+++ +++ +.
.
+++ .
>++ .
<<+ +++ +++ +++ +++ ++.
>.
+++ .
--- --- .
--- --- --.
>+.

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.