The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of possible outputs.

This is a classical result and is easily proven; a proof outline appears in the Wikipedia article on Kolmogorov complexity.

My question is about a related complexity metric operating on programming languages rather than program outputs. A quine is a program that outputs its own source code (and nothing else). Every Turing-complete programming language is capable of formulating quines (by Kleene's recursion theorem). We can therefore define the quine complexity of a programming language as the length of the shortest quine possible in that language.

Is the quine complexity a computable function on the set of programming languages?

My gut tells me that it is not, but the standard approach used to prove the uncomputability of the Kolmogorov complexity metric does not seem to work here.

  • 2
    $\begingroup$ What is your formal definition of "set of programming languages"? $\endgroup$
    – Raphael
    May 26 '14 at 21:22

You need to formally define the computational problem. It appears that the input is "a programming language" and the output is the length of the shortest quine in that language. But how is the programming language specified? The only way I can think of is to specify it by giving the encoding of a Turing machine that interprets the language. So, then, our input is $\langle M\rangle$ and our output is $\min\,\{|x|\mid M(x)=x\}$. This is uncomputable: it's uncomputable even whether $M(0)=0$

  • $\begingroup$ Yes, this definition is what I had in mind. But how can I see (prove) that this function is indeed uncomputable? $\endgroup$
    – user16652
    May 27 '14 at 9:06
  • $\begingroup$ @pew By using the standard fact that it's undecidable whether $M(0)$ even halts, let alone whether it outputs a specific value. $\endgroup$ May 27 '14 at 11:27

Your Answer

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