Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657243 | The Journal of Logic and Algebraic Programming | 2005 | 24 Pages |
Abstract
As shown in [H. Tsuiki, Real number computation through gray code embedding, Theoretical Computer Science 284 (2002) 467], the real line can be embedded topologically in the set Σâ¥,1Ï of infinite sequences of {0, 1, â¥} containing at most one â¥. Moreover, there is a nondeterministic multi-headed machine, called an IM2-machine, which operates on Σâ¥,1Ï and which induces the standard notion of computation over the reals via this embedding. In this paper, we study how the behavior of an IM2-machine can be expressed in “real” programming languages. When we use a lazy functional language like Haskell and represent a sequence as an infinite list, we cannot express the behavior of an IM2-machine. However, when we use a logic programming language with guarded clauses and committed choice, such as Concurrent Prolog, PARLOG, and GHC (Guarded Horn Clauses), we can express the behavior of IM2-machines naturally and execute them on an ordinary computer. We show that GHC-computability implies IM2-computability but not vice versa when we consider functions defined on Σâ¥,1Ï in general, but they coincide when we only consider functions defined on the reals. We give some GHC program examples, such as the conversions between Gray-code and the signed-digit representations, and the addition function on reals.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hideki Tsuiki,