## You are here

HomeVariable automaton

## Primary tabs

# Variable automaton

# 1 Introduction

The question of a variable ‘automaton’, or an automaton with varying internal structure goes back to Norbert Wiener’s suggestion in his book on “The Human Use of Human Beings” (Cybernetics and Society, 1954).

A classical automaton, s-automaton $\mathcal{A}$, or ‘sequential machine’, is defined as a quintuple of three sets: $I$,$O$ and $S$, and two set-theoretical mappings:

$(I,O,S,\delta:I\times S\rightarrow S;\lambda:S\times S\rightarrow 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, $\delta$ is the transition function that maps a s-automaton state $s_{j}$ onto its next state $s_{{j+1}}$ in response to a specific s-automaton input $j\in I$, and $\lambda$ 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}}$ ($(s_{i},s_{{i+1}})\mapsto o_{{i+1}}$, hence the older name of ‘sequential machine’ for the s-automaton).

###### Definition 1.1.

An alternative definition of an automaton is also in use: as a five-tuple $(S,\Sigma,\delta,I,F)$, where $\Sigma$ is a non-empty set of symbols $\alpha$ such that one can define a configuration of the automaton as a couple $(s,\alpha)$ of a state $s\in S$ and a symbol $\alpha\in\Sigma$. Then $\delta$ defines a “next-state relation, or a transition relation” which associates to each configuration $(s,\alpha)$ a subset $\delta(s,\alpha)$ 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 1.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 1.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 1.3.

A *homomorphism of automata* or automaton homomorphism is a morphism of automata quintuples that preserves commutativity of the set-theoretical mapping compositions of both the transition
function $\delta$ and the output function $\lambda$.

With the previous two definitions one has now sufficient data to be able to define the category of automata and automata homomorphisms, $C_{A}$.

# 2 Categories of Automata and Variable Automata Definitions

###### Definition 2.1.

A category of automata $C_{A}$ is defined as a category of quintuples $(I,O,X,\delta:I\times X\rightarrow X;\lambda:X\times S\rightarrow O)$ and automata homomorphisms $h:{\mathcal{A}}_{i}\rightarrow{\mathcal{A}}_{j}$, such that these homomorphisms commute with both the transition and the output functions of any automata ${\mathcal{A}}_{i}$ and ${\mathcal{A}}_{j}$.

A formal definition of an ‘automaton with a varying internal structure’ is here proposed, and then extended by means of categorical concepts in the context of supercategories $\mathbb{S}_{2}$ of automata state spaces $S_{X}$ and automata state space homomorphisms $h_{{XY}}:S_{X}\to S_{Y}$.

As a relatively simple example consider the case of the category of sequential, or Turing machines, $T_{a}$, which is a subcategory of the category of automata $C_{A}$.

###### Definition 2.2.

A ‘variable Turing machine’ is a supercategory $\mathbb{S}^{T}$ of Turing machine topological semigroup (or monoid) categories $S_{{TX}}$ and topological semigroup (monoid) functors $F_{{T_{{XY}}}}:S_{{TX}}\to S_{{TY}}$ between pairs of such semigroup (or monoid) categories.

###### Definition 2.3.

In the general case of universal Turing machines ($UTS$) one simply replaces ‘Turing machine’ with $UTS$ in the previous definition to obtain a formal representation of variable universal Turing machines, $V_{{UTS}}$.

# 2.1 Remarks:

1. Automaton homomorphisms can be considered also as transformations of automata, or as semigroup homomorphisms, when the state space, $X$, of the automaton is defined as a semigroup $S_{X}$.

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, and especially $V_{{UTM}}$s, are not included, but rigid Universal Turing machines are included.5. Such variable automata as $V_{{UTM}}$s may be practically constructed for both industrial, agricultural and Biotechnology/medical applications, and perhaps also as ‘nanobots’, by employing as part of their logical operation design MV-logics, such as the $LM_{N}$-algebraic logic, with $N$ being finite.

6. Other definitions of automata, sequential machines, semigroup automata or cellular automata lead to subcategories of the category of automata defined above.

7. On the other hand, the category of quantum automata is not a subcategory of the automata category defined here.

.

More to come…

# 3 References Cited

Wiener, Norbert. 1988. “The Human Use of Human Beings: Cybernetics and Society”. Da Capo Press, 1954 (first edition).

## Mathematics Subject Classification

18-00*no label found*00-02

*no label found*00-01

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections