5
$\begingroup$

The normal Quine - a program that prints its own code - is a special case of an n-Quine.

An n-Quine is a program that prints code for a different program that after n iterations of printing and running will yield its own source (it has a period of n, and it does not repeat during the first n-1 iterations).

A "super Quine" is a (n>1)-Quine that is shorter than all the shortest n-Quines with smaller n (including the shortest 1-Quine = normal Quine).

When are super Quines possible? It's easy enough to think of a language where they are. But it is hard to think of an example in any general purpose language.

What factor determines the presence or absence of super Quines in a language?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You can find what I think is a 5-Quine here. I'm not sure if that's what you have in mind though. $\endgroup$ – Martin Berger Jan 30 '14 at 20:41
  • 1
    $\begingroup$ You should of course be aware that the property of being a super-Quine is highly undecidable in a general purpose language... $\endgroup$ – cody Jan 30 '14 at 23:40
  • $\begingroup$ @MartinBerger The multi-language case is an interesting one, but makes the task easier in some way as the number of languages enforces as minimal periodicity, but in a well defined sense it might not be shorter, A super Quine would have to be shorter in the same language, or at least it should be shorter with reference to the same reference machine. $\endgroup$ – Lucas Jan 31 '14 at 1:27
  • $\begingroup$ I haven't heared of a super quine, but I know it's possible that there is a program that outputs a quine and is shorter than all quines. $\endgroup$ – Zsbán Ambrus May 10 '14 at 13:03
  • $\begingroup$ @ZsbánAmbrus it's terminology I made up to ask my question. $\endgroup$ – Lucas May 10 '14 at 13:09
2
$\begingroup$

There's a good chance this question is independent of ZFC for most programming languages. In particular, I'd expect it to be true of any language where the shortest Quine is longer than the Kolmogorov complexity decidability bound, the integer $n$ such that no string can be proven to have Kolmogorov complexity $> n$. I don't know to prove this, since even if you could express a Quine by a shorter program it wouldn't be a Quine, but I would expect a similar result to apply.

However, if the above argument were true, the argument itself might also be unprovable in ZFC, since it would require showing that no Quines exist below the complexity bound.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

  • A super quine exists in any language where some n-quines exist: just take the smallest program among all n-quines. I guess you wanted to ask another question.

  • a k-quine is also always a (kn)-quine for any $n$, so the smallest super quine is a super n-quine for infinitely many n

  • in any "acceptable programming language" we can prove that for all n, there exists a program which is a n-quine but not a k-quine for any $k<n$ (Kleene fixed-point theorem).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Re your first bullet point, yes, what assures that the shortest n-quine isn't the 1-quine. Though I admit I didn't specify that a super-quine shouldn't be a 1-quine except by saying it must be shorter than the shortest 1-quine. $\endgroup$ – Lucas May 9 '14 at 23:10
  • $\begingroup$ Also, I would not consider a k-quine to be a kn-quine, the number denotes its period, not a multiple of it. I appreciate the effort though (+1) $\endgroup$ – Lucas May 9 '14 at 23:19
  • $\begingroup$ @Lucas: Yes I knew that your question was about super-quine which are not 1-quine :) $\endgroup$ – user148606 May 10 '14 at 23:37
  • $\begingroup$ What do you mean by "example in a general purpose language"? I think we can artificially produce languages with the full Turing expressiveness but where there is a super-quine which is not a 1-quine. $\endgroup$ – user148606 May 10 '14 at 23:42
  • $\begingroup$ I basically mean in a language that hasn't been constructed specifically to contain a super-quine, but for general computing. Like c or something. $\endgroup$ – Lucas May 11 '14 at 0:39

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.