Talk:Invariance theorem

From Wikipedia, the free encyclopedia

This article incorporates material from PlanetMath, which is licensed under the GFDL.

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:

.

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)

[edit] References

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