HOME

• Home

Theory of X-Machines

• History of X-Machine Theory
• Physical Description
• When is a function X-computable?
• Monoids and X-machines

Reference

• Notation
• Bibliography

MOTIVE

• The MOTIVE Project

X-Computability

f ---->

( Equ. 1 )

Given this situation, it appears that every relation is computable by X-machine, so that our question is vacuous. This intuition is wrong in an important way, but understanding the error requires a more careful discussion of what we mean by the term computability itself.

We are accustomed in theoretical computer science to such statements as the square-root function, sqrt, is computable, but we can end up using terms so freely that we forget their exact meaning. We contend that, even in standard computational theory, the phrase "sqrt is computable" has no independent meaning. Rather, it is a convenient abbreviation for the much more cumbersome phrase "given the rules of Turing-machine computation, and given certain basic interpretations of bit patterns expressed by marking various squares on a tape, there is a Turing-machine program which can be thought of as a representation of sqrt". In other words, while we appear to be talking about a single, well-defined relation sqrt, we are actually discussing a set of relations, of which sqrt is just one constituent part.

The question, then, is not "when is a relation computable by X-machine?," but rather, "given a set S of relations, what does it mean to say, in the context of X-machines, that S is a mutually computable set of relations?" To use a biological metaphor, it is helpful to think of X-machines as describing species rather than individual animals. Species are generally defined by the ability of animals to interbreed, but this definition is only ever relevant to collections of animals rather than individuals, because it is entirely possible for two individuals of the same species to be incapable of successful breeding. In the same way, "being computable by X-machine" is something that has little meaning for individuals, but can nonetheless identify collections of relations rather accurately. Now that it has been properly phrased, our question does have an answer, and one that is both meaningful and useful.

Recall (see Physical Description) that an X-machine is essentially a finite state machine (FSM) whose labels are interpreted not as abstract symbols in an alphabet, but as relations on some set X. We can think of X as an auxiliary memory, the control system of a second machine, or whatever else seems appropriate for the system being modelled. Given that X-machines and FSMs differ only in their interpretation of labels, our investigation of X-machines, and especially our understanding of the ways in which X-machines go beyond FSMs, must begin with a correct understanding of labels.

The standard notation we have developed for this context is as follows.

• Firstly, because FSMs are often used to recognise whether or not words belong to a language, the abstract labels attached to the arcs of an FSM are normally called its alphabet, aF. However, when we come to discuss the role of general topology in X-machine theory, we'll be using a construct called the Alexandrov compactification of X, which is also traditionally denoted aF. To avoid confusion later, we'll write Labels(F) instead of aF, or if F can be taken for granted, simply Labels.
   
• Next, we'll frequently need to talk about the collection of relations on a set X, and we'll call this collection Rel_X. In mathematical terms this set forms a semigroup under relational composition. In other words, whenever you compose two such relations, you get another i.e., if you apply first one and then the other, there is some third relation on X that has the same overall effect. Any subset of Rel_X that is also a semigroup under relational composition is called a sub-semigroup of Rel_X. It's important to bear in mind that relational composition typically works the "wrong way round;" that is, given two relations f and g, their composition (fg) is the relation defined by switching the order of f and g, like this,

  (fg)(x) = g(f(x))

  ( Equ. 2 )

  For this reason, it is common to see the application of f to x written xf rather than f(x), because using right-sided application in this way maintains the typographical order of terms when we expand complicated formulae, e.g.,

  (((xf0)f1)f2)...fn = x(f0f1f2...fn)

  ( Equ. 3 )

  
   

• Finally, we borrow terminology from permutation theory. If x is some object of type X, and f is a relation on X, we say that f acts on X, call f an action, and write x^f instead of f(x). Thinking of f as an action effectively allows us to apply dynamic metaphors to the relations on X. In essence, we regard the action f as a mechanism for "stirring X up." Applying f once has the effect of moving each x to its corresponding x^f. If we now apply another action g we'll stir X again, this time moving x^f to (x^f)^g, and its a simple matter to confirm that this is the same as x^(fg), so that this notation is consistent with, and indeed highlights, the semigroup structure of Rel_X.
   

Accordingly, we think of an X-machine, M, as an FSM equipped with a labelling function, viz.

L: Labels ----> RelX

( Equ. 4 )

so that traversing an arc labelled a in the FSM corresponds to the X-machine behaviour "now perform the action a^L." Similarly, traversing a path a = a₀...a_n in the FSM is equivalent to applying the action

aL = a0L ... anL

( Equ. 5 )

Regular Languages vs. Rel_X

Now just as Rel_X forms a semigroup under relational composition, so A*, the set of all finite strings written using characters from A (including e, the empty string) forms a semigroup under string concatenation, because combining any two finite strings over A forms a third. What's more, because

(ab)L = aLbL

( Equ. 6 )

for every pair of strings s, t, it's clear that these two semigroups have closely related structures. The labelling function L mediates this relationship by linking the two semigroups together while preserving their essential family resemblance. We call structure-preserving functions between semigroups (in the sense of Equ. 6) homomorphisms. Formally, then, we can regard L as the homomorphism that maps each recognised string a = a₀...a_n to the action a^L of (Equ. 5).

(Equ. 6) tells us that recognised strings in the world of finite state machines are closely related to path computations in X-machines, and in consequence that X-machine computations are closely related to regular languages. We've seen already that each string in a regular language corresponds via L to a path computation in an X-machine. Now the relation computed by an X-machine is defined to be simply the union of all its path computations. So, if we obtain the X-machine M by attaching the labelling L to the finite state machine, F - written

M = FL

( Equ. 7 )

- then the relation |M| computed by M is related to the language |F| recognised by F by the simple formula

|M| = È{ aL | a Î |F| }

( Equ. 8 )

A language over A just means "a subset of A*." Taking our cue from (Equ. 8), let's consider the function

LL = È{ aL | a Î L }

( Equ. 9 )

which maps each language L, via the labelling L, to a well-defined action L^L in Rel_X.

Combining (Equ. 7, Equ. 8, Equ. 9) tells us that, whenever F is an FSM, X is a datatype and L is a labelling into Rel_X, the operations |·| and ·^L commute, viz.

|FL| = |F|L

( Equ. 10 )

Labellings of N

L~(b) = L(subst(b)) = bsubst.L

( Equ. 11 )

and now it is a straightforward matter to verify that

F~L~ = FL

( Equ. 12 )

Consequently, it doesn't much matter what we call the characters in our alphabet, just as long as we have enough of them to label each machine appropriately. To simplify matters, then, we shall choose a fixed alphabet, and use it for every FSM we need to construct. Although any given recogniser can employ at most finitely many labels, there is no upper bound to the number of labels that might be needed, so we'll take as our alphabet the set N of natural numbers. Each labelling L is accordingly assumed to be a labelling of N, L: N ----> Rel_X.

X-computable subsets of Rel_X

|L| = { LL | L is a regular language }

( Equ. 13 )

of all L-computable relations will be called the L-computable subset of Rel_X. A subset of Rel_X is X-computable if it is L-computable for some L.

The extent to which L-computable subsets of Rel_X are "computable" relative to standard conceptions of the term will be discussed in our next entry, but it should already be clear that, general though this definition is, it can happen that X-computability is no longer vacuous.

If X is infinite, not every subset of Rel_X is X-computable.

This is because there are at most |Rel_X^N| labellings available, but 2^|Rel_X| subsets of Rel_X. Now, since Rel_X = 2^X×X, we have |Rel_X| = 2^|X| whenever X is infinite. Consequently, for infinite X, we have

|RelXN| = (2|X|)^|N| = 2|X| but 2^|RelX| = 22^|X|

( Equ. 14 )

whence 2^|Rel_X| (the number of subsets of Rel_X) is exponentially larger than |Rel_X^N| (the number of distinct labellings available).