« Diverse länkar med ett tema samt en TUNPMÄÄ | Main | En lite längre länklista »
november 13, 2004
John Allen Paulos: Complexity, Randomness and Impossible Tasks
I John Allen Paulos senaste kolumn Complexity, Randomness and Impossible Tasks: A Mathematical Approach to Understanding Complexity diskuteras komplexitet och de näraliggande begreppen ordning och slump.
Some things are simple, some are complicated. What makes them so? In fields ranging from biology to physics to computer science, we're often faced with the question of how to measure complexity.
The flavor of the subject can perhaps be sampled by considering this question: Why is it that the first sequence of 0's and 1's below is termed orderly or patterned and the second sequence random or patternless? (Note that since almost everything from DNA to symphonies to this very column can be encoded into 0's and 1's, this is not as specialized a question as it may at first appear.)
(A) 0010010010010010010010010010010010010010010 …
(B) 1000101101101100010101100101111010010111010 …
Answering this question leads not only to the definition of algorithmic complexity, but also to a better understanding of (a type of) randomness as well as a proof of the famous incompleteness theorem first proved by the Austrian mathematician Kurt Godel.
Hang on. The ride's going to be bumpy, but the view will be bracing.
Att t.ex. vidare se:
G J Chaitin Home Page
Andrey Nikolaevich Kolmogorov (biografi)
Kolmogorov Complexity and Solomonoff Induction
Posted by hakank at november 13, 2004 09:03 FM Posted to Diverse vetenskap