格雷戈里·柴廷
概述
格雷戈里·柴廷（Gregory J. Chaitin，1947—）是阿根廷裔美国计算机科学家和数学家，算法信息论的三大独立发源之一，1966 年独立发现柯尔莫哥洛夫复杂性，并引入了著名的 Ω 常数（停机概率）。
关键内容
核心贡献
- 独立发现柯尔莫哥洛夫复杂性（1966）：与 Solomonoff (1960/1964) 和 Kolmogorov (1965) 独立发现了本质相同的概念
- Ω 常数：定义了随机程序停机的概率 Ω = Σ 2^{-|p|}（对所有停机程序求和），这是一个不可计算的超越数
- 前缀 Kolmogorov 复杂性（1975）：与 Levin (1974) 独立引入了前缀复杂性 [前缀复杂性|K_prefix]，修复了链式法则的技术问题
对 Gödel 不完备定理的信息论解读
Chaitin 用 Kolmogorov 复杂性给出了 Gödel 不完备定理的一个信息论版本：一个公理系统（其复杂性为 K_axioms）不能证明任何"K(x) > K_axioms + c"形式的命题。即一个复杂性有限的形式系统不能证明某个字符串具有超过系统自身复杂性的复杂性。
来源
- raw/books/信息论/09_kolmogorov_1965_three_approaches_to_information.md — Kolmogorov (1965) 深度解析
相关
- 雷·所罗门诺夫 — 算法信息论共同先驱
- 安德烈·柯尔莫哥洛夫 — 算法信息论共同先驱
- 算法信息论 — 开创的学科
- 柯尔莫哥洛夫复杂性 — 独立发现