# PlanetPhysics/Category of Automata

A *classical automaton* , (or simply *automaton* , or
*sequential machine* , is defined as a quintuple of sets, and , and set-theoretical mappings,

with being called the *transition function* and being called the *output function*.

Acategorical automatonordiscrete and finite/countable, categorical dynamic systemis defined by a commutative square diagram containing all of the above components and assuming that is either a countable or finite set of discrete states:

**Failed to parse (unknown function "\begin{xy}"): {\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ {I \times S }\ar[r]^{\delta}\ar[d]_{t}&{S}\ar[d]^{o}\\ {S \times S}\ar[r]_{\lambda}&{O} } }\end{xy}}**

With the above definition one can now define morphisms between automata and their composition. If the automata are defined by square diagrams such as the one shown above, and diagrams are defined by their associated functors, then automata homomorphisms are in fact defined as natural transformations between diagram functors. One also has a consistent, simpler definition as follows.

Ahomomorphism of automatais 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 now we have sufficient data to define the category of automata and automaton homomorphisms.

The *category of automata* is a category of automata quintuples
and automata homomorphisms **Failed to parse (unknown function "\A"): {\displaystyle h:{\A}_i \rightarrow {\A}_j}**
,
such that these homomorphisms commute with both the transition and the output functions of any automata **Failed to parse (unknown function "\A"): {\displaystyle {\A}_i}**
and **Failed to parse (unknown function "\A"): {\displaystyle {\A}_j}**
.

**Remarks:**

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

An alternative definition of an automaton is also in use:

as a five-tuple , where is a non-empty set of symbols
such that one can define a *configuration* of the automaton as a couple
of a state and a symbol . Then
defines a "next-state relation, or a transition relation" which associates to each configuration
a subset 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.

A special case of automaton is when all its transitions are *reversible* ; then its state space is a groupoid. The *category of reversible automata* is then a 2-category, and also a subcategory of the 2-category of groupoids, or the groupoid category.

### Remarks:[edit | edit source]

Other definitions of automata, sequential machines, semigroup automata or cellular automata lead to subcategories of the category of automata defined above. On the other hand, the category of quantum automata is not a subcategory of the automata category defined here.