8
$\begingroup$

A Quine is a computer program which produces a copy of its own source code as its only output. Is there any Quine program that could print itself out n times, with n specified some way in the program?

$\endgroup$
  • $\begingroup$ Could you please provide more information about what is a Quine program? (Also please read the FAQ and how to ask a good question if you have not read yet.) $\endgroup$ – Kaveh Oct 1 '10 at 4:01
  • $\begingroup$ @Kaveh: I re-added the logic tag. Quines originate in logic and the study of self-reference, self-application, etc, so it seem apropos. $\endgroup$ – Per Vognsen Oct 1 '10 at 4:44
  • $\begingroup$ A great resource on quines: nyx.net/~gthompso/quine.htm $\endgroup$ – Sylvain Peyronnet Oct 1 '10 at 10:05
  • 3
    $\begingroup$ Btw, I don't think there is any need to write the code of such a program, the existence follows easily from Kleene's fixed point theorem. $\endgroup$ – Kaveh Oct 1 '10 at 12:27
  • 1
    $\begingroup$ @Kaveh: Yes I suspect that the term "Quine program" has been coined by Hofstadter in GEB (he certainly coined the verb "to aritmoquine"). But I'm not 100% sure. I heartily recommend everyone to read GEB (at least, everyone interested in Logic and/or Artificial Intelligence). IMHO, it is a masterpiece. $\endgroup$ – Giorgio Camerani Oct 1 '10 at 16:21
9
$\begingroup$

Fun question! As a base I will use this Haskell quine I found on Wikipedia:

main=putStr(p++show(p))where p="main=putStr(p++show(p))where p="

You can make it print out two copies of itself by replacing the occurrences of p++show(p) with p++show(p)++p++show(p). If you see why, the pattern to achieve variable repetition should be clear.

I will be using the following function that calculates the nth iterate of f on x:

iterateN n f x = (iterate f x) !! n

I'll assume it's available as a library function. You can easily embed its definition directly in the quine, but that would clutter the presentation without good reason. Now the rest is simple:

main=putStr(iterateN 42(++(p++show(p)))[])
  where p="main=putStr(iterateN 42(++(p++show(p)))[])where p="

The line break was inserted to aid readability; remove it if you want exact self-replication.

$\endgroup$
  • $\begingroup$ Very nicely done! $\endgroup$ – arnab Oct 1 '10 at 4:35
9
$\begingroup$

You can also proof the existence of such programs without giving an example.
Let $(\Phi_i)$ be the list of all partial computable functions. Clearly there is a partial computable function $\varphi(k)$ which prints the input $k$ n times. So there is an Index $e$ with $\varphi(k) = \Phi_e(k)$. Using the smn-theorem we see that there is a computable function $f$ with $\Phi_{f(k)} = \Phi_e(k) = \varphi(k)$ for all $k$. Now we can apply the recursion theorem and get an $s$ with $\Phi_{f(s)} = \Phi_s$. So $\Phi_s$ is a program which outputs $s$ n times.

$\endgroup$
3
$\begingroup$

Here is another one, based on the printf-version on wikipedia:

main() { int i=5; char *s="main() { int i=5; char *s=%c%s%c; while (i--)
  printf(s,34,s,34); }"; while (i--) printf(s,34,s,34); }`

Though it is short, it is actually not so nice, as it lacks the inclusion for printf, as well as the counter has to be specified twice. A slightly longer version cures both issues:

#include <stdio.h>
#define k 5
main() { int i=k; char *s="#include <stdio.h> %c#define k %d%cmain() { int i=k;
  char *s=%c%s%c; while (i--) printf(s,10,k,10,34,s,34); }";
  while (i--) printf(s,10,k,10,34,s,34); }
$\endgroup$

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.