The length of the shortest program in a given (fixed) programming language that

Question

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.

Explanation / Answer

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 ?M? and our output is min{|x|?M(x)=x}. This is uncomputable: it's uncomputable even whether M(0)=0

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.