Talk:Invariance theorem

Untitled

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)

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)

References

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

'Universality'

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)

Entries without a link to a Wikipedia article

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