scientific article; zbMATH DE number 3848615

From MaRDI portal
Publication:3318115





The paper contains a mathematical model of computational devices, where the control part and the (processing and) memory are considered independently, by means of the theory of environments and respectively the theory of automata. An environment U is defined as being a partial automaton of Moore type where the input vocabulary is a finite set of actions, the output vocabulary is a finite set of local informations, and the set of states is an enumerable set of points. A recognizing automaton \({\mathcal U}\) is an initial partial finite Mealy automaton equipped with a set of teminal states. A pair (\({\mathcal U},U)\), where the input vocabulary of \({\mathcal U}\) is identical with the set of local informations of U and the output vocabulary of \({\mathcal U}\) is identical with the set of actions of U, is stated to be a recognizing machine. The R-environments (R- recognizing automata, R-recognizing machines) are defined by means of R- automata. The interaction between \({\mathcal U}\) and U is considered as a path in U on which \({\mathcal U}\) is moving. A partial function f is U- computable if \({\mathcal U}\) starting in a point P of U is reaching a terminal state. The properties of environments, recognizing automata and recognizing machines are studied by means of the theory of categories. The paper contains many examples of recognizing machines: Turing machines, counter machines, random access machines, push-down automata.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3318115)