Shkaravs'ka O. Classes of the functions defined by transducers ovar superwords.

Українська версія

Thesis for the degree of Candidate of Sciences (CSc)

State registration number

0499U001266

Applicant for

Specialization

  • 01.10.08 -

31-05-1999

Specialized Academic Board

Д 26.001.18

Taras Shevchenko National University of Kyiv

Essay

In this paper, are considered the class of transducers over infinite symbolic representations of real numbers. The computational portentialities of these transducers as means of defining continuous real functions and fractal sets are studied. Turing machines, in particular finite automata, can define real functions. From this point of view the finite automata and generalized sequentail machinies were first studied by S.Eilenberg. A finite automaton sequentially works over the finite binary expansion of x to define f(x) for the corresponding function f.The notion of the R-transducer introduced by L.P.Lisovik generalizes Eilenberg‘s approach. Finite R-transducers can be asynchronic and difine the mapping of binary expansions into the set of so called overflowed expansions. (The symbol 2 is allowed in the overflowed expansion of an arbitrary real number). Later on the nation og the R-transducer was generalized by the nations of the Rmn-transducer has m imput and n output tapes; an R(s,t)- trancuder work s over the base - s expansions and builds the base - t expansins (if it output expansions without overflowed symbols, it is called strict); an RA[0,1] - transdicer works over the still more general representations of real numbers. This approach in defining real functions is constructive on the one hand? but it differs from the traditional theories in constructive analysis, on the other hand. The constructive real functions are defined on the constructive real numbers. The latter ones can be roughly considered as algorithms of apporximation of “ordinary) real numbers. Notte that we don‘t restrict ourselves by constructive expansions dealing with transducers. The R-transducers can be classsified according to the type of their memory. They could be finite, push-down, stack, C-machines or transducers of a common from with a countable number of states. L.P.Lisovik has shown that an arbitrary continiuos function or function with the 1st order discontinuty can be defined by the corresponding R- transducer. Thus we have a new criterion of classification of these functions, based on power and structure of the memory of the corresponding transducers. From the practical point of view the transducers are algorithms that calculate the values the functions with an arbitrary precision. Also, the transducers can be considered as means for defining the recursive fractal sets and functions on these sets. In this thesis, the following new results are presented: it has been shown that the class of the functions differentiable on a given interval and defined by a push-down R-transducer is included in the class of the functiions liner on the interval; the necessary and sufficient condition under which the affine mapping, with the rational parameters, of the given subest P of the space Rn can be defined by a finite R-transducer has been considered; the generalization of Mostovsky-Uspensky throrem on translation of constructive real numbers for the finite R(s,t)-transducers has been proved: the strict R(s,t)-transducer defining the ide ntity map exists iff the set of the prime diversors of s is included in the set prime divisors of t; the R12-transducer for Peano curve with the best overlapping coefficient 3 and the function mapping the unit segment onto Serpinsky carpet have been built; it has proved that for an arbitrary hierarchical iterated function system (HIFS) one can build the system of RA m - П [ai,bi] i=1 transducers (which generalize the nation of an RA[0,1]-transducer) that define the same vector of the compact sets from a given HIFS; the RA[0,1]- transducer definig the set that is not closed has been built. All the statements listed above are based on recursive nature of transducers, i.e on iteration or “almost iteration” oof the commands of the given transducer while it is working over the infinite expansion of a real number. Also the