Iota和Jot
在形式语言理论和计算机科学中，Iota（ι，发音如希腊字母 iota）和Jot（י，发音如希伯来字母 yodh）是两种极简的形式系统与编程语言。 这两个名称分别取自希腊语字母Ι（iota）和希伯来语字母Yodh（י/yodh）——分别是各自字母表中最小、最简单的字母，这一命名恰如其分地体现了这些语言的极简主义设计哲学。 它们的设计目标是比λ演算以及SKI组合子演算等更为人熟知的图灵完备系统更加简洁、更加基础。 因此，它们也被归类为图灵焦…
标签：#算法信息论
共 7 篇文章
柴廷常數
在计算机科学的算法信息论中，柴廷常数（也称柴廷欧米茄数）或任意随机图灵机停机的概率是一个实数。即，柴廷常数代表着随机生成的程序在通用图灵机上最终将会停机的概率。这一数字被格雷戈里·柴廷所构造。 即便有无穷多个最终停机的概率（存在无穷多个针对特定图灵机的停机概率常数），我们使用字母 \Omega 表示特定的前缀无符号通用图灵机最终停机的概率的统称。由于 \Omega 取决于图灵机具体编码的细节，因此在不指代任何特定图灵机的编码方式时，它常…
柯氏复杂性
在算法信息论（计算机科学和数学的一个分支）中，一个对象比如一段文字的柯氏复杂性（亦作柯尔莫哥洛夫复杂性、描述复杂性、柯尔莫哥洛夫-复杂度、随机复杂度，或算法熵）是衡量描述这个对象所需要的信息量的一个尺度。柯氏复杂性是由安德雷·柯尔莫哥洛夫于1963年发现，所以用他的名字命名。 以下面的两个长度为64的字符串为例。 01010101010101010101010101010101010101010101010101010101010101…
伪随机数生成器
伪随机数生成器（，），又被称为确定性随机位元生成器（，），是一个生成数字序列的算法，其特性近似于随机数序列。伪随机数生成器生成的序列并不是完全随机，生成的每一个数完全由一个初始值决定，这个初始值被称为随机种子（种子有时使用接近于完全随机的硬件随机数生成器生成）。尽管硬件随机数生成器可以生成接近于完全随机的序列，但伪随机数生成器因为其生成速度和可再现的优势，在实践中显得尤为重要。 '多用於仿真（例如蒙地卡羅方法）、电子游戏（例如程序化生成…
计算不可区分性
在算法分析和密码学中，如果没有高效的算法可以区分两个分布族之间的差异（或区分出两者的概率可以忽略），那么两个分布族被称为是计算不可区分（）的。 正式定义 令\scriptstyle\{ D_n \}_{n \in \mathbb{N}}和\scriptstyle\{ E_n \}_{n \in \mathbb{N}} 是两个，下标n（通常指输入的长度）是。如果对于任意的概率多项式时间算法 A，以下值是一个n上的可忽略函数，则我们说它们在…
算法信息论
算法信息论（Algorithmic information theory）是使用理论计算机科学的工具，研究复杂性概念的学科领域。它是信息理論的一環，关注計算與信息之間的關係。按照Gregory Chaitin的说法，它是“把香农的信息论和图灵的可计算论放在调酒杯使劲摇晃的结果。”
所罗门诺夫的归纳推理理论
所罗门诺夫的归纳推理理论（Solomonoff's theory of inductive inference）是对奥卡姆剃刀叙述的数学化描述。该理论指出：在所有能够完全描述的已观测的可计算类中，较短的可计算理论在估计下一次观测结果的概率时具有较大的权重。简而言之，在几组可以给出的答案的假设论述中，假设越少的越被大家选择。引申为“越简单的越易行”。 参考资料