24 lines
768 B
Markdown
24 lines
768 B
Markdown
---
|
||
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]]
|