Quine (computing)

related topics
{math, number, function}
{work, book, publish}
{system, computer, user}
{theory, work, human}

A quine is a computer program which produces a copy of its own source code as its only output. The standard terms for these programs in the computability theory and computer science literature are self-replicating programs, self-reproducing programs, and self-copying programs.

A quine is a fixed point of an execution environment, when the execution environment is viewed as a function. Quines are possible in any programming language that has the ability to output any computable string, as a direct consequence of Kleene's recursion theorem. For amusement, programmers sometimes attempt to develop the shortest possible quine in any given programming language.

The name "quine" is coined by Douglas Hofstadter in his popular science book Gödel, Escher, Bach: An Eternal Golden Braid in the honor of philosopher Willard Van Orman Quine (1908–2000), who made an extensive study of indirect self-reference, and in particular for the following paradox-producing expression, known as Quine's paradox:

"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.

The name has become popular between amateur enthusiasts and programming hobbyists although it is not adopted by computer scientists.

A quine takes no input. Allowing input would permit the source code to be fed to the program via the keyboard, opening the source file of the program, and similar mechanisms.

In some languages, an empty source file is a fixed point of the language, producing no output. Such an empty program, submitted as "the world's smallest self reproducing program", once won the "worst abuse of the rules" prize in the Obfuscated C contest.[1]

Contents

History

The idea of self-reproducing programs first appeared in Bratley, Paul and Jean Millo. "Computer Recreations; Self-Reproducing Automata", Software -- Practice & Experience, Vol. 2 (1972). pp. 397-400. Bratley first became interested in self-reproducing programs after seeing the first known such program written in Atlas Autocode at Edinburgh in the 1960s by the University of Edinburgh lecturer and researcher Hamish Dewar. This program appears below:

Full article ▸

related documents
Tychonoff space
Separation axiom
Cardinality
Gamma function
Heapsort
Inverse limit
Banach fixed point theorem
Julia set
Blackboard bold
Antiderivative
Polytope
Probability space
Separable space
Linear equation
Mersenne prime
Exact sequence
Division algebra
Constant of integration
Search algorithm
Power set
Topological group
Golomb coding
Symmetric group
Liouville number
Max-flow min-cut theorem
Boolean algebra (structure)
Analytic geometry
Hypercomplex number
Supervised learning
Finite difference