2
$\begingroup$

I was reading about the concept of quine and in particolar of "reciprocal Quines" for example a Program $A$ that output the code of a program $B$ and vice versa, with the two being written in the same programming language.

Thinking of this particular case I have come to the conclusion that these two program must necessarily submit to certain properties. The first thing that came to my mind is the fact that they cannot have different cardinalities, the reason is easily understood: lets take the case that one of the two (lets say $A$) has a $\gt$ cardinality, so $\mid A \mid\gt\mid B \mid$.

Now we codify this example in a trivial way: $A = 1111$ (|A|=4) and $B = 111$ (|B|=3).
It is evident that $A$ can produce the $B$ code but the reverse cannot happen as $B$ has fewer bits than $A$. The only way for the game to work is that the programs have the exact same length and all the practical examples I have seen online (through high-level programming languages) seem to respect this "supposition" of mine.
A second thing I noticed is the fact that these two codes differ only by a short number of characters.

Am I making any mistakes in these considerations?
Is there a way to calculate the maximum number of difference characters that can exist between the two codes?

I would also appreciate if someone could indicate me some sources for the theoretical study of this particular case of quines, searching online I found only practical examples accompanied by brief explanations on the syntax of programming languages.

$\endgroup$
4
$\begingroup$

I don't see why they should have the same length, given that one can succinctly output large amounts of whitespace using something like

for i=1 to 1000 do
    print " "

So, given any mutual Quines $A$ and $B$, one could surely add 1000 spaces to $A$ and 2000 spaces to $B$ and adjust the programs to use for loops like the above.

$\endgroup$
  • $\begingroup$ I am sorry but cant understand your answer... how can a code with 100 significative instruction (lines) print the exact code of a program with 200 instruction by adding or subtracting white spaces and vice versa? Can you give me pratical exanples? $\endgroup$ – Yamar69 May 27 at 18:24
  • 1
    $\begingroup$ @Yamar69 Add blank lines to both programs until they are 1000 lines both. Then replace a few of these lines with the above for loop, tweaking the "1000" constant in it so to compensate for the difference: you will need to use different constants. $\endgroup$ – chi May 27 at 18:58
  • $\begingroup$ @David Richerby I am sorry but i continue to not understand. lets take program A (pseudocode) = print ("hello"); int a = 1; int b = 2; int c = a+b; print(c); print(a + b + c); print ("end of program"); lets say that the number of characters in this program is n, how can you output this code by a program that has n/2 characters? $\endgroup$ – Yamar69 May 27 at 19:12
  • 1
    $\begingroup$ @Yamar69 Maybe you can't, with that particular program. But the program print "111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111" has 116 characters and it's output by, e.g., print "print \""; for i=1 to 108 do print "1"; print "\"", which has 58 characters. (See Kolmogorov complexity.) $\endgroup$ – David Richerby May 27 at 21:35
  • $\begingroup$ @DavidRicherby thanks for the perseverance, now I understand what you mean, however this trick only works in the trivial case where the difference in length between the two codes is only and exclusively of long printing statement and in any case requires a change to the code of both applications. In all other cases the program lengths must be identical, in fact as I wrote in the question, all the examples that I found online of reciprocals quines, were subject to this property. $\endgroup$ – Yamar69 May 28 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.