Talk:Invariance theorem

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 articles

Mathematics Low‑priority

	Mathematics portal 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 articles
Low	This disambiguation page has been rated as Low-priority on the project's priority scale.

Text and/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.

Untitled[edit]

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:

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]

References[edit]

Ming Li & Paul Vitanyi (1997). An Introduction to Kolmogorov Complexity and Its Applications -- Second Edition. Heidelberg: Springer Verlag. ISBN 0-387-94868-6.

'Universality'[edit]

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]

Entries without a link to a Wikipedia article[edit]

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