An Extension of Interval-Valued Computing Equivalent to Red-Green Turing Machines

Abstract

Interval-valued computing is a kind of massively parallel computing. It operates on specific subsets of the interval [0,1) - unions of subintervals. They serve as basic data units and are called interval-values. It was established that this system (in its unrestricted version) has computing power equivalent to Turing machines, by a rather simple observation. However, this equivalence involves an infinite number of interval-valued variables. In this paper, a more refined equivalence is established using only a fixed number of interval-valued variables. This fixed number depends only on the number of states of the Turing machine - logarithmically. This method makes it also possible to extend interval-valued computations into infinite length to capture the computing power of red-green Turing machines.