Real functions defined by transducers (Q1286281)

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.