Content deleted Content added
Andre Engels (talk | contribs) mNo edit summary |
texification |
||
Line 6:
Fortunately, it doesn't really matter: one could take a particular notation for [[Turing machine|Turing machines]], or [[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
:
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>.
Line 21:
Now for Chaitin's incompleteness result: though we know that most strings are complex in the above sense, the fact that a specific string is complex can never be proven (if the string's length is above a certain threshold). The precise formalization is as follows. Suppose we fix a particular consistent [[axiomatic system]] for the [[natural number|natural numbers]], say [[Peanos axioms|Peano's axioms]]. Then there exists a constant ''L'' (which only depends on the particular axiomatic system and the choice of definition of complexity) such that there is no string ''s'' for which the statement
:
can be proven within the axiomatic system (even though, as we know, the vast majority of those statements must be true). Again, the proof of this result is a formalization of Berry's paradox.
| |||