Rough Book

bAdkOde is Turing Complete

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:

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

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 = <STDIN>;
 $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++;
 }

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.

Popularity: unranked [?]

December 26, 2009 - Posted by vivin | Programming and Development, Projects | badkode, brainf*ck, brainfuck, code, computing, development, perl, programming, programming languages, project, turing complete, turing completeness