Attila Egri-Nagy 2018 14 Pages
Computational implementations are special relations between what is computed and what computes it.
A chain of emulation is ultimately grounded in an algebraic object, a full transformation semigroup.
Mathematically, emulation is defined by structure preserving maps (morphisms) between semigroups.
In contrast, interpretations are general functions with no morphic properties. They can be used to derive semantic content from computations.
Hierarchical structure imposed on a computational structure plays a similar semantic role.
Beyond bringing precision into the investigation, the algebraic approach also sheds light on the interplay between time and computation.
It is argued that for doing a philosophical investigation of computation, semigroup theory provides the right framework.
Roughly speaking, computation is a dynamical process governed by some rules.
When we limit the tape or the number of calculation steps to a finite number, the halting problem ceases to be undecidable.
We restrict the Turing Machine to a finite capacity of memory and such a restricted Turing machine is said to be a finite state automaton.
Thought: Why isn’t it mapped to PDA or a 2-stack machine?
xy = z
We can say that x is combined with y results in z.
One interpretation is that two sequential events x and y happens resulting in the event z.
Alternatively, x can be an input, y a function and xy denotes a function application usually denoted as y(x)
Or, the same idea with different terminology, x is a state and y is a state-transition operator. This explains how to compute.
Semigroup: a set with an associative binary operation and the composition often called multiplication.
Principle 1: State event Abstraction
We can identify an event with its resulting state: state x is where we end up when event x happens, relative to a ground state. The ground state, in turn, corresponds to a neutral event that does not change any state.
Numbers measure size, groups measure symmetry.
M. Armstrong, Groups and Symmetry (1988)
The general idea of measuring is that we assign a mathematical object to the thing to be measured. In the everyday sense, the assigned object is a number, but for measuring more complicated properties, we need more structured objects. In this sense, we say that semigroups measure computation. Turing completeness is just a binary measure, hence the need for a more fine-grained scale. Thus, we can ask questions like “What is the smallest semigroup that can represent a particular computation?”
The idea of accretion has a clear algebraic description: the set of generators. These are elements of a group whose combinations can generate the whole table.
An extreme difference between logical time and actual time is that computation can be suspended
If there were infinite time available for computation, or equivalently, infinitely fast computers, we would not need to do any programming at all, brute-force would suffice (time travel even changes computability). A possible shortcut to the future would render the P vs. NP problem meaningless with enormous consequences.
Memory space can often be exchanged for time and the limit of this process is the lookup table, the precomputed result. Taking the abstraction process to its extreme, we can replace the 2D composition table with a 1D look up table with keys as pairs (x,y) and values xy.
Computation, completely stripped off any locality the process may have, is just an association of keys to values.
We can talk about static computational structures, composition tables, and we can also talk about computational processes, sequences of events tracing a path in the composition table.
If computation is information processing, then information is frozen computation.
For a Rubik’s Cube, one can specify a particular state either by describing the positions and orientations of the cubelets or by giving a sequence of moves from the initial ordered configuration. This is another example of the state-event abstraction (Principle 1).
“A physical system implements a given computation when the causal structure of the physical system mirrors the formal structure of the computation.”
Homomorphism is a knowledge extension tool: we can apply knowledge about one system to another. It is a way to predict outcomes of events in one dynamical system based on what we known about what happens in another one, given that a homomorphic relationship has been established. This is also a general trick for problem solving, widely used in mathematics. When obtaining a solution is not feasible in one problem domain, we can use easier operations by transferring the problem to another domain — assuming that we can move between the domains with structure preserving maps.
What does it mean to be in a homomorphic relationship for computational structures? Using the composition table definition, we can now define their structure preserving maps. If in a systems S event x combined with event y yields the event z = xy, then by a homomorphism φ : S → T, then in another system T the outcome of φ(x) combined with φ(y) is bound to be φ(z) = φ(xy), so the following equation holds
φ(xy) = φ(x)φ(y)
On the left hand side, composition happens in S, while on the right hand side composition is done in T.
A distinguished class of homomorphisms is isomorphisms, where the correspondence is one-to-one. In other words, isomorphisms are strictly structure preserving, while homomorphisms can be structure forgetting down to the extreme of mapping everything to a single state and to the identity operation. The technical details can be complicated due to clustering states (surjective homomorphism) and by the need of turning around homomorphism we also consider homomorphic relations.
By turning around implementations we can define computational models. We can say that a physical system implements an abstract computer, or we can say that the abstract computer is a computational model of the physical system.
Definition 1 (vague). Computers are physical systems that are homomorphic images of computational structures (semigroups).
The first definition begs the question, how can a physical system be an image of a homomorphism, i.e., a semigroup itself? How can we cross the boundary between the mathematical realm and the external reality? First, there is an easy but hypothetical answer. According to the Mathematical Universe Hypothesis, all physical systems are mathematical structures, so we never actually leave the mathematical realm.
Secondly, the implementation relation can be turned around. Implementation and modeling are the 2 directions of the same isomorphic relation. If T implements S, then S is a computational model of T. Again, we stay in the mathematical realm, we just need to study mappings between semigroups.
Definition 2. Computers are physical systems whose computational models are homomorphic images of semigroups.
This definition of computers is orthogonal to the problem of whether mathematics is an approximation or a perfect description of a physical reality, and the definition does not depend on how physical systems are characterized.
Biological systems are also good candidates for hosting computation, since they’re already doing some information processing. However, it is radically different from digital computation. The computation in digital computers is like toppling dominoes, a single sequence of chain reactions of bit-flips. Biological computation is done in a massively parallel way (e.g., all over in a cell), more in a statistical mode.
Computational implementation is a homomorphism, while an arbitrary function with no homomorphic properties is an interpretation. We can take a computational structure and assign freely some meaning to its elements, which we call the semantic content. Interpretations look more powerful since they can bypass limitations imposed by the morphic nature of implementations. However, since they are not necessarily structure preserving, the knowledge transfer is just one way. Changes in the underlying system may not be meaningful in the target system. If we ask a new question, then we have to devise a new encoding for the possible solutions.
For instance, reversible system can carry out irreversible computation by a carefully chose output encoding. A morphism can only produce irreversible systems out of irreversible(?) systems. This in turn demonstrates that today’s computers are not based on the reversible laws of physics. From the logic gates up, we have proper morphic relations, but the gates themselves are not homomorphic images of the underlying physics. When destroying information, computers dissipate heat. Whether we can implement group computation with reversible transformations and hook on a non-homomorphic function to extract semantic content is an open engineering problem. In essence, the problem of reversible computation implementing programs with memory erasure is similar to trying to explain the arrow of time arising from the symmetrical laws of physics.
Throwing computing into reverse (2017) — M. P. Frank
Composition and lookup tables are the “ultimate reality” of computation, but they are not adequate descriptions of practical computing. The low-level process in a digital computer, the systematic bit flips in a vast array of memory, is not very meaningful. The usefulness of a computation is expressed at several hierarchical layers above (e.g., computer architecture, operating system, and end user applications).
A semigroup is seldom just a flat structure, its elements may have different roles. For example, if xy = z but yx = y (assuming x ≠ y ≠ z), then we say that x has no effect on y (leaves it fixed) while y turns x into z. There is an asymmetric relationship between x and y: y can influence x but not the other way around. This unidirectional influence gives rise to hierarchical structrues. It is actually better than that. According to the Krohn-Rhodes theory, every automaton can be emulated by a hierarchical combination of simpler automata. This is true even for inherently non-hierarchical automata built with feedback loops between its components. It is a surprising result of algebraic automata theory that recurrent networks can be rolled out to one-way hierarchies. These hierarchies can be thought as easy-to-use cognitive tools for understanding complex systems. They also give a framework for quantifying biological complexity.
The simpler components of a hierarchical decomposition are roughly of two kinds. Groups correspond to reversible combinatorial computation. Groups are also associated with isomorphisms (due to the existence of unique inverses), so their computation can also be viewed as pure data conversion. Semigroups, which fail to be groups, contain some irreversible computation, i.e., destructive memory storage.
The question of whether cognition is computational or not, might be the same as the question of whether mathematics is a perfect description of physical reality or is just an approximation of it. If it is just an approximation, then there is a possibility that cognition resides in physical properties that are left out.
A recurring question in philosophical conversations is the possibility of the same physical system realizing two different minds simultaneously. Let’s say n is the threshold for being a mind. You need at least n states for a computational structure to do so. Then suppose there is more than one way to produce a mind with n states, so the corresponding full transformation group T_n can have subsemigroups corresponding to several mind. We then need a physical system to implement T_n. Now, it is a possibility to have different embeddings into the same system, so the algebra might allow the possibility of two minds coexisting in the same physical system. However, it also implies that most subsystems will be shared or we need a bigger host with at least 2n states. If everything is shared, the embeddings can still be different, but then a symmetry operation could take one mind into the other. This is how far mathematics can go in answering the question. For scientific investigation, these questions are still out of scope. Simpler questions about the computation form a research program. For instance, What is the minimum number of states to implement a self-referential system? and, more generally, What are the minimal implementations of certain functionalities? and How many computational solutions are there for the same problem? These are engineering problems, but solutions for these may shed light on the more difficult questions about the possibilities and constraints of embedding cognition and consciousness into computers.
In the opinion of the author, philosophy should be ahead of mathematics, as it deals with more difficult questions, and it should not be bogged down by the shortcomings of terminology. In philosophy, we want to deal with the inherent complexity of the problem, not the incidental complexity caused by the chosen tool. The algebraic viewpoint provides a solid base for further philosophical investigations of the computational phenomena.
Attila Egri-Nagy 2016
12 Pages
What is computable with limited resources? How can we verify the correctness of computations? How to measure computational power with precision?
Despite the immense scientific and engineering progress in computing, we still have only partial answers to these questions. In order to make these problems more precise, we describe an abstract algebraic definition of classical computation, generalizing traditional models to semigroups.
The exponential growth of the computing power of hardware (colloquially known as Moore’s Law) seems to be ended by reaching its physical and economical limits. In order to keep up technological development, producing more mathematical knowledge about digital computation is crucial for improving the efficiency of software.
Our computers are physical devices ad the theory of computation is abstracted from physical processes. Mathematical models clearly define the notion of computation, but mapping the abstract computation back to teh physical realm is often considered problematic. It is argued that structure-preserving maps between computations work from one mathematical model to another just as well as from the abstract to the concrete physical implementation, easily crossing any ontological borderline one might assume between the two.
Since abstract algebra provides the required tools, suggestion is made for further abstractions to the models of computations to reach the algebraic level safe for discussing implementations. It is also suitable for capturing the hierarchical structure of computers. Finiteness and the abstract algebraic approach paint a picture where universal computation becomes relative and the ‘mathematical versus physical’ distinction less important.
First it is attempted to define computations and implementations purely as abstract functions, then the need for combining functions leads us to definition of computational structures.
Starting from the human perspective, computation is a tool. We want a solution for some problem: the input is the question, the output is the answer. Formally, the input-output pairs are represented as a function f : X → Y, and computation is function evaluation f(x) = y, x ∈ X, y ∈ Y. As an implementation of f, we need a dynamical system whose behaviour can be modelled by another function g, which is essentially the same as f.
Computation can be described by a mapping f : { 0, 1 }^ m → { 0, 1 }^n , m,n ∈ ℕ
According to the fundamental theorem of reversible computing, any finite function can be computed by an invertible function. This apparently contradicts the idea of implementation, that important properties of functions have to be preserved.
Embedding XOR: [00] ↦ [0]0 [01] ↦ [1]1 [10] ↦ [1]0 [11] ↦ [0]1 Embedding FAN-OUT: [0]0 ↦ [00] 0[1] ↦ [11] 10 ↦ 10 11 ↦ 01
into the same bijective function. By putting information into the abstract elements, any function can ‘piggyback’ even on the identity function.
These ‘tricks’ work by composing the actual computations with special input and output functions, that might have different properties. In reversible computing the readout operation may not be a reversible function.
Focussing on the process view, what is the most basic unit of computation? A state transition: an event changes the current state of a system. A state is defined by a configuration of a system’s components, or some other distinctive properties the system may have.
Let’s say the current state is x, then event s happens changing the state to y. We might write y = s(x) emphasizing that s is a function, but it is better to write xs = y meaning that s happens in state x yielding state y. Why? Because combining events as they happen one after the other, e.g. xst = z, is easier to read following our left to right convention.
State-event abstraction: We can identify an event with its resulting state: state x is where we end up when event x happens.
According to the action interpretation, xs = y can be understood as event s changes the current state x to the next state y. But xs = y can also be read as event x combined with event s yields the composite event y, the event algebra interpretation. We can combine abstract events into longer sequences. These can also be considered as a sequence of instructions, i.e. an algorithm. These sequences of events should have the property of associativity
(xy)z = x(yz) for all abstract events x, y, z
since a given sequence xyz should be a well-defined algorithm.
We can put all event combinations into a table. These are the rules describing how to combine any two events.
Computational Structure: A finite set X and a rule for combining elements of X that assigns a value x’ for each two-element sequence, written as xy = x’, is a computational structure if (xy)z = x(yz) for all x, y, z ∈ X.
In mathematics, a set closed under an associative binary operation is an abstract algebraic structure called semigroup.
Computation is a process in time — an obvious assumption, since most of engineering and complexity studies are about doing computation in shorter time. Combining two events yield a third one (which can be the same), and we can continue with combining them to have an ordered sequence of events. This ordering may be referred as time. However, at the abstraction level of the state transition table, time is not essential. The table implicitly describes all possible sequences of events, it defines the rules how to combine any two events, but it is a timeless entity. This is similar to some controversial ideas in theoretical physics such as the idea of “The End of Time” by D. M. Barbour of Shape Dynamics fame.
How are the function and the process view of computation related? They are actually the same. Given a computable function, we ca construct a computational structure capable of computing the function. An algorithm (a sequence of state transition events) takes an initial state (encoded input) into a final state (encoded output). The simplest way to achieve this is by a lookup table.
Lookup table semigroup: Let f : X → Y be a function, where X ∩ Y = ∅. Then the semigroup S = X ∩ Y ∩ {l} consists of resets X ∪ Y and the lookup operation l defined by xl = y if f(x) = y for all x ∈ X and ul = u for all u ∈ S \ X.
Is it associative? Let v ∈ X ∪ Y be an arbitrary reset element, and s, t ∈ S any element. Since the rightmost event is a reset, we have (st)v = v and s(tv) = sv = v. For (sv)l = vl = s(vl) since vl is also a reset. For (vl)l = vl, since l does not change anything in S \ X and v(ll) = vl since l is an idempotent (ll = l). Separating the domain and the codomain of f is crucial, for function X → X we can simply have a separate copy of elements of X. When trying to make it more economical associativity may not be easy to achieve.
Turning a computational structure into a function is also easy. Pick any algorithm (a composite event), and that is also a function from states to states.
Information storage and retrieval are forms of computation. By the same token computation can be considered as a general form of information storage and retrieval, where looking up the required piece of data may need many steps. We can say that if computation is information processing, then information is frozen computation.
From finite state automata, we abstract away the initial and accepting states. Those special states are needed only for the important application of recognizing languages. Input symbols of a finite state automaton are fully defined transformations (total functions) of its state set.
A transformation is a function f : X → X from a set to itself, and a transformation semigroup (X, S) of degree n is a collection S of transformations of an n-element set closed under function composition.
If we focus on the possible state transitions of a finite state automaton only, we get a transformation semigroup with a generator set corresponding to the input symbols. These semigroups are very special representations of abstract semigroups, where state transition is realized by composing functions.
If we focus on the possible state transitions of a finite state automaton only, we get a transformation semigroup with a generator set corresponding to the input symbols. These semigroups are very special representations of abstract semigroups, where state transition is realized by composing functions.
In general, if we take the models of computation that describe the detailed dynamics of computation, and remove all the model specific decorations, we get a semigroup.
Intuitively, a computer is a physical system whose dynamics at some level can be described as a computational structure. For any equation xy = z in the computational structure, we should be able to induce in the physical system an event corresponding to x and another one corresponding to y such that their overall effect corresponds to z. Algebraically, this special correspondence is a structure-preserving map, a homomorphism. If we want exact realizations, not just approximations, then we need stricter one-to-one mappings, isomorphisms. However, for computational structures we need to use relations instead of functions.
Isomorphic relations of computational structures: Let S and T be computational structures (semigroups). A relation ɸ : S → T is an isomorphic relation if it is:
- homomorphic: ɸ(s)ɸ(t) ⊆ ɸ(st)
- fully defined: ɸ(s) ≠ ∅ for all s ∈ Structures
- lossless: ɸ(s) ∩ ɸ(t) ≠ ∅ ⇒ s = t
for all s, t ∈ S. We also say that T emulates, or implements S.
Homomorphic is the key property, it ensures that similar computation is done in T by matching individual state transitions. Here ɸ(s) and ɸ(t) are subsets of T (not just single elements), and ɸ(s)ɸ(t) denotes all possible state transitions induced by these subsets (element-wise product of two sets). Fully defined meas that we assign some state(s) of T for all elements of S, so we account for everything that can happen in S. In general, homomorphic maps are structure-forgetting, since we can map several states to a single one. Being lossless excludes loosing information about state transitions. In semigroup theory, isomorphic relations are called divisions, a special type of relational morphisms.
What happens if we turn an implementation around? It becomes a computational model.
Modelling of computational structures. Let S and T be computational structures (semigroups). A function µ : T → S is a modelling if it is:
- homomorphism µ(u)µ(v) = µ(uv) for all u, v ∈ T,
- onto: for all s ∈ S there exists a u ∈ T such that µ(u) = s.
We also say that S is a computational model of T. In algebra, functions of this kind are called surjective homomorphisms.
A modelling is a function, so it is fully defined. A modelling µ turned around µ^-1 is an implementation, and an implementation ɸ turned around is a modelling ɸ^-1. This is an asymmetric relation, naturally we assume that a model of any system is smaller in some sense than the system itself. Also, to implement a computational structure completely we need another structure at least as big.
According to the mathematical universal hypothesis, we have nothing more to do, since we covered mappings from one mathematical structure to another one. In practice, we do seem to have a distinction between mathematical models of computations and actual computers, since abstract models by definition are abstracted away from reality, they do not have any inherent dynamical force to carry out state transitions. Even pen and paper calculations require a driving force, the human hand and the pattern matching capabilities of the brain. But we can apply a simple strategy: we treat a physical system as a mathematical structure, regardless its ontological status. Building a computer then becomes the task of constructing an isomorphic relation.
Computer: An implementation of a computational structure by a physical system is a computer.
Anything that is capable of state transition can be used for some computation. The question is how useful that computation is? We can always map the target system’s mathematical model onto itself. In this sense the cosmos can be considered as a giant computer computing itself. However, this statement is a bit hollow since we don to have a complete mathematical model of the universe. Every physical system computes, at least its future states, but not everything does useful calculation. Much like entropy is heat not available for useful work. The same way as steam and combustion engines exploit physical processes to process materials and move things around, computers exploit physical process to transfer and transform information.
Huge state transition tables are not particularly useful to look at; they are like quark-level descriptions for trying to understand living organisms. Identifying substructures and their interactions is needed. Hierarchical levels of organizations provide an important way to understand computers. Information flow is limited to one-way only along a partial order, thus enabling functional abstraction. According to Krohn-Rhodes theory, any computational structure can be built by using destructive memory storage and the reversible computational structures in a hierarchical manner. The way the components are put together is the cascade product which is a substructure of the algebraic wreath product. The distinction between reversible and irreversible is sharp: there is no way to embed state collapsing into a permutation structure. Reversible computing seems to contradict this. The trick there is to put information into states and then selectively read off partial information from the resulting states. This selection of required information can be done by another computational structure. We can have a reversible computational structure on the top, and one at the bottom that implements the readout. We can have many transitions in the reversible part without a readout. Reversible implementations may prove to be decisive in terms of power efficiency of computers, but it does not erase the difference between reversible and irreversible computations.
Important to note that hierarchical decompositions are possible even when the computational structure is not hierarchical itself. on of the research directions is the study of how it is possible to understand loopback systems in a hierarchical manner.
What is the difference between a piece of rock and a silicon chip? They are made of the same material, but they have different computational power. The rock only computes its next state (its temperature, all wiggling of its atoms), so the only computation we can map to it homomorphically is its own mathematical description. While the silicon chip admits other computational structures. General purpose processors are homomorphic images of universal computers.
The main topics where further research needs to be done are:
- exploring the space of possible computations
- measuring finite computational power
- computational correctness
Cataloguing stocktaking are basic human activities for answering the question What do we have exactly? For the classification of computational structures and implementations, we need to explore the space of all computational structures and their implementations, starting from the small examples. Looking at those is the same as asking the questions What can we compute with limited resources? What is computable with n states? This is a complementary approach to computational complexity, where the emphasis is on the growth rate of resource requirements.
Given an abstract or physical computer, what computations can it perform? The algebraic description gives a clear definition of emulation, when one computer can do the job of some other computer. This is a crude form of measuring computational power, in the sense of the ‘at least as much as’ relation. This way computational power can be measured on a partial order (the lattice of all finite semigroups).
The remaining problem is to bring some computation into the common denominator semigroup form. For example, if we have a finite piece of cellular automata grid, what can we calculate with it? If the cellular automata is universal and big enough we might be able to fit in a universal Turing machine that would do the required computation. However, we might be able to run a computation directly on the cellular automata instead of a bulky construct.
Extending the slogan, “Numbers measure size, groups measure symmetry.”, we can say that semigroups measure computation.
Computations can differ by:
- having different intermediate results
- applying different operations
- having different modular structure
Attila Egri-Nagy 2017
18 pages
Computational complexity studies the asymptotic behaviour of algorithms. Complementing that, it is here suggested to focus on small theoretical computing devices, and study of the possibilities of limited finite computations. Instead of asking what resources we need in order to solve bigger instances of a computational problem, we restrict the resources and ask what can we compute within those limitations. The practical benefit of such an approach is that we get to know the lowest number of states required to execute a given algorithm and having the minimal example are useful for low-level optimizations. Another example of such a reversed question is asking what is the total set of all possible solutions for a problem instead of looking for the single right solution. The mathematical formalism turns this into a well-defined combinatorial question, and the payoff could be that we will find solutions we had never thought of.
Since abstract algebra provides the required tools, we suggest further abstractions to the models of computations to reach the algebraic level safe for discussing implementations. It is also suitable for capturing the hierarchical structure of computers. Finiteness and the abstract algebraic approach paint a picture where universal computation becomes relative and the ‘mathematical versus physical’ distinction less important.
A composition table of groups that are semigroups with an identity and a unique inverse for each element is always a Latin square.
Finite State Automata is considered to be a discrete dynamical system.
By a finite state automaton, we mean a triple (X, Σ, δ) where
- X is the finite state set
- Σ is the finite input alphabet
- δ : X × Σ → X is the transition function
How is this a definition of a semigroup? For each state x ∈ X an input symbol σ ∈ Σ gives the resulting state δ(X, σ) = (δ(x_1, σ), δ(x_2, σ), …, δ(x_n, σ)). Therefore, input symbols of a finite state automaton are fully defined transfomaitons (total functions) of its state set.
A transformation is a function f : X → X from a set to itself, and a transformation semigroup (X, S) of degree n is a collection S of transformations of an n-element set closed under function composition.
If we focus on the possible state transitions of a finite state automaton only, we get a transformation semigroup with a generator set corresponding to the input symbol.s These semigroups are very special representations of abstract semigroups, where state transitions is realized by composing functions. It turns out that any semigroup can be represented as a transformation semigroup (Cayley’s Theorem for semigroups).
Transformation semigroup realization of the flip-flop semigroup. The set being transformed is simply X = { 0, 1 } also called the set of states.
s0 = { 0 ↦ 0, 1 ↦ 0 }
s1 = { 0 ↦ 1, 1 ↦ 1 }
r = { 0 ↦ 0, 1 ↦ 1 }
The events can be denoted algebraically by listing the images s0 = [0, 0], s1 = [1, 1], r = [0, 1].
First, we give an algebraic definition of computational implementations, then we justify the choices in the definitions by going through the alternatives.
Emulation, isomorphic relation of computational strucutres. Let S and T be computational structures (semigroups). A relation ɸ : S → T is an isomorphic relation if it is:
- homomorphic: ɸ(s)ɸ(t) ⊆ ɸ(st)
- fully defined: ɸ(s) ≠ ∅ for all s ∈ S
- lossless: ɸ(s) ∩ ɸ(t) ≠ ∅ ⇒ s = t
Homomorphism is a fundamental algebraic concept often described by the equation:
ɸ(s)ɸ(t) = ɸ(st),
where the key idea is hidden in the algebraic generality. We have two semigroups S and T, in which the actions of computations are the composition of elements. In both semigroups these are denoted by juxtaposition of their elements. This obscures the fact that computations in S and in T are different. Writing ∘S for composition in S and ∘_T for composition in T we can make the homomorphism equation more transparent:
ɸ(s) ∘_T ɸ(t) = ɸ(s ∘_S t)
This shows the underlying idea clearly: it does not matter whether we convert the inputs in S to the corresponding inputs in T and do the computation, in T (left hand side), or do the computation in S then send the outputs in S to its counterpart in T (right hand side), we will get the same result. In the above definition, ɸ(s) and ɸ(t) are subsets of T (not just single elements), and ɸ(s)ɸ(t) denotes all possible state transitions induced by these subsets (element-wise product of two sets).
S : s ----------------------------> st
| t |
| | |
| ɸ | ɸ | ɸ
| | |
| v |
v ɸ(t) v
T : ɸ(s) ------------->ɸ(s)ɸ(t) = ɸ(st)
Fully defined means that we assign some state(s) of T for all elements of S, so we account for everything that can happen in S. This is just a technical, not a conceptual requirement, since we can always restricte a morphism to a substructure of S.
Being lossless excludes loosing information about state transitions. In general, homomorphic maps are structure-forgetting, since we can map several states to a single one. In case of s_1 ≠ s_2 and both s_1 and s_2 are sent to t in the target, the ability of distinguishing them is lost. For lossless correspondence we need one-to-one maps. For relations this requires the image sets to be disjoint. Varying these conditions we can have a classification of structure preserving correspondences between semigroups.
| lossy (many-to-1) | lossless (1-to-1) | |
|---|---|---|
| relation (set-valued) | relational morphism | division |
| function (point-valued) | homomorphisms | isomorphism |
In semigroup theory, isomorphic relations are called divisions, a special type of relational morphism. This is a bit unfortunate terminology from computer science perspective, emulation instead of division, and morphic relation instead of relational morphism perhaps would be slightly better. In semigroup theory, relational morphisms are used for the purpose of simplifying proofs, not for any deep reasons. However, for describing computational implementations relations are necessary, since we need to be able to cluster states (e.g. micro versus macro states in a real physical settings).
Modelling of computational structures: Let S and T be computational structures (semigroups). A function µ : T → S is a modeling if it is:
- homomorphism: µ(u)µ(v) = µ(uv) for all u, v ∈ T
- onto: for all s ∈ S there exists a u ∈ T such that µ(u) = s
We also say that S is a computational model of T. In algebra, functions of this kind are called surjective homomorphisms.
In the case of ℤ_2 → ℤ_4, there are more divisions that isomorphisms. ℤ_2 is a quotient of ℤ_4, so ℤ_4 has a surjective homomorphism to ℤ_2. The division here is exactly that surmorphism turned around. Exactly this reversal of surjective homomorphisms was the original motivation for defining divisions.
Computer: An implementation of a computational structure by a physical system is a computer
Abstract state machines are generalizations of finite state machines. These models can be refined and coarsened forming a hierarchical succession, based on the same abstraction principles as in Krohn-Rhodes theory.
The full transformation semigroup of degree n (denoted by T_n) consists of all n^n transformations of an n-element set. These can be generated by compositions of three transformations: a cycle [1, 2, 3, …, n - 1, 0], a swap [1, 0, 2, 3, …, n - 1], and a collapsing [0, 0, 2, 3, …, n - 1]. Leaving out the state collapsing generator, we generate the symmetric group S_n, which is the universal structure of all permutations of n points.
Some practical problems of finite computation which are the difficult ones, that were not really in the focus of mathematical research:
- What are the possible computational structures and implementations?
- How to measure the amount of computational power?
- How can we trust computers?
The method of enumerating certain types of semigroups by enumerating all subsemigroups of relatively universal semigroup of that type has been applied to a wider class of semigroups, called diagram semigroups. These generalize function composition to other combinatorial structures (partial functions, binary relations, partitions, etc.), while keeping the possibility of representing the semigroup operation as stacking diagrams. These can be considered as ‘unconventional’ mathematical models of computations (e.g. computing with binary relations or partitions instead of functions). The existence of different types of computers leads to the problem of comparing their power.
For an abstract semigroup, finding the minimal number of states n such that it embeds into the full transformation semigroup T_n is the same of finding the minimal number of states such that the given computation can be realized. This state minimization is an important engineering problem. It is not to be mistaken with the finite state automata minimization problem, where the equivalence is defined by recognizing the semi regular language, not by isomorphic relation.
The simplest definition of a computational task is that we want to produce output from some input data. How many different ways are there for completing a particular task? The answer is infinity, unless we prohibit wasteful computations and give a clear definition of being different. Computational complexity distinguishes between classes of algorithms based on their space and time requirements. This is only one aspect of comparing solutions, since there might be different algorithms with very similar performance characteristics (e.g. bubble sort and insertion sort). Therefore we propose to study the set of all solutions more generally.
When are two solutions really different? The differences can be on the level of implementation or of the algorithm specification. Informally we can say that computations can differ by their:
- intermediate results
- applied operations
- modular structure
- or by any combination of these
An algorithmic solution space is a set of computer programs solving a computational problem, i.e. realizing a function described by input-output mappings.
C. Lev Nehaniv 16 pages 1997
We identify certain formal algebraic models affording understanding (including positional number systems, conservation laws in physics, and spatial coordinate systems) that have empowered humans when we have augmented ourselves using them. We survey how, by explicit mathematical constructions, that such algebraic models can be algorithmically derived for all finite-state systems and give examples illustrating this including coordinates for the rigid symmetries of a regular polygon, and recovery of the decimal expansion and coordinates arising from conserved quantities in physics.
Coordinate systems derived by algebra or computation for affordances of the understanding and manipulation of physical and conceptual worlds are thus a ‘natural’ step in the use of ‘tools’ by biological systems as they/we learn to modify selves and identities appropriately and dynamically.
Throughout the history of science, the greatest advances have come about when human beings came to realizations about how to think about their subject “correctly”. The deepest such advances have resulted from the advent of appropriate coordinate systems for a phenomenon to be understood. Some obvious and familiar examples include the decimal or binary expansions of the real numbers, Cartesian coordinate in analytic geometry, Galilean or Newtonian spatial coordinates, the periodic table in chemistry, conservation laws in physics, locally Euclidean coordinates in Riemannian geometry, and more recently, the idea of object-orientation.
Our chief claims in this paper are that:
- such appropriate coordinate systems generally share certain crucial properties that explain their usefulness
- such coordinate systems for understanding and manipulating a given system at least in the case of finite-state systems (such as our present day digital computers) can be generated algorithmically for use by humans or machines.
Such models for understanding may empower a human being to manipulate real, abstract, or synthetic worlds. It is important to note that to exploit or access formal models constructed with the aid of computers, a human being need not understand the algebraic theory behind their construction and should be free from such intellectual and computational encumbrances; however, mastering manipulation and application of a coordinate system e.g. the decimal number system may require some effort.
When we reflect on how we understand a system using any of the historically useful coordinate systems mentioned above, certain properties of the coordinate systems are evident:
- Globality: we have some sort of description of essential characteristics of the system and can describe or predict how it will change with occurrences of events important for that system.
- Hierarchy: Except in the simplest cases, the whole is broken down into component parts, which themselves may consist of other parts, and so on, resulting in an ordering that encodes the dependencies among parts. Information from higher levels of the hierarchy gives good approximate knowledge, while “lower order” details are fleshed at subordinate levels
- Simplicity of Components: The smallest component parts are by themselves easy to understand
- Covering: We have implicitly or explicitly a knowledge of how to map the coordinate representation of the system to the system we are trying to understand.
A non-required property is that of a one-to-one correspondence between possible coordinate states and states of the system. Indeed, there is usually a many-to-one relationship between representations in coordinates and states of the system (as for example, with real numbers and their decimal representations).
Taking these properties as axiomatic for appropriate coordinate systems on understanding, we note that such understanding of a system is something quite different from knowledge (but may be related to such knowledge) of how the original system can be built or efficiently emulated, nor is it the same as knowledge of how the system is really structured. It is the utility afforded by such coordinate systems as tools for understanding which interests humans, but we shall also be concerned with the nature of affordance in cognitive (and physical) environments that are created, affected, or manipulated by these systems, as well as with explicit methods to construct these systems.
Object-oriented design can be regarded as a special case of wreath product decomposition over a partial order, and global semigroup theory then provides a rigorous algebraic foundation.
Algebraic engineering of understanding: Global hierarchical coordinates on computation for manipulation of data, knowledge, and process - C. L. Nehaniv, 1994
We present first a formalization of “system” common in physics and computer science. Then, beginning from the above properties, we present a formalization of “model for understanding” of such a system.
We contend that generally such useful coordinate systems can be considered as formal models for understanding of the domain via an emulation by the (generally larger) coordinate system, giving global hierarchical coordinates in the sense of emulation by a cascade (or wreath product) of small component parts.
The idea that wreath product emulations provide models for understanding appears to be due to John L. Rhodes. In a still unpublished book written in the late 1960s, what we call formal models for understanding here are motivated as theories which provide understanding of an experiment, i.e. a system.
The examples of coordinate systems on the concepts of number, time, physical transformation, and software represent hard-won achievements for humanity, and they share the properties listed above. Could they have been found by some algorithm, rather than brilliant insights?
Our thesis is that the answer is “yes”, at least in part. Given a finite-state model of any system, mathematical constructions based on the Krohn-Rhodes Theorem in algebra show how to construct a coordinate system bearing the markings of a useful model of understanding as described above. Generalizations of this theorem to the infinite case, show that this is even possible without the assumptions of finiteness, although algorithmically the construction may be more complicated. In particular, mathematics guarantees the existence of and yields generally many formal models of understanding of the given system in global hierarchical coordinates. A hierarchy of simple components is found by a simple recursive procedure, and the dependencies between these components are configured in such a way that an input to the system results in a change of state whose effect at each given component, i.e., at the given coordinate position depends only on the input and states above the component in the hierarchy. Each state and input of the original system has one or many representations in the covering coordinate system, and computation of the updated state when working in the covering coordinates proceeds in a hierarchical, feed forward manner. Hence in global hierarchical coordinates the functioning of the system to be understood is easy globally computable, and recovery of the corresponding state in the original system given in a determined way.
Given a finite state system described to a human or to a computer, it is possible then to algebraically engineer an appropriate formal model for understanding that system. For example, an object-oriented software realization of the system could be derived automatically from an unstructured finite-state description of the system to be emulated.
Moreover, relationships and analogies between formal models for understanding have a nice algebraic descriptions which are amenable to automatic manipulation, and the completion of relations to full analogies can be carried out using recently developed “kernel theorems” of algebraic automata theory which capture mathematically the notion of what needs to be added to a relationship between systems to complete it to a full, covering analogy.
We shall see below that for finite-state systems, methods already exist for generating a formal model of understanding for the given system and that one also has definitions for analogy and metaphors as relational mappings (morphisms in an appropriate setting) as well as characterizations of exactly what [extension] is required for an incomplete relation to be transformed into an finished model [emulation].
4 Mathematical Platonism and Cybernetic Contigency: For cyborgs who have considered suicide when ad hoc coordinates were enough
The non dualism of Haraway’s characterization of ourselves as cyborg is naturally disturbing to notions of separate identity, fixed boundaries, a Platonic realm of forms, ‘The Good’. As a profession that as a whole has implicitly adopted Platonic idealism (the belief in a heaven of pure, perfect forms beyond mere physical being) where proving existence and uniqueness takes an a primary role mathematics seems remote from considerations of the fragmentation and re-construction of ourselves. The late great combinatoricist Paul Erdös often spoke of ‘The Book’ in which the ‘Supreme Fascist’ (God) keeps secret the most elegant and beautiful proofs of eternal mathematical truths. only by great effort and inspiration can a mortal hope to find any of its proofs, glimpses of ‘The Book’. It is hardly possible to be a mathematician without taking this metaphysical realm seriously at least implicitly in practice if not consciously, since at least the abstract objects of study are presumed to exist. Yet we will see that this Platonic world can serve as a substrate for constructing (non-unique) models affording understanding and contingent self-extension. And indeed, whether empiricism science and engineering like it or not, mathematical results are neither physical nor subject to Popper’s notion of ‘falsifiability’, viz. the possibility of disproof by experiment. Thus mathematics is a branch of metaphysics providing tools applied by science and engineering, while remaining itself outside their epistemological scope. While mathematical entities may be of dubious or at least unclear ontological status, the structure (whatever this may ‘be’) of these entities (whatever they may ‘be’) informs and constrains science and engineering.
The contingency we see in the cyborg appears also in the mathematically derived hierarchical coordinate systems comprising models for understanding that we shall survey below. Indeed, by extending our minds with coordinate systems such as the decimal expansion, we adopt non unique, possible non ideal, contingent (and thus historical tools and methods of self augmentation or interface with the world which could have been otherwise).
This contingency of design appears elsewhere in science: it is the essential characteristic of what Herbert Simon has called the sciences of the artificial. That is, unlike the physical and chemical structures of the natural world, artificial systems are those that have a given form and behaviour only because they adapt (or are adapted) in reference to goals or purposes, to their environment. They have interfaces to the world that are contingent on possibly teleological circumstances (choice or design). We shall argue that this concept of ‘artificial’ has a natural extension to the biological and cognitive worlds (where design may not be of the conscious sort).
Whether we consider our eyes, our human languages, or our number systems for calculation, the arbitrariness of choices while constrained by physics or chemistry or evolutionary history or the metaphysics of mathematics is not determined by necessity but could usually have been otherwise within historical contingencies and design constraints. The non-uniqueness of coordinate systems for understanding physics is well-known from the examples of Galilean inertial frames and from the locally Euclidean relativistic space-time coordinate systems. Local Euclidean coordinate systems agree where they overlap, describing regions of space which patch together to cover lal of curved space time in a manifold which is globally not the naïve Euclidean space.
In a similar way, the earth is locally like a flat plane, and can be covered by sheets which are just planes topologically, but globally no single plane can cover the earth; consider for example the non-uniqueness of longitudes at the north and south poles. In fact, a globally consistent, one to one planar coordinate system is impossible for a sphere like the surface of the earth! There must be at least two patches, and where they overlap the coordinates are non-unique resulting in an expansion of space in the coordinate world but not of physical space.
We see that we ourselves can be understood as “artificial systems” in the sense of contingent design. Our coordinate systems (that is, our ways of understanding space-time, numbers, language, concepts etc.) as conceptual tools as well as our physical tools (stone knives, hammers, eyeglasses, clothes, prosthetic limbs) have arbitrariness in their conscious or non-conscious design. Moreover, the evolution of multicellular life, the incorporation of bacterial endosymbionts into our ancestral eucaryotic cells, our evolution via duplication and divergence of HOX controlled development in segmented animals, even the correspondence (a code!) between nucleotide triplets (codons) and amino acids in protein biosynthesis could have been other wise. All this seems to have occurred without a ‘master plan’, but rather via ‘just’ the opportunistic (for self-reproduction) merging of identities and contingent choice of ad-hoc solutions.
Tools, whether codes, boundaries, molecules, or even other beings, are just so much raw material for living systems in their ceaseless self-creation, reproduction and evolution under constrained circumstances. These facts point to the fundamental nature of the tool as logically prior to the cyborg or even to the living system. Indeed, living systems especially, whether human, metazoan, bacterial, plant or fungal, have always ‘taken what they could use’. In this way, one has now deconstructed by taking to their extreme the notions of tool and cyborg so that even a bacterium may be called a cyborg in the sense of being an ‘artificial’, contingent system making its best use of ‘tools’. While the cyborg arises from a living system merging with its tools from its very beginning choosing them by means of natural selection.
Uniqueness of design may be possible sometimes, and existence of a unique necessary solution can be a beautiful thing, but in general it is a degenerate case, not to be expected in our coordinate system for understanding or in the design of other tools as we take responsibility for their construction, and thereby for the augmentation of our minds, ourselves.
A way to see that decimal expansion are not numbers is to see that the decimal system truly ‘expands’ the numbers. For instance, the representations 1.000… and 0.999… are distinct expansions of the same number, 1. Examination of the decimal expansions also shows that they given ‘historical pathways’ for getting to a number, viz. 3, 3.1, 3.14, are the first steps on a path to the ratio between a circle’s circumference and diameter π.
We contend that the decimal expansion is but one system of an entire class of computational coordinate systems for understanding, and wish to promote the techniques for generating such models, both with mathematical reasoning and, for the widest impact, with computer assistance.
When a transformation semigroup arises from a system (of states and events) to be understood, a covering of the transformation semigroup by a wreath product of simpler transformation semigroups can be considered a formal model for understanding. Such a wreath product decomposition yields a coordinate system appropriate to the original system.
As shown by Noether and Rhodes, conservation laws and symmetries lead to refined understanding of physical systems, and this understanding may be formalized as global hierarchical coordinatization. Hierarchical object structuring in computer software provides another example.
Relational morphisms can be considered as metaphors, since they can be interpreted as partially successful attempts at understanding one structuring using another. Kernel theorems for relational morphisms of transformation semigroups can then be employed as algebraic tools for the manipulation and construction of such models of / for understanding.
We suggest that developing computational tools for the implementation of feasible automatic discovery of these formal models of understanding as well as for their algebraic manipulation will extend the human notions of understanding, metaphor and analogy to a formal automated realm.
Semigroups, Automata, Transformation Semigroups
A semigroup is a set S with a binary multiplication defined on it satisfying the associative law: (xy)z = x(yz). An automaton X = (Q, S) is a set of states Q together with, for each symbol s of an input alphabet S, an associated [state-transition] function from Q to Q (also denoted by s). A special case of this is a transformation semigroup (Q, S), which is a right action of a semigroup S on a set of states Q, i.e. a rule taking q ∈ Q and s ∈ S to q.s ∈ Q, satisfying (q . s) . s’ = q . ss’ for all q ∈ Q, and s, s’ ∈ S. Given any automaton X we can canonically associate to it a transformation semigroup generated by considering the semigroup of state transition mappings induced by all possible sequence of inputs to the automaton acting on its states. To avoid trivialities, we shall always assume that state sets, input sets, and semigroups are non-empty. Generally we shall require that two distinct inputs a ≠ a’ to an automaton differ at least at one state x: x.a ≠ x.a’. Such an automaton is called faithful. The restriction of faithfulness is really not essential, as one can make X faithful by identifying input symbols which have the same action. A transformation semigroup (X, S) is faithful if x.s = x.s’ for all x ∈ X implies s = s’. One can always make a transformation semigroup faithful by identifying the s and s’ which both map X exactly the same way.
For semigroups, a homomorphism (or, more briefly, a morphism) from S to T is a function ɸ : S → T such that ɸ(ss’) = ɸ(s)ɸ(s’) for all s, s’ ∈ S. A morphism known to be surjective (onto) will be called a surmorphism and be denoted with a double-headed arrow ɸ : S ↠ T: the semigroup T is then said to be a homomorphic image of S. An injective (one-to-one) morphism ɸ is called an embedding of S into T. T is a subsemigroup of S if T is a subset of S closed under multiplication.
Thought: If something does not have a closure, then it is not a subsemigroup, but rather a partial section of the original space. A complete partition of the space into subsemigroups I think is an equivalence partition, so in that sense, closure is an important property for obtaining the subsemigroups. Verify this claim when exploring these ideas further.
We write T ≤ S if T is a subsemigroup of S or, more generally, embeds in S. If there is a bijective (one-to-one and onto) morphism from S to T, we say that S and T are isomorphic and write S ≅ T. The notation S ≺ T means S is a homomorphic image of a subsemigroup of T. Intuitively, T can emulate any computation of S. In such a case, we say S divides T.
If X = (Q, S) and Y = (U, T) are automata or transformation semigroups a morphism ɸ from X to Y consists of a function ɸ_1 : Q → U and a mapping ɸ_2: S → T (which is required to a semigroup morphism in the transformation semigroup case), such that for all q ∈ :Q and s ∈ S, one has ɸ_1(q.s) = ɸ_1(q).ɸ_2(s). Surmorphism, embedding, isomorphism, and division of transformation semigroups are defined analogously. If Y divides X, it is also common to say that X covers Y and that X emulates Y.
New Automata from Old: For transformation semigroups X = (Q, S) and Y = (U, T), their wreath product Y ≀ X is the transformation semigroup with states U × Q and semigroup consisting of all pairs (f, s) where f : Q → T and s ∈ S with action: (u, q) . (f, s) = (u . f(q), q . s). Thus the action of input (f, s) on the X component is independent of the Y component but depends only on the input, while the action Y depends on the input and the state of the X component. We have multiplication (f’, s’)(f, s) = (h,s’s) where h(q) = f’(q)f(q.s), a product in T.
To understand action and the multiplication in the semigroup, observe That
((u, q) . (f’, s’)) . (f, s) = (u . f’(q), q . s’) . (f, s) = (u . f’(q)f(q . s), q.s’s) = (u . h(q), q . s’s)
and indeed, the element h(q) in T applied to u is a function only of the input and the state q, while the element s’s in S applied to q depends only on the input (f’, s’)(f, s). The wreath product is an associative product on the class of all transformation semigroups.
More generally, transformation semigroups (X_α, S_α) generically combined with dependencies coded by an (irreflexive) partial order μ = (V, <) yield (X, S) = ∫_α ∈ V (X_α, S_α)dμ, with states X = ΠX_α and semigroup elements f : X → X with (xf)_α = x_α . f(x<_α), where f(x<_α) ∈ S_α and x<_α is the projection of x that forgets all components except the x_β with β < α. The transformation semigroup (X, S) is called the cascade integral of the (X_α, S_α) over µ.
The usual wreath product of n transformation semigroups is just a cascade integral over a finite total order. Since the hierarchies we allow for formal models of understanding permit components to be combined according to a partial ordering, the above generalized form of wreath product is very useful. For computational applications, one would evidently most often restrict to finite partial orders (as for Cartesian coordinates) or finitely many coordinates of an infinite partial order (as for the decimal expansion of the integers).
To read: Cascade decomposition of arbitrary semigroups - C. L. Nehaniv (1995)
The wreath product of faithful transformation semigroups is easily seen to be faithful. Notice that there is a hierarchical dependence of Y and on X. By iterating this construction, one may take the wreath product of any sequence of components.
The direct product (U, T) × (Q, S) of automata [resp. transformation semigroups] has state U × Q and inputs [resp. semigroup] T × S with component-wise action: (u,q) . (t, s) = (u . t, q . s). This is the case of no interaction between components.
A cascade of automata X and Y as above has states U × Q and any set of inputs (f, s) with f : Q → T and s ∈ S, acting on the states as for the wreath product. The wreath product is the transformation semigroup version of a generic cascade of automata: It is easy to see that every cascade of two automata (including of course their product) embeds in the wreath product of their associated transformation semigroups. Thus, the wreath product provides the formal algebraic framework for the notion of hierarchical combination of automata.
Given a semigroup S, we define S* to be S if S contains an identity element 1 ∈ S with s1 = 1s = s for all in S, otherwise take S* to be S with new identity element 1 adjoined. If X = (Q, S) is an automaton or transformation semigroup, we define X* = (Q, S*), where the identity of S* acts as the identity function on all states in Q. Also X^c = (Q, S^c), where for each state q ∈ Q a constant map taking value q has been adjoined as an element of S.
The disjoint union of automata X ⊔ Y has state set Q × U and inputs S ⊔ T, with
(q, u) . i = { (q.i, u) if i ∈ S | (q, u.i) if i ∈ T }
Observe that this automaton generates the direct product at the associated transformation semigroup level if X and Y contain identity transformations. Whence, X ⊔ Y embeds in X* ⊔ Y.
For a semigroup S, one obtains a canonically its so-called right regular representation (S*, S), with states S*, semigroup S and action s.s’ = ss’ for all s ∈ S* and s’ ∈ S. If S and T are semigroups, we shall write S ≀ T for the wreath product of their right regular representations.
A group is a semigroup S of a very special (symmetric and reversible) kind: S has an identity e and for each element s in S, there exists an inverse s’ in S with ss’ = s’s = e. Generally, a semigroup may contain many groups (having unrelated structures) as subsemigroups. A group is called simple if its homomorphic images are just itself and the one element group (up to isomorphism). A finite semigroup each of whose subgroups have only one element is called aperiodic.
Relational Morphisms. A relational morphism of ɸ : (X, S) ◁ (Y, T) is a subtransformation semigroup (Q, R) of (X, S) × (Y, T), thus,
(x, y) ∈ Q and (s, t) ∈ T implies (x.s, y.t) ∈ Q
and Q and R project fully onto X and S, respectively. A relational morphism is a morphism if each Q and R are [graphs of] functions, an embedding if Q and R are injective functions, or is an approximation [or simulation] of (X, S) by (Y, T) if it is a surjective morphism. It is an emulation or covering of (X, S) by (Y, T) if Q and R are injective relations: ((x, y) ∈ Q and (x’, y) ∈ Q) ⇒ x = x’
and similarly for R. If (Y, T) covers (X, S) we write (X, S) ≺ (Y, T), and often say that (X, S) divides (Y, T). Also in the case of semigroups, we write S ≺ T (S divides T) if S is a homomorphic image of a subsemigroup of T.
In the case of covering, one can use (Y, T) in place of (X, S): given x ∈ X and s ∈ S, we choose (x, y) ∈ Q and (s, t) ∈ T. The elements y and t are called lifts of x and of s, respectively. Now the state x.s is uniquely determined from y.t by the injectivity condition. If (Y, T) has a nice form, say as a wreath product of simpler transformation semigroups, then this covering provides a global hierarchical coordinate system on (X, S), which may be more convenient to manipulate and provide insights into the original (X,S).
5.2 Systems & Formal Models for Understanding
A system (X, A, λ) consists of a state spac X, inputs A, and a transition function λ : X × A → X. Traditional physics considers (or hopes) that physical phenomenon are faithfully modelled as such systems: knowing the current state x and what happens a, one can determine the resultig state as λ(x, a). Note that for a sequence of events a_1, …, a_n+1 one has a recursive description of the behaviour of the system (as λ induces an action of the free semigroup A^+ on X):
x.a_1 … a_n a_n+1 = λ(x.a_1 … a_n, a_n+1)
Crucially, such a description of the system is not a model of understanding rather only a starting point for analysis. However, such a system, if modelling real world phenomena, abstracts essential features of state and events while ignoring others. This abstraction from the real world is one property of understanding that our formalism does not address. We shall always assume the system (X, A, λ) to be available before beginning any formalization for understanding it or we shall construct it from other, already available, systems.
Indeed, A may consist of tiny intervals of time and λ describe the evolution of a physical situation accordign to a set of differential equations, e.g. determining the position and momentum of a set of point masses according to Newtonian mechanics. Such recursive descriptions including descriptions in terms of differential equations ar often the beginning of analysis of a physical system and precede formal understanding.
From (X, A, λ) one derives a transformation semigroup (X, S) by making that induced action of A^+ faithful w ≡ w’ ⇔ forAll(x ∈ X, x.w = x.w’).
Here S = A^+ / ≡.
A formal model of understanding for a system (X, A, λ) is a covering of the induced transformation semigroup (X, S) by a wreath product of “simpler” transformation semigroups over a partial ordering.
Cartesian Coordinates on Euclidean n-Space.
The n “simple” coordinates used to coordinatize Euclidean space are copies of the real numbers under addition. These copies are partially ordered by the empty partial order (no dependencies between them). In this case, there is a one-to-one correspondence from coordinates for points to points of the space, and points (or vectors) are added component-wise without regard to other components.
Symmetries of a Hexagon.
Let us imagine a regular polygon with n vertices in the plane with one vertex topmost. Let ℤ_n detone the cyclic gorup of order n (corresponding to a modulo n counting circuit). By our convention ℤ_n ≀ ℤ_2 denotes the wreath product of the right rectangular representations of ℤ_n and ℤ_2. Symmetries of a hexagon comprises the dihedral group D_6 (resp. D_n for the regular n-gon), which is covered by such a wreath product. If we paint one side of the hexagon white and the other black, and number the vertices of the hexagon clockwise on the white side from 0 to 5, then a pair (k, color) determines a configuration of the hexagon where we understand k ∈ ℤ_6 as the number on the currently topmost vertex and color ∈ ℤ_2 as the color of the face we see, either 0 denoting white or 1 denoting black. This gives a coordinate representation of the state of the hexagon.
Bruce McLennan June 20, 1994 19 Pages
If numbers are not broken down into digits but are represented by physical quantities proportional to them the computer is called an analogue. For example, a slide rule. In a simple analog computer the representing variable in the computer model is proportional to the represented variable in the modeled system.
In traditional applications of analog computing, the represented variables were continuous phyical quantities, and so the analog computer usually made use of continuous quantities (states of the analog device, such as voltages or currents) to represent them. In digital computers, in contrast, the discrete states of the computer and the values of the modeled variable are not related by a simple proportion.
There is an isomorphism (one-to-one structure preserving map) between the values of a model variable andd the values of the system variable in both analog and digital or a homomorphism (many-to-one structure preserving map) if we consider that a discrete model is an approximation of a continuous system and an analog system too can only have a finite amount of precision when it is used for simulating models.
The complementarity principle states that continuous and discrete models should be complementary, that is, an approximately-discrete continuous model should mak the same macroscopic predictions as a discrete model, and conversely an approximately-continuous discrete model shhould make the same macroscopic predictions as a continuous model.
In computation, the substance (matter and energy) is merely a carrier for the form (mathematical structure).
The principal difference between analog and digital computation is that digital compuatiton has discrete series for its successive state while for analog compuattion the states form a continuous trajectory in state space. The state space provides substance for computation upon which a form is imposed by the path through state space.
The equation: S(t’) = F[t, S(t), X(t)]
is used to characterize four kinds of autonomous systems.
If we call t as time, S(t) as dependent variables, and X(t) as independent variables, depending on whether the next state S(t’) depends on them;
Independent of X: Purely autonomous (Square root of 2) Dependent of X only at start: Less autonomous (Square root of a given number) Dependent of X anytime: Interactive computing / Feedback control system Dependent of X but independent of S: Reactive system with no memory
Axiomatic systecs studied in logic do not define a unique trajectory. Rather they define constraints (the inference rules) on allowaable trajectories, but the trajectory over which a give computation proceeds that is, the proof generated is determined by an outside agent.
Formality vs. Transduction
To the extent that the variables do refere to spcific physical quantities, equations are material.
Formal equations: Contain no physical variables while material equations do.
The formal equations specify an implementation-independent computation, whereas the material equations specify an implementation-specific transduction.
Intuitively, the formal equations are the program, the material equations are the input/output relations to the real world.
In its modern sense, calculus emboddies the idea of digital computation and formal logical inference.
Simulacrum as a possible alternate to calculus. Simulacra have images as counterparts of formulas in calculi.
One commonly distinguishes between an uninterpreted calculus andan interpreted calculus. Both hare formal computational systems, but in the former case we consider syntactic relaitons that are internal to the system, wheras in the latter we take into account semantic relaitons, which associate some meaning in an external domain with the states andd processes of the calculus, thus making them representations.
I think of this roughly as being concerned about the internal relations (syntactic) and the mappings being made from the exterior to other systems (semantics).
Systematicity in both the analog and digital cases can be defined as continuity, under the appropriate topology in each case.
Computation is the instantiation of a formal process in a physical system to the end that we may exploit or better understand that process.
A task is computational if its function would be served as well by any system with the same formal structure. Thus, computing the square root and unifying propositions are computational tasks, but digesting starch is not.
A system is computational if it accomplishes a computational task by means of a computation.
A computational system comprises a formal part (e.g., a calculus or simulacrum) and, usually, an interpretation.
Stephanie Dick