Real number computation through Gray code embedding.
type: Item
instance of: scholarly article
title: Real number computation through Gray code embedding.
zbMATH Open document ID: 1042.68071
DOI: 10.1016/S0304-3975(01)00104-9
author: Hideki Tsuiki
published in: Theoretical Computer Science
publication date: 2002-07-31T00:00:00Z
review text: We propose an embedding \(G\) of the unit open interval to the set \({0,1}_{\perp,1}^{\omega}\) of infinite sequences of \({0,1}\) 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}_{\perp,1}^{\omega}\). We also define a machine called an indeterministic multihead Type 2 machine which input/output sequences in \({0,1}_{\perp,1}^{\omega}\), 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1774173
zbMATH Keywords: Gray code
zbMATH Keywords: Real number computation
zbMATH Keywords: IM2-machines
zbMATH Keywords: Multihead
zbMATH Keywords: Indeterminism
MaRDI profile type: Publication
cites work: Topological properties of real number representations.
cites work: Q4875855
cites work: Q4222886
cites work: A domain-theoretic approach to computability on the real line
cites work: Real number computability and domain theory
cites work: An abstract data type for real numbers
cites work: On the definitions of computable real continuous functions
cites work: The Takagi function and its generalization
cites work: Q3994907
cites work: Q4088800
cites work: Q4023900
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem
cites work: Type 2 recursion theory
cites work: Q4485693
description: scientific article; zbMATH DE number 1774173