Gray-code representation of real number and the induced computability structure

我们研究了由{0，1，bot}-无穷序列表示(格雷码表示)和不确定多头机(IM2-Machine)操作的实数的可计算结构的计算、拓扑和论域理论问题。1.IM2-机可以用GHC(Guarded Horn子句)之类的逻辑程序设计语言实现。当我们考虑{0，1，bot}-无限序列上的函数时，可用GHC表示的函数集大于可用IM2计算的函数集，但当仅考虑实数表示时，它们是相等的。2.IM2-机器不能用函数式语言实现，但通过用顺序图归约规则而不是项归约规则实现的受限AMB算子来扩展函数式语言，可以实现IM2-机的能力。我们将其实现为Haskell语言的扩展。3.表示一个拓扑空间所需的底数与该空间的拓扑维相等。我们在代数域上得到了一个更一般的结果，并从区域理论上证明了这一点。4.拓扑空间的编码和子基是密切相关的。产生自然计算结构的编码将产生一个基于正则开集对的并矢子基。格雷码表示的效率可以通过相应子基的性质来表征，这些性质是从拓扑学上研究的。

We studied computational, topological, and domain-theoretic problems related to the computable structure of real numbers derived form representation with {0,1,bot}-infinite sequences (Gray-code representation) and indeterministic multi-head machine (IM2-machine) operating on them.1.IM2-machines can be realized with logic programming languages with guards like GHC (Guarded Horn Clauses). The set of functions expressible in GHC is larger than the set of IM2-computable functions when we consider functions over {0,1,bot}-infinite sequences but they are equal when only real number representation is considered.2.IM2-machines cannot be realized with functional languages, but by extending a functional language with a restricted amb operator which is realized with sequential graph reduction rules instead of term reduction rules, one can implement the ability of IM2-machines. We have implemented it as an extension of the Haskell language.3.The number of bottoms required to represent a topological space and the topological dimension of the space is equal. We have a more general result on an algebraic domain, which is proved domain-theoretically.4.Codings and subbases of a topological space are closely related. Codings which induce natural computational structure will induce a dyadic subbase, which is based on pairs of regular open sets. The efficiency of the Gray-code representation can be characterized through properties of the corresponding subbase, which are studied topologically.