automaton | Physics Library

Definition 0.1. A (classical) automaton, s-automaton 𝒜, or sequential machine, is defined as a quintuple of sets, I,O and S, and set-theoretical mappings,

(I,O, S, δ : I × S → S;λ : S × S → O),

where I is the set of s-automaton inputs, S is the set of states (or the state space of the s-automaton), O is the set of s-automaton outputs, δ is the transition function that maps an s-automaton state s_i onto its next state s_i+1 in response to a specific s-automaton input i ∈ I, and λ is the output function that maps couples of consecutive (or sequential) s-automaton states (s_i,s_i+1) onto s-automaton outputs o_i+1:

(si,si+1) ↦→ oi+1

(hence the older name of sequential machine for an s-automaton).

Definition 0.2. A categorical automaton can also be defined by a commutative square diagram containing all of the above components.

With the above automaton definition(s) one can now also define morphisms between automata and their composition.

Definition 0.3. A homomorphism of automata or automata homomorphism is a morphism of automata quintuples that preserves commutativity of the set-theoretical mapping compositions of both the transition function δ and the output function λ.

With the above two definitions one now has sufficient data to define the category of automata and automata homomorphisms.

Definition 0.4. A category of automata is defined as a category of quintuples (I,O,X,δ : I × X → X; λ : X × S → O) and automata homomorphisms h : 𝒜_i → 𝒜_j, such that these homomorphisms commute with both the transition and the output functions of any automata 𝒜_i and 𝒜_j.

Remarks:

1.: Automata homomorphisms can be considered also as automata transformations or as semigroup homomorphisms, when the state space, X, of the automaton is defined as a semigroup S.
2.: Abstract automata have numerous realizations in the real world as : machines, robots, devices, computers, supercomputers, always considered as discrete state space sequential machines.
3.: Fuzzy or analog devices are not included as standard automata.
4.: Similarly, variable (transition function) automata are not included, but Universal Turing machines are.

Definition 0.5. An alternative definition of an automaton is also in use: as a five-tuple (S, Σ,δ,I,F), where Σ is a non-empty set of symbols α such that one can define a configuration of the automaton as a couple (s,α) of a state s ∈ S and a symbol α ∈ Σ. Then δ defines a “next-state relation, or a transition relation” which associates to each configuration (s,α) a subset δ(s,α) of S- the state space of the automaton. With this formal automaton definition, the category of abstract automata can be defined by specifying automata homomorphisms in terms of the morphisms between five-tuples representing such abstract automata.

Example 0.1. A special case of automaton is that of a stable automaton when all its state transitions are reversible; then its state space can be seen to possess a groupoid (algebraic) structure. The category of reversible automata is then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.

Definition 0.6. An alternative definition of an automaton is also in use: as a five-tuple (S, Σ,δ,I,F), where Σ is a non-empty set of symbols α such that one can define a configuration of the automaton as a couple (s,α) of a state s ∈ S and a symbol α ∈ Σ. Then δ defines a “next-state relation, or a transition relation” which associates to each configuration (s,α) a subset δ(s,α) of S- the state space of the automaton. With this formal automaton definition, the category of abstract automata can be defined by specifying automata homomorphisms in terms of the morphisms between five-tuples representing such abstract automata.

Example 0.2.

A special case of automaton is that of a stable automaton when all its state transitions are reversible; then its state space can be seen to possess a groupoid (algebraic) structure. The category of reversible automata is then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.

"automaton" is owned by bci1.
(view preamble)