This disambiguation page does not require a rating on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Disambiguation This disambiguation page is within the scope of WikiProject Disambiguation, an attempt to structure and organize all disambiguation pages on Wikipedia. If you wish to help, you can edit the page attached to this talk page, or visit the project page, where you can join the project or contribute to the discussion.DisambiguationWikipedia:WikiProject DisambiguationTemplate:WikiProject DisambiguationDisambiguation Mathematics This disambiguation page is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics

Text or other creative content from Invariance theorem was copied or moved into Kolmogorov complexity with this edit. The former page's history now serves to provide attribution for that content in the latter page, and it must not be deleted as long as the latter page exists.

Why is it a theorem if it "follows trivially from the definition of a universal turing machine"? Is there something more to it that I'm missing?--208.120.106.136 (talk) 08:43, 30 December 2007 (UTC)Reply

Although not problematic to those familiar with the diatype, at its face, the main connective of this formula is ambiguous:

${\displaystyle C(x)=C_{U}(x)\leq C_{M}(x)+c}$.

An explanation of the meanings of C(x), C_U(x) and C_M(x) will also be needed. These explanations will likely be found in Li and Vitanyí's book. Since I don't have it handy, can anyone help clarify this theorem?

Also, in my opinion, any math article concerning a theorem should have (1) an informal statement of the theorem, (2) why it is significant, (3) an informal sketch of one of its proofs, and (4) eventually show a more formal proof. Vonkje 14:06, 23 July 2005 (UTC)Reply

Ming Li & Paul Vitanyi (1997). An Introduction to Kolmogorov Complexity and Its Applications -- Second Edition. Heidelberg: Springer Verlag. ISBN 0-387-94868-6.{{cite book}}: CS1 maint: publisher location (link)

I added the word 'universal' at the last sentence of the proof. It could read 'invariant', but some texts refer to prefix programming languages as needing the two properties:

• Prefix-free
• Universal (invariance theorem)

This seemed to give clarity, but I feel it leaves the rest of article open to reinterpretation, i.e. what do we really mean by 'optimal'? --☯Lightbound☯ ^talk 07:56, 19 April 2012 (UTC)Reply

I think it is useful to list also entries for which no article exists yet. Wilkibur 00:18, 6 November 2016