A quine is a program that writes itself.

Consider the syntax: <Function> : <Argument>

For example:

(1) Write this twice : Write this twice would output  Write this twice Write this twice 

(2) Write this twice : Write this twice : would output  Write this twice : Write this twice :

We are working with a register machine in the recursion theory class, and we wrote a quine in it. Later I wrote a quine in scheme and then tried writing one in C. That set me thinking as to whether the problem of being able to write a quine in a given language L was decidable. Is there a formal method to prove that a quine, or other quine like programs can be written in an arbitrary language? Talking to Roshan and Ramyaa about this, we concur that if the language is turing complete [i.e you can build a universal turing machine or eqvt (in lambda calculus, pi calculus)] then it should be possible to model a quine in it. You can find some quine implementations in different programming languages at http://www.nyx.net/~gthompso/quine.htm

We are working on a Register Machine (RM) with 7 possible instructions:

0*m# - add 0 at the end of Rm
1*m# - add 1 at the end of Rm
**m# - add * at the end of Rm
*0m# - add # at the end of Rm
n#    - go forward n steps
n*#   - go backward n steps
n**#  - cases on Rn in the order empty, 0, 1, *, #

I have 7 problems for the weekend, one of the interesting problems is to write twin programs s1 and s2 with the properties that s1 <> s2 and a) running s1 with all registers empty gives s2 in R1 b) running s2 with empty registers gives s1 in R1. Phew!

I wrote a scheme parser and interpreter for the langauge, so I can write code and execute it. If anybody wants a copy, drop me an email.