Automata Theory
Automata Theory
In the last article where I discussed universal Darwinism I discussed the concept of cellular automata and abstract computation. In this article I will be discussing automata theory which is part of the study of abstract machines. An abstract machine is also called an abstract computer.
Abstract machines are used usually in academia for theoretical computations and thought experiments. Cellular automata for example is based upon very simple rules which all participants follow but which produce emergent behavior which resemble what someone might expect from evolution. Cellular automata can be used to investigate philosophical problems such as questions around consciousness,
John Conway came up with the Game of Life which was a simulation of how a basic set of rules might produce something emergent such as a mind. This video gives a good example:
From very basic rules there emerges deterministic behaviors from the initial set of rules. The initial set of rules act as a seed very similar to how DNA might act. It's these rules which instruct the evolution of the participants in the simulation. These shapes that you see in the video are information patterns which act as artificial life. Cellular automata is a very good example to use when thinking about the question of what is abstract computation.
Tree Automation and Finite State Automata
Tree automation and finite state automata are more practical examples of abstract computation called state machines. A key concept to understand state machines is the concept of the state transition.
In a finite state machine there could be different possible states. So for example if you have one state which is "door open" and another state which is "door close" then you would think of the transition as the path between the opposing states. Blockchain technology, the Raft algorithm, and other distributed computing methods will rely on state transition. Bitcoin could be thought of as a finite state machine which relies on state transitions to map the ownership status. The Ethereum yellow paper defines Ethereum as a transaction-based state machine which is the most accurate definition for what Ethereum is in the abstract sense of the word. World computer, cryptocurrency, are more marketing terms but are easier to understand than transaction-based state machine for most people.
A tree automation is a particular kind of state machine which deals with tree structures. A tree structure is a very common data structure and there are many different types of tree structures such as binary trees or radix trees. Tree structures are hierarchical structures which have roots, and leaves or children. Tree automation comes in the form of bottom up or top down, and they may be deterministic or non-deterministic. DTFA (deterministic finite tree automata) or NFTA (non-deterministic finite tree automata) are distinct in that the deterministic finite tree automata works as such that the output state is determined by the input while the non-deterministic version has output which isn't determined by the input.
An example of tree language:
Language Security
An unrestricted protocol grammar is thus a security risk, since
malicious input could cause its parser to fail to halt — a syntactic
denial of service — or perform arbitrary computation.
In a future article I will discuss language security and how it relates to Chomsky's hierarchy.