Real functions defined by transducers (Q1286281): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Operations on R-numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Axiomatic theory of partial continuous functions and the Peano curve / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite transformers for construction of fractal curves / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: One-to-one mappings defined by finite transformers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5603921 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5590810 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5639489 / rank | |||
Normal rank |
Latest revision as of 19:56, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Real functions defined by transducers |
scientific article |
Statements
Real functions defined by transducers (English)
0 references
31 August 1999
0 references
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.
0 references
differentiability
0 references
linearity
0 references
pushdown transducers
0 references
computable real functions
0 references
\(R\)-transducers
0 references
binary representations of real numbers
0 references
Peano curve with overlap coefficient 3
0 references