Real number computation through Gray code embedding
Real number computation through Gray code embedding
复制标题
DOI：
10.1016/s0304-3975(01)00104-9
复制
发表时间：
2002-07-28
影响因子：
1.1
通讯作者：
Tsuiki, H
中科院分区：
文献类型：
--
作者：
Tsuiki, H
我们提出了一种单位开区间到集合 {0, 1}（垂直于）(ω),(1)的嵌入 G，该集合由最多有一个未定义元素的 10, 11 的无限序列组成。这种嵌入基于格雷码，是一种拓扑嵌入，在{0, 1}(垂直于)(ω),(1)上具有自然拓扑结构。我们还定义了一种叫做不确定多头第 2 类机器的机器，它的输入/输出序列在{0,1}（垂直于omega）,(1)上，并证明通过嵌入 G 在实函数上引起的可计算性概念等同于有符号数字表示和第 2 类机器引起的可计算性概念。我们还证明，基本算法可以根据这个嵌入自然地表达出来。(C) 2002 Elsevier Science B.V. 版权所有。保留所有权利。
We propose an embedding G of the unit open interval to the set {0, 1}(perpendicular to)(omega),(1) of infinite sequences of 10, 11 with at most one undefined element. This embedding is based on Gray code and it is a topological embedding with a natural topology on {0, 1}(perpendicular to)(omega),(1). We also define a machine called an indeterministic multihead Type 2 machine which input/output sequences in {0,1}(perpendicular toomega),(1). and show that the computability notion induced on real functions through the embedding G is equivalent to the one induced by the signed digit representation and Type 2 machines. We also show that basic algorithms can be expressed naturally with respect to this embedding. (C) 2002 Elsevier Science B.V. All rights reserved.