|
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 machines, or LISP programs, or Pascal programs, or [recursive function]?s. If we agree to measure the lengths of all objects consistently in bits, then the resulting notions of complexity will only differ by a constant: if IT(s) is the complexity of the string s when Turing machines are used for the definition, and IL(s) is the complexity of the string s when LISP programs are used, then there is a constant C such that for all strings s: |
|
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 machines, or LISP programs, or Pascal programs, or [recursive function]?s. If we agree to measure the lengths of all objects consistently in bits, then the resulting notions of complexity will only differ by a constant: if IT(s) is the complexity of the string s when Turing machines are used for the definition, and IL(s) is the complexity of the string s when LISP programs are used, then there is a constant C such that for all strings s: |
|
Similar ideas are used to prove the properties of Chaitin's constant. |
![[Home]](wikipedia.png)