---
title: 蔡廷常数 Ω (Chaitin's Constant)
created: 2025-04-15
updated: 2026-05-01
type: concept
tags: []
sources: []
---

# 蔡廷常数 Ω (Chaitin's Constant)

- **领域**: 算法信息论
- **定义者**: Gregory Chaitin
- **来源**: [[godel-incompleteness-tutorial|哥德尔不完备定理教程]]

## 概述

Ω = Σ_{p: U(p)↓} 2^{-|p|}，即随机输入一个程序时通用图灵机停机的概率。Ω 具有不可计算性（无法计算任意位）、不可压缩性（前 n 位的信息量至少为 n）和完备性（前 n 位足以判定所有长度 ≤ n 的停机问题）。

> 📌 *占位符页面 — 待补充完整内容。*

## 相关概念
[[chaitin-algorithmic-information-theory]] · [[kolmogorov-complexity]] · [[halting-problem]]