一般情况下，概率与概率密度都是在连续区间上取值的实数，这导致随机变量的各阶矩也往往如此。而数字计算机并不能直接处理连续取值，实践中我们往往不得不按照人工设定的精度进行截断。离散化究竟会不会造成关键信息的损失？这个问题可以通过假设能够处理连续实值输入的计算模型中找到答案。
处理离散输入的标准计算模型是图灵机，不失一般性，我们设其输入/输出皆为自然数。
在此条件下，Yuri Matiyasevich定理指明：图灵机可枚举的非空集合恰好是可被整系数多项式生成的解集——丢番图集，更进一步地研究表明，图灵机可枚举的非空集合都能被定义成：
其中P（）为某个整系数多项式，其形式不随式中x参数的取值而变化。
粗略地说，图灵机对自然数的识别能力等同于整系数多项式。
Yuri Matiyasevich以此解决了希尔伯特第十问题：判定任意丢番图集的算法即能判定任意图灵机的枚举集，而后者的算法显然不存在（对角线可证），故第十问题的答案为否定。
虽然将图灵机直接推广到实数域看起来无从下手，但将整系数多项式推广到实数域却是简单直接得多了。
试探定义：实数域可枚举的非空集合是能被表示为
的集合。其中P（）为某个整系数多项式，其形式不随式中x参数的取值而变化。
从定义可以直接看出，这类集合只含有代数数。
有鉴于此，我们不妨认定：
只有能力止于识别代数数的计算模型，适合作为图灵机（在实数域上）的合理推广。
网友评论