tailieunhanh - ALGORITHMIC INFORMATION THEORY - CHAPTER 8

Incompleteness Phát triển các hình thức lý thuyết thông tin cần thiết trong Chương 6, và sau khi nghiên cứu các khái niệm về một thực tế ngẫu nhiên trong Chương 7, chúng ta có thể bắt đầu để lấy được các định lý không đầy đủ. Thiết lập như sau. Các tiên đề của một lý thuyết chính thức được coi là mã hóa như là một chuỗi bit duy nhất của đêm, các quy tắc suy luận được coi là một thuật toán để liệt kê các định lý các tiên đề, và nói chung chúng ta sẽ. | Chapter 8 Incompleteness Having developed the necessary information-theoretic formalism in Chapter 6 and having studied the notion of a random real in Chapter 7 we can now begin to derive incompleteness theorems. The setup is as follows. The axioms of a formal theory are considered to be encoded as a single finite bit string the rules of inference are considered to be an algorithm for enumerating the theorems given the axioms and in general we shall fix the rules of inference and vary the axioms. More formally the rules of inference F may be considered to be an . set of propositions of the form AxiomsHyTheorem . The . set of theorems deduced from the axiom A is determined by selecting from the set F the theorems in those propositions which have the axiom A as an antecedent. In general we ll consider the rules of inference F to be fixed and study what happens as we vary the axioms A. By an n-bit theory we shall mean the set of theorems deduced from an n-bit axiom. Incompleteness Theorems for Lower Bounds on Information Content Let s start by rederiving within our current formalism an old and very basic result which states that even though most strings are random 197 198 CHAPTER 8. INCOMPLETENESS one can never prove that a specific string has this property. As we saw when we studied randomness if one produces a bit string s by tossing a coin n times of the time it will be the case that 77 s n H nỴ In fact if one lets n go to infinity with probability one H s n for all but finitely many n Theorem R5 . However Theorem LB Chaitin 1974a 1974b 1975a 1982b Consider a formal theory all of whose theorems are assumed to be true. Within such a formal theory a specific string cannot be proven to have information content more than 0 1 greater than the information content of the axioms of the theory. . if uH s n is a theorem only if it is true then it is a theorem only if n 77 axioms 0 1 . Conversely there are formal theories whose axioms have information .