Content deleted Content added
Tim Retout (talk | contribs) m Link |
Minesweeper (talk | contribs) m wiki |
||
Line 3:
The field was developed by [[Andrey Kolmogorov]] and [[Gregory Chaitin]] starting in the late [[1960s]].
To formalize the above definition of complexity, one has to specify exactly what types of programs are allowed. Fortunately, it doesn't really matter: one could take a particular notation for [[Turing machine|Turing machines]], or [[Lisp programming language|LISP]] programs, or [[Pascal programming language|Pascal]] programs, or [[Java virtual machine]] bytecode. If we agree to measure the lengths of all objects consistently in [[bit|bits]], then the resulting notions of complexity will only differ by a constant factor: if ''I''<sub>1</sub>(''s'') and ''I''<sub>2</sub>(''s'') are the complexitites of the string ''s'' according to two different programming languages ''L''<sub>1</sub> and ''L''<sub>2</sub>, then there are constants ''C'' and ''D'' (which only depend on the languages chosen, but not on ''s'') such that▼
▲If we agree to measure the lengths of all objects consistently in [[bit|bits]], then the resulting notions of complexity will only differ by a constant factor: if ''I''<sub>1</sub>(''s'') and ''I''<sub>2</sub>(''s'') are the complexitites of the string ''s'' according to two different programming languages ''L''<sub>1</sub> and ''L''<sub>2</sub>, then there are constants ''C'' and ''D'' (which only depend on the languages chosen, but not on ''s'') such that
:<math>I_1(s) \le C \cdot I_2 (s) + D </math>
Here, ''D'' is the length of an interpreter for ''L''<sub>2</sub> written in ''L''<sub>1</sub>, and ''C'' describes the overhead of storing programs written in ''L''<sub>2</sub> as part of programs in ''L''<sub>1</sub>.
| |||