实数序是最密的可判定全序关系

简介: 证明部分:定义:可判定全序关系:存在一个有限字母表和其构成的无穷输入序列可以表达所有的元素。存在一台图灵机判定这些无穷序列,即对于任意的,可在有限时间内输出和的大小关系。最密的可判定全序关系:1.该关系属于可判定全序关系2.所有的可判定全序关系可以序嵌入(order-embedding)该关系中。前缀:定义为图灵机判定和的大小关系时,读取的关于和的字符串。严格定义:在可判定全序关系中,将图灵机改写

证明部分:

定义:

  • 可判定全序关系:存在一个有限字母表和其构成的无穷输入序列可以表达所有的元素。存在一台图灵机判定这些无穷序列,即对于任意的,可在有限时间内输出和的大小关系。
  • 最密的可判定全序关系:1.该关系属于可判定全序关系2.所有的可判定全序关系可以序嵌入(order-embedding)该关系中。
  • 前缀:定义为图灵机判定和的大小关系时,读取的关于和的字符串。
    • 严格定义:在可判定全序关系中,将图灵机改写成为双带图灵机模式,输入分别为表示A的纸带和表示B的纸带,在图灵机运行至结束时,所有图灵机读写头经过的纸带格子对应的A与B的原始字符构成的字符序列为图灵机在判断A和B的大小关系时A与B的前缀。
    • 前缀必然是有限序列,因此可以通过前缀构建可数关系。实数可以通过可数序列逼近来定义,完成这种可数构造是完成序嵌入构造的关键点。
    • 一个元素可以对应多个前缀,例如A可以对应。
    • 无妨设,由于与比较时,只有的前缀参与了计算,因此所有具有的前缀的元素都大于。即
    • 记所有前缀构成的集合为

证明:

实数序是可判定全序关系:

利用函数将实数映射到区间上,然后从小数点后第1位开始逐位比较即可。

构造任意可判定全序到实数的映射:

按照如下规则将所有前缀构成的集合进行排列为:

  • 字符少的在字符多的前面。
  • 字符数相等的,则按照字符的自然序进行排列。

按照如下规则,将元素映射到三进制实数集上:从第位开始,对于任意一位,可以取得第个前缀为

  • 若大于所有以为前缀的元素,则第位为。记为
  • 若小于所有以为前缀的元素,则第位为。记为
  • 以上两点都不满足,则第位为。记为

由于每个前缀都是从两个元素的比较中得来,因此每个至少存在一个以为前缀的元素,故这种映射规则是明确的。

记这个映射为,第位为。

映射是序嵌入的:

序保持:任取及任意一位:

在任意一位上,都是序保持的;因此映射都是序保持的。

单射:对于任意的,无妨设,存在两个前缀。设对应的位次为,则:

因此。

讨论:

关于哲学:

一个古老的哲学命题在于探讨究竟什么是实在,什么是表象。罗素的理念中,我们对于椅子的视觉,触觉等都是表象而不是椅子的实在。不过这会引入一个问题,那就是如果我们排除掉所有表象的手段,我们有什么手段能够来认识事物的实在?因此,在关于什么是实在的问题上,我的想法是,本来就不存在什么实在,实在就是所有表象的集合。这个观点进入到实践性的领域则演变成了等于号这个概念不是天然的,相反,大于号与小于号才是天然的概念。序关系的定义优先于等于号的定义,这就引发了一个问题。既然序关系如此底层,是不是存在一个最密的序列,我们的所有序关系本质上是这个序关系的衍生品?这是提出这个问题的出发点。我们可以通过一些反例来看到等于号是如何影响这个命题的。举个例子,在空间上构造一个不可判定的全序关系:。这个关系的不可判定性在于,我们如何知道两个元素是相等的,特别是无限不循环小数?

关于可计算性:

我们是不是可以有如下的思路:将np问题的解空间映射到一个全序的空间中,然后给出对于任意一个排序系统,不通过遍历即可以找到这个排序系统中第k个元素的构成。基于此,我们寻找排序系统的构造方式,并找到最优化的排序系统,以此来寻找解决np=p问题的路径。在本文中,我们给出了一个利用排序进行编码的系统,可以通过探讨这个编码系统本身的复杂度,编码系统的最优化来做一些工作。

目录
相关文章
|
7月前
一个16位的数以4位为一组分割,然后将各部分相加获取最终结果。
一个16位的数以4位为一组分割,然后将各部分相加获取最终结果。
|
4月前
【高数】常数项级数概念与性质
【高数】常数项级数概念与性质
|
6月前
技术心得:实数域的戴德金分划和有理数域的戴德金分划,以及戴德金原理
技术心得:实数域的戴德金分划和有理数域的戴德金分划,以及戴德金原理
34 0
|
7月前
|
Web App开发
求最小函数依赖集:求候选键(例题讲解)超详细,易理解
求最小函数依赖集:求候选键(例题讲解)超详细,易理解
133 1
|
7月前
29.输入三个实数,判断能否构成三角形;若能,再说明是何种类型的三角形
29.输入三个实数,判断能否构成三角形;若能,再说明是何种类型的三角形
65 0
|
数据挖掘 大数据
为什么相关不等于因果
相关不等于因果。 图表也会说谎,并非所有的相关性都蕴含因果关系。相关性是科学分析的重要组成部分,但如果使用不当,会带来很多误导。更可怕的是还有人会对图表巧妙包装,将图表设计的更具欺骗性。此时我们需要拿出因果为武器,驱逐虚假关联。
98 0
为什么相关不等于因果
|
算法 数据可视化 数据挖掘
RNAseq|组学分型-ConsensusClusterPlus(一致性聚类), NMF(非负矩阵分解)
RNAseq|组学分型-ConsensusClusterPlus(一致性聚类), NMF(非负矩阵分解)
1134 0
|
移动开发 JavaScript
集合论—关系的运算和性质
集合论—关系的运算和性质
|
机器学习/深度学习 vr&ar
矩阵的等价,相似,合同,正定判定和关系
如果矩阵可逆,那么它的逆矩阵和它的伴随矩阵之间只差一个系数。然而,伴随矩阵对不可逆的矩阵也有定义,并且不需要用到除法。
1476 0
矩阵的等价,相似,合同,正定判定和关系
01:判断数正负
01:判断数正负
119 0