Talk:Reductibility

From Wikipedia, the free encyclopedia

I think this is an article about Kolmogorov-Chaitin complexity, but the author doesn't seem to realize that, or at least doesn't know how to say so. Michael Hardy 01:57, 8 Nov 2003 (UTC)

Connection to Chaitin and Kolmogorov was explicitly given in previous pages that have been deleted (re. Cognition theory, and Cognitics).

Since the time Chaitin-Kolmogorov theory was established, progress has been made.

In MCS cognition theory, complexity has been defined in a different way, with the additional benefit of being given a unit:

"Complexity is the quality of a domain which requires a lot of information to be exhaustively described. The unit to measure it is the bit".

Another cognitive property in MCS is knowledge, which, in short, is the property of a person or system capable of generating the pertinent information.

In the new framework, the problem of Chaitin and Kolmogorov theory appears to be the following: the assessment of complexity is made NOT for a domain directly, but somehow for the knowledge to generate it.

In Chaitin-Kolmogorov views a complex domain becomes simpler if we find a simpler knowledge to generate it. In MCS theory, a complex domain remains always complex; but it may be reductible, i.e. it may be generated by some simpler knowledge. Now a big difference in practice is that if we rely on knowledge, knowledge will not be sufficient: one will need time and implementation ("a cognitive engine") in order to run the knowledge and to yield the actual domain (information).

In summary there is a crucial difference between a domain intrinsically simple and a complex domain which is reductible.

(In MCS, simplicity as been defined as the quality of a domain which requires little information to be exhaustively described. The unit for simplicity is the inverse of the one for complexity: 1/bit.) Dessimoz 15:32, 12 Nov 2003 (UTC)