<p>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 $&gt; 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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-10T19:03:12.073Z
2014-05-10T19:14:02.250Z
2014-05-10T19:14:02.250Z
Geoffrey Irving
<ul>
<li><p>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.</p></li>
<li><p>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</p></li>
<li><p>in any "<a href="http://en.wikipedia.org/wiki/Admissible_numbering" rel="nofollow">acceptable programming language</a>"  we can prove that for all n, there exists a program which is a n-quine but not a k-quine for any $k&lt;n$ (Kleene fixed-point theorem).</p></li>
</ul>

CC BY-SA 3.0
2014-05-09T23:10:54.213Z
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.
Lucas
CC BY-SA 3.0
2014-05-09T23:19:22.790Z
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)
Lucas
CC BY-SA 3.0
2014-05-10T23:37:47.877Z
@Lucas: Yes I knew that your question was about super-quine which are not 1-quine :)
user148606
CC BY-SA 3.0
2014-05-10T23:42:16.080Z
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.
user148606
CC BY-SA 3.0
2014-05-11T00:39:44.357Z
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.
Lucas
CC BY-SA 3.0
2014-05-09T22:58:58.680Z
2014-05-09T22:58:58.680Z
user148606
<p>The normal Quine - a program that prints its own code - is a special case of an n-Quine.</p>

<p>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).</p>

<p>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).</p>

<p>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.</p>

<p>What factor determines the presence or absence of super Quines in a language?</p>

CC BY-SA 3.0
2014-05-10T13:03:49.563Z
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.
Zsbán Ambrus
CC BY-SA 3.0
2014-05-10T13:09:02.453Z
@ZsbánAmbrus it's terminology I made up to ask my question.
Lucas
CC BY-SA 3.0
2014-05-10T13:33:33.803Z
Sure, I mean I haven't heared of any real language where super quines exist.
Zsbán Ambrus
CC BY-SA 3.0
2014-05-10T13:38:51.893Z
Ah, OK. Your original point seems to be intuitively correct.
Lucas
CC BY-SA 3.0
2014-01-30T20:41:46.213Z
You can find what I think is a 5-Quine [here](http://blog.sigfpe.com/2011/01/quine-central.html). I'm not sure if that's what you have in mind though.
Martin Berger
CC BY-SA 3.0
2014-01-30T23:40:28.407Z
You should of course be aware that the property of being a super-Quine is highly undecidable in a general purpose language...
cody
CC BY-SA 3.0
2014-01-31T01:27:26.610Z
@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.
Lucas
<fl.formal-languages><pl.programming-languages><recursion>
Higher order Quines - when do super Quines exist?
Lucas
# Higher order Quines - when do super Quines exist?

(Asked by: username_0 on 2014-01-30)

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?

**Tags:** fl.formal-languages, pl.programming-languages, recursion

> **Comments:**
> **username_2**: You can find what I think is a 5-Quine [here](http://blog.sigfpe.com/2011/01/quine-central.html). I'm not sure if that's what you have in mind though.  
> **username_3**: You should of course be aware that the property of being a super-Quine is highly undecidable in a general purpose language...  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: @ZsbánAmbrus it's terminology I made up to ask my question.  
> **username_1**: Sure, I mean I haven't heared of any real language where super quines exist.  
> **username_0**: Ah, OK. Your original point seems to be intuitively correct.  

---

## 2 answers

### Answer by username_4 on 2014-05-10. Score: 2

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.


---

### Answer by username_5 on 2014-05-09. Score: 1

* 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](http://en.wikipedia.org/wiki/Admissible_numbering)" we can prove that for all n, there exists a program which is a n-quine but not a k-quine for any $k

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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)  
> **username_5**: @username_0: Yes I knew that your question was about super-quine which are not 1-quine :)  
> **username_5**: 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.  
> **username_0**: 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.  

---

