Real functions defined by transducers
type: Item
instance of: scholarly article
title: Real functions defined by transducers
zbMATH Open document ID: 0919.03047
DOI: 10.1007/BF02911264
author: L. P. Lisovik
author: O. Yu. Shkaravskaya
published in: Cybernetics and Systems Analysis
publication date: 1999-08-31T00:00:00Z
review text: One of the approaches to the specification of computable real functions involves \(R\)-transducers. These are automata with infinite input and output tapes that sequentially process binary representations of real numbers. The more general model of an \(R^n_m\)-transducer [see, e.g., the first author, Kibern. Sist. Anal. 1993, No. 3, 58-68 (1993; Zbl 0824.03033)] is equipped with \(m\) input and \(n\) output tapes. These machines are used to specify functions of the form \(\widetilde f_A: R^m\to R^n\). In a series of papers we investigated the capacity of finite transducers to define real functions. The present article continues these studies. In the paper cited above we constructed a finite \(R^2_1\)-transducer that defines a Peano curve with overlap coefficient 4. This result can be strengthened: there exists a finite \(R^2_1\)-transducer that defines a Peano curve with overlap coefficient 3 (Theorem 1). A Peano curve with overlap coefficient 2 does not exist [see \textit{N. N. Luzin}, Theory of functions of a real variable (Russian) (1948; Zbl 0032.33901)]. In Kibernetika 1990, No. 2, 1-7, 25 (1990; Zbl 0752.03030), the first author constructed a finite \(R\)-transducer that defines a continuous nowhere differentiable function. Later it was shown [the authors, Dopov. Nats. Akad. Nauk Ukr. 1995, No. 9, 57-59 (1995)] that if a real function \(f(x)\) is everywhere differentiable and is defined by a finite \(R\)-transducer, then it is linear. Here we prove that if the function \(f(x)\) is everywhere differentiable and is defined by a pushdown \(R\)-transducer, then it is linear. We also prove an even more general result: If the function \(f(x)\) is everywhere differentiable and is defined by a nondeterministic pushdown \(R\)-transducer, then it is linear. There is an example of a function which is defined by a pushdown \(R\)-transducer but is not defined by a finite \(R\)-transducer.
Mathematics Subject Classification ID: 03F60
Mathematics Subject Classification ID: 26E40
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 03D10
zbMATH DE Number: 1283613
zbMATH Keywords: differentiability
zbMATH Keywords: linearity
zbMATH Keywords: pushdown transducers
zbMATH Keywords: computable real functions
zbMATH Keywords: \(R\)-transducers
zbMATH Keywords: binary representations of real numbers
zbMATH Keywords: Peano curve with overlap coefficient 3
MaRDI profile type: Publication
cites work: Operations on R-numbers
cites work: Axiomatic theory of partial continuous functions and the Peano curve
cites work: Finite transformers for construction of fractal curves
cites work: One-to-one mappings defined by finite transformers
cites work: Q5603921
cites work: Q5590810
cites work: Q5639489
description: scientific article; zbMATH DE number 1283613