The class of continuous functions given by strict finite R-transducers is not too simple
by
Dmitry A. Koval and Leonid P. Lisovik
Kiev National University, Kiev, 01017, Ukraine

Every continuous real function can be presented by R-transducer. Correspondingly it can be presented by computation tree which is infinite labelled tree. Thence macrotransducers over infinite labelled trees can be used to present continuous operators in the functional spaces, for instance, in space C[0, 1]. Now we are able to prove that every continuous real functions given by (finite) R-transducer can be presented as a sum of two continuous real functions given by strict (finite) R-transducers.

Let L be the class of functions of the title of this paper. In previous papers (see [1-3]) it was proved that to the class L belong many interesting examples: nowhere differentiable function, Peano's curve, and various fractal curves. Some convenient extentions of finite R-transducers were proposed in [4]. We continue investigations of possibilities of finite (and strict finite) R-transducers. In this direction the following two new results can be proved.

1. The question of determining value of real number x₀, 0 <= x₀ <= 1, satisfying the condition f(x₀)=sup{f(x) | 0 <= x <= 1}, is not realizable, for the class of continuous real functions, i.e., it cannot be decided with help of deterministic macrotransducer over labelled computation trees. Moreover aforesaid question cannot be decided in such a way even for the case of functions f(x) which belong to the class L.

2. Every continuous real function can be presented as a sum f(x)=f₁(x)+f₂(x) where functions f₁(x), f₂(x) belong to the class L.

Additional information about R-trasducers, macrotransducers and computation trees is presented in review [5]. In paper [2] were investigated R_{(s, t)}-transducers which have s-adic representations for input and t-adic representations for output (with additional digits (t) and ([( -) || t])). Correspondingly the R-trasducers are R_{(2, 2)}-transducers. They have output symbols 0, 1, 2, [`1], [`2] and Ñ. The last symbol is used to present the point in binary notation. The use of symbols 2 and [`2] is essential because we permit only unmixed expansions. An R-transducer is a deterministic sequential machine with control head, input and output tapes. Usually a control head has infinite memory.

In the process of computation the R-transducer transforms from the left to the right any input infinite binary notation into corresponding output infinite binary notation where additional digits 2 and [ _ || 2] (minus 2) are allowed to be used in the output alphabet. An R-transducer A is called a strict R-transducer if it has not digits 2 and [ _ || 2] on the output. An R-transducer A is called a finite R-transducer if its control head has finite memory. The generalization of R-transducer is notion of R_mⁿ-transducer which has m input and n output tapes.

Below we mention one result concerning of existence of finite R₁²-transducer which gives fine Peano's curve.

3. There exists a finite R₁²-transducers B such that f_B:[0, 1] --> [0, 1]² is a continuous surjective function and for every z in [0, 1]² the preimage f_B^-1(z) contains at most three elements (see [3]).

References

[1] L.P. Lisovik, Algorithmic questions for real functions, Kibernetika 1 (1987) 14-20.

[2] L.P. Lisovik, Applications of finite R-transducers for construction of fractal curves, Kibernetika i Systemny Analiz 3 (1994) 11-22.

[3] L.P. Lisovik and O.Ju. Shkaravska, About real functions defined by transducers, Kibernetika i Systemny Analiz 1 (1998) 82-93.

[4] L.P. Lisovik, D.A. Koval, S.V. Martines, R ^* -transducers and fractal curves, Kibernetika i Systemny Analiz 3 (1999) 95-105.

[5] L.P. Lisovik, Three metatheorems on continuity and computability, Theoret. Comput. Sci. (to appear).

Date received: April 2, 2002