How could a quine in my programming language look?

Question

I have created a turing-complete programming language (already proven) so it must be possible to write a quine for it, right?

But all quines I know store their source code in a string and then replace a special character in it using something like chr and ord.

My language only has the following

• Basic arithmetics
• Int and string types
• Variables
• == operator
• Conditional gotos

I have no idea how I could write a quine as I have no real string manipulation available, I can only output constant strings. Yet, it is 100% turing-complete.

Answer 1

If you have integers you can encode or decode strings (schemes as simple as A=1, B=2 etc. are enough to do that). You only need to be able to compare constant strings or to compare int. Hence there seems to be no fundamental problem.

You work with numbers and write things like

if (n == 1) print "A"
if (n == 2) print "B"
...

There can be some practical difficulties. The thing with strings is not that you have characters in it but that they are equivalent to very large numbers. What you need here is either to have access to unlimited precision numbers or to some kind of array of fixed size numbers, or other large data structure. An array of numbers will do for you what a string can do. But if your language is Turing complete it should have a way to easily access some large chunk of memory

A Turing complete language limited to a 32 bits tape (or where you must give a new name to each different memory space of 32 bits) would be a pity, not sure you could write a quine with such restriction. By the way it would be interesting to know how you proved that your language was Turing complete if you don't have arrays or similar structure. The common method I usually use is to implement some Turing Machine using my language. But to do this I need some kind of array to simulate the band.

This kind of encoding is basically what Gödel did in it's theorem of incompletude, find some way to encode logical expressions as integers and then reason on that.

If you give some more elements of syntax, we could even try to do it (if you do not have functions but only gotos, that also will be a problem, but you can also simulate that). The basic problem is that you have to find a way to "compress" your encoded source code. If you have long string constant available it can probably help.

Answer 2

If your language is Turing complete and there is one quine, there most likely are infinitely many of them. Here's a way to construct just some of them:

1. Implement a Brainfuck (or some other simple Turing complete language) interpreter in your language. Write your program such that the source X1<brainfuck source>Y1 when run, interprets the Brainfuck program.
2. Write an algorithm string f(string a, string b) in any language of your choice that when given any a and b outputs a Brainfuck program that when run outputs the string a, the entire Brainfuck source code, then the string b. You can adapt an existing Brainfuck quine to do this.
3. Calculate f(X1, Y1) and then embed the resulting Brainfuck program into your program from 1.

Step one is the most difficult, but you might already have done it because one of the easiest ways to prove that something is Turing complete is to implement an interpreter for another language that has already been proven to be Turing complete.

Step two is proven to be possible already and is independent of your program language.

Step three is a simple calculation.