Skip to content

Rough Book

random musings

Menu
  • About Me
  • Contact
  • Projects
    • bAdkOde
    • CherryBlossom
    • FXCalendar
    • Sulekha
Menu

A bAdkOde quine (which suggests that bAdkOde is Turing Complete)

Posted on December 25, 2009January 23, 2010 by vivin

On the bAdkOde project page, I mentioned that I didn't know whether bAdkOde is Turing Complete (although I suspected it). I also mentioned that if I was able to write a quine in bAdkOde, then it would probably mean that it is Turing Complete. I was able to write one after going through this excellent quine tutorial by Dave Cope.

A quine is basically a program that prints a copy of its source code. Writing a quine seems trivial, but can be, and is in most cases, fiendishly difficult. The quine tutorial that I mentioned earlier describes a rather simple method to create a quine. In any quine, you need to store a representation of part of the source code. This representation is referred to as the core or body. In the method described in the tutorial, and the method that I used, the core is represented as ASCII codes. In some approaches, the core is represented as a string or character array (which, when it comes down to it, is probably represented in memory as an array of ASCII codes). In the approach that I used, there are two parts to the core. The first part prints out the code for the data structure that will contain a representation of the core, and the second part prints out the actual core. For example, let's say I wanted to make a Perl quine. I start off with the core:

[sourcecode language="perl"]
print " \@body = (\n";
map { printf "0x%x, ", $_ } @body;
print " );\n";
map { printf "%c", $_ } @body;
[/sourcecode]

Here, you can see that I've decided to use an array called @body to store the ASCII values (in hexadecimal). The first three lines print out the definition for the array that will hold the ASCII values. The last line reads the array, translates the code into actual characters, and prints them out. Now all we have to do is get the hexadecimal codes and create the array. To do that, we use a utility called xxd:

[email protected] ~/Projects/code/perl/quine
$ xxd -i quinegen.pl >qhex.pl

The output is an array definition in C:

[sourcecode language="c"]
unsigned char quinegen_pl[] = {
0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x20, 0x22, 0x20, 0x5c, 0x40, 0x62,
0x6f, 0x64, 0x79, 0x20, 0x3d, 0x20, 0x28, 0x5c, 0x6e, 0x22, 0x3b, 0x0a,
0x20, 0x6d, 0x61, 0x70, 0x20, 0x7b, 0x20, 0x70, 0x72, 0x69, 0x6e, 0x74,
0x66, 0x20, 0x22, 0x30, 0x78, 0x25, 0x78, 0x2c, 0x20, 0x22, 0x2c, 0x20,
0x24, 0x5f, 0x20, 0x7d, 0x20, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x3b, 0x0a,
0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x20, 0x22, 0x20, 0x29, 0x3b, 0x5c,
0x6e, 0x22, 0x3b, 0x0a, 0x20, 0x6d, 0x61, 0x70, 0x20, 0x7b, 0x20, 0x70,
0x72, 0x69, 0x6e, 0x74, 0x66, 0x20, 0x22, 0x25, 0x63, 0x22, 0x2c, 0x20,
0x24, 0x5f, 0x20, 0x7d, 0x20, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x3b, 0x0a
};
unsigned int quinegen_pl_len = 108;
[/sourcecode]

We need to change this to valid Perl, and that's quite simple:

[sourcecode language="perl"]
@body = (
0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x20, 0x22, 0x20, 0x5c, 0x40, 0x62,
0x6f, 0x64, 0x79, 0x20, 0x3d, 0x20, 0x28, 0x5c, 0x6e, 0x22, 0x3b, 0x0a,
0x20, 0x6d, 0x61, 0x70, 0x20, 0x7b, 0x20, 0x70, 0x72, 0x69, 0x6e, 0x74,
0x66, 0x20, 0x22, 0x30, 0x78, 0x25, 0x78, 0x2c, 0x20, 0x22, 0x2c, 0x20,
0x24, 0x5f, 0x20, 0x7d, 0x20, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x3b, 0x0a,
0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x20, 0x22, 0x20, 0x29, 0x3b, 0x5c,
0x6e, 0x22, 0x3b, 0x0a, 0x20, 0x6d, 0x61, 0x70, 0x20, 0x7b, 0x20, 0x70,
0x72, 0x69, 0x6e, 0x74, 0x66, 0x20, 0x22, 0x25, 0x63, 0x22, 0x2c, 0x20,
0x24, 0x5f, 0x20, 0x7d, 0x20, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x3b, 0x0a
);
[/sourcecode]

We take this and paste it on top of our core:

[sourcecode language="perl"]
@body = (
0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x20, 0x22, 0x20, 0x5c, 0x40, 0x62,
0x6f, 0x64, 0x79, 0x20, 0x3d, 0x20, 0x28, 0x5c, 0x6e, 0x22, 0x3b, 0x0a,
0x20, 0x6d, 0x61, 0x70, 0x20, 0x7b, 0x20, 0x70, 0x72, 0x69, 0x6e, 0x74,
0x66, 0x20, 0x22, 0x30, 0x78, 0x25, 0x78, 0x2c, 0x20, 0x22, 0x2c, 0x20,
0x24, 0x5f, 0x20, 0x7d, 0x20, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x3b, 0x0a,
0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x20, 0x22, 0x20, 0x29, 0x3b, 0x5c,
0x6e, 0x22, 0x3b, 0x0a, 0x20, 0x6d, 0x61, 0x70, 0x20, 0x7b, 0x20, 0x70,
0x72, 0x69, 0x6e, 0x74, 0x66, 0x20, 0x22, 0x25, 0x63, 0x22, 0x2c, 0x20,
0x24, 0x5f, 0x20, 0x7d, 0x20, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x3b, 0x0a
);
print " \@body = (\n";
map { printf "0x%x, ", $_ } @body;
print " );\n";
map { printf "%c", $_ } @body;
[/sourcecode]

Now the interesting thing here is that this piece of code is not the actual quine. Rather, it generates the quine. But the generated code isn't that different from the generator:

[sourcecode language="perl"]
@body = (
0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x20, 0x22, 0x20, 0x5c, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x20, 0x3d, 0x20, 0x28, 0x5c, 0x6e, 0x22, 0x3b, 0xa, 0x20, 0x6d, 0x61, 0x70, 0x20, 0x7b, 0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x66, 0x20, 0x22, 0x30, 0x78, 0x25, 0x78, 0x2c, 0x20, 0x22, 0x2c, 0x20, 0x24, 0x5f, 0x20, 0x7d, 0x20, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x3b, 0xa, 0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x20, 0x22, 0x20, 0x29, 0x3b, 0x5c, 0x6e, 0x22, 0x3b, 0xa, 0x20, 0x6d, 0x61, 0x70, 0x20, 0x7b, 0x20, 0x70, 0x72, 0x69, 0x6e, 0x74, 0x66, 0x20, 0x22, 0x25, 0x63, 0x22, 0x2c, 0x20, 0x24, 0x5f, 0x20, 0x7d, 0x20, 0x40, 0x62, 0x6f, 0x64, 0x79, 0x3b, 0xa, );
print " \@body = (\n";
map { printf "0x%x, ", $_ } @body;
print " );\n";
map { printf "%c", $_ } @body;
[/sourcecode]

The only difference is the extra comma in the array definition, and the fact that all the ASCII codes are on one line. If you run this perl script, you will get an exact copy of its source code. Now how do we write a quine in bAdkOde? We use a similar approach. First we write the core:

[sourcecode]
>0a
"62"48"97"10
{![a
"62'[a"91"97"43"49"97
+1a
}
"10
>0a
{![a
"[a
+1a
}
[/sourcecode]

To implement a quine in bAdkOde, I decided to store the representation of the core (in decimal ASCII values) in memory starting at location zero. The first line initializes the a register to zero. The second line prints out the string >0a with a newline. This line is analogous to the print " \@body = (\n"; line in the perl quine. Within our first loop, we're printing out the actual code that will store the representation of the core in memory. So the first line within the loop prints >ASCII[a+1a where ASCII is the ASCII value of a character from the core. The line is analogous to the printf "0x%x, ", $_ line in the perl quine. There is another print statement right outside the first loop, which simply prints a newline. This line is analogous to the print " );\n"; line in the perl quine. The second loop performs the actual translation of the ASCII code into the core. Now, just like the perl quine, we use xxd:

[email protected] ~/Projects/code/perl/bAdkOde
$ xxd -i quine.bad >qhex.txt

After doing this, we get C code that looks like this:

[sourcecode language="c"]
unsigned char quine_bad[] = {
0x3e, 0x30, 0x61, 0x0a, 0x22, 0x36, 0x32, 0x22, 0x34, 0x38, 0x22, 0x39,
0x37, 0x22, 0x31, 0x30, 0x0a, 0x7b, 0x21, 0x5b, 0x61, 0x0a, 0x20, 0x22,
0x36, 0x32, 0x27, 0x5b, 0x61, 0x22, 0x39, 0x31, 0x22, 0x39, 0x37, 0x22,
0x34, 0x33, 0x22, 0x34, 0x39, 0x22, 0x39, 0x37, 0x0a, 0x20, 0x2b, 0x31,
0x61, 0x0a, 0x7d, 0x0a, 0x22, 0x31, 0x30, 0x0a, 0x3e, 0x30, 0x61, 0x0a,
0x7b, 0x21, 0x5b, 0x61, 0x0a, 0x20, 0x22, 0x5b, 0x61, 0x0a, 0x20, 0x2b,
0x31, 0x61, 0x0a, 0x7d, 0x0a
};
unsigned int quine_bad_len = 77;
[/sourcecode]

Translating this into bAdkOde is not as straightforward, but it's not that difficult either. I removed the first line, and the last two lines from qhex.txt and then used a oneliner:

[email protected] ~/Projects/code/perl/bAdkOde
$ cat qhex.txt | perl -e 'chomp($a=); map { print ">" . hex($_) . "[a+1a"; } \
   split(",", $a);' > qdec.txt

You end up with this snippet of bAdkOde:

[sourcecode]
>62[a+1a>48[a+1a>97[a+1a>10[a+1a>34[a+1a>54[a+1a>50[a+1a>34[a+1a>52[a+1a>56[a+1a>34[a+1a>57[a+1a>55[a+1a>34[a+1a>49[a+1a>48[a+1a>10[a+1a>123[a+1a>33[a+1a>91[a+1a>97[a+1a>10[a+1a>32[a+1a>34[a+1a>54[a+1a>50[a+
1a>39[a+1a>91[a+1a>97[a+1a>34[a+1a>57[a+1a>49[a+1a>34[a+1a>57[a+1a>55[a+1a>34[a+1a>52[a+1a>51[a+1a>34[a+1a>52[a+1a>57[a+1a>34[a+1a>57[a+1a>55[a+1a>10[a+1a>32[a+1a>43[a+1a>49[a+1a>97[a+1a>10[a+1a>125[a+1a>10[
a+1a>34[a+1a>49[a+1a>48[a+1a>10[a+1a>62[a+1a>48[a+1a>97[a+1a>10[a+1a>123[a+1a>33[a+1a>91[a+1a>97[a+1a>10[a+1a>32[a+1a>34[a+1a>91[a+1a>97[a+1a>10[a+1a>32[a+1a>43[a+1a>49[a+1a>97[a+1a>10[a+1a>125[a+1a>10[a+1a
[/sourcecode]

Now all you need to do is copy this snippet into quine.bad (with one minor change) to get a bAdkOde quine:

[sourcecode]
>0a
>62[a+1a>48[a+1a>97[a+1a>10[a+1a>34[a+1a>54[a+1a>50[a+1a>34[a+1a>52[a+1a>56[a+1a>34[a+1a>57[a+1a>55[a+1a>34[a+1a>49[a+1a>48[a+1a>10[a+1a>123[a+1a>33[a+1a>91[a+1a>97[a+1a>10[a+1a>32[a+1a>34[a+1a>54[a+1a>50[a+
1a>39[a+1a>91[a+1a>97[a+1a>34[a+1a>57[a+1a>49[a+1a>34[a+1a>57[a+1a>55[a+1a>34[a+1a>52[a+1a>51[a+1a>34[a+1a>52[a+1a>57[a+1a>34[a+1a>57[a+1a>55[a+1a>10[a+1a>32[a+1a>43[a+1a>49[a+1a>97[a+1a>10[a+1a>125[a+1a>10[
a+1a>34[a+1a>49[a+1a>48[a+1a>10[a+1a>62[a+1a>48[a+1a>97[a+1a>10[a+1a>123[a+1a>33[a+1a>91[a+1a>97[a+1a>10[a+1a>32[a+1a>34[a+1a>91[a+1a>97[a+1a>10[a+1a>32[a+1a>43[a+1a>49[a+1a>97[a+1a>10[a+1a>125[a+1a>10[a+1a
>0a
"62"48"97"10
{![a
"62'[a"91"97"43"49"97
+1a
}
"10
>0a
{![a
"[a
+1a
}
[/sourcecode]

The small change I had to make, was to add >0a at the beginning. If you run this bAdkOde program, it will print its source code as output. So there you have it. A bAdkOde quine, which proves that bAdkOde is Turing Complete. I have to thank Dave Cope for his quine tutorial, without which it would have been extremely difficult for me to write a bAdkOde quine!

Update (12/26/2009)

Dave mentioned that writing a quine only suggests that a language is Turing Complete, but not that it is. He suggested that I write an interpreter for Brainfuck which would then prove that bAdkOde is Turing Complete. That was actually my next project!

Update (12/26/2009)

I've been able to provide a direct translation of Brainfuck into bAdkOde, which proves the Turing Completeness of bAdkOde.

1 thought on “A bAdkOde quine (which suggests that bAdkOde is Turing Complete)”

  1. Pingback: bAdkOde is Turing Complete | Rough Book

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Meta

  • Log in
  • Entries feed
  • Comments feed
  • WordPress.org

Archives

  • February 2023
  • April 2020
  • February 2020
  • January 2020
  • December 2019
  • November 2019
  • September 2019
  • August 2019
  • July 2019
  • June 2019
  • May 2019
  • March 2019
  • February 2019
  • January 2019
  • December 2018
  • November 2018
  • September 2018
  • August 2018
  • July 2018
  • June 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • June 2017
  • March 2017
  • November 2016
  • August 2016
  • July 2016
  • June 2016
  • February 2016
  • August 2015
  • July 2014
  • June 2014
  • March 2014
  • December 2013
  • November 2013
  • September 2013
  • July 2013
  • June 2013
  • March 2013
  • February 2013
  • January 2013
  • October 2012
  • July 2012
  • June 2012
  • January 2012
  • December 2011
  • November 2011
  • October 2011
  • September 2011
  • July 2011
  • June 2011
  • May 2011
  • February 2011
  • January 2011
  • December 2010
  • November 2010
  • October 2010
  • September 2010
  • July 2010
  • June 2010
  • May 2010
  • April 2010
  • March 2010
  • January 2010
  • December 2009
  • November 2009
  • October 2009
  • September 2009
  • August 2009
  • July 2009
  • May 2009
  • April 2009
  • March 2009
  • February 2009
  • January 2009
  • December 2008
  • November 2008
  • October 2008
  • August 2008
  • March 2008
  • February 2008
  • November 2007
  • July 2007
  • June 2007
  • May 2007
  • March 2007
  • December 2006
  • October 2006
  • September 2006
  • August 2006
  • June 2006
  • April 2006
  • March 2006
  • January 2006
  • December 2005
  • November 2005
  • October 2005
  • September 2005
  • August 2005
  • July 2005
  • June 2005
  • May 2005
  • April 2005
  • February 2005
  • October 2004
  • September 2004
  • August 2004
  • July 2004
  • June 2004
  • May 2004
  • April 2004
  • March 2004
  • February 2004
  • January 2004
  • December 2003
  • November 2003
  • October 2003
  • September 2003
  • July 2003
  • June 2003
  • May 2003
  • March 2003
  • February 2003
  • January 2003
  • December 2002
  • November 2002
  • October 2002
  • September 2002
  • August 2002
  • July 2002
  • June 2002
  • May 2002
  • April 2002
  • February 2002
  • September 2001
  • August 2001
  • April 2001
  • March 2001
  • February 2001
  • January 2001
  • December 2000
  • November 2000
  • October 2000
  • August 2000
  • July 2000
  • June 2000
  • May 2000
  • March 2000
  • January 2000
  • December 1999
  • November 1999
  • October 1999
  • September 1999
©2023 Rough Book | Built using WordPress and Responsive Blogily theme by Superb
All original content on these pages is fingerprinted and certified by Digiprove