Home | X-Computability X-Machines.Com


Theory of X-Machines




Historically the question what does computability mean in terms of X-machines has foundered on the observation that, given any set-theoretic relation, f, we can construct a datatype X and a simple one-arrow X-machine that seems, intuitively at least, to 'compute' that relation.

( 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 RelX. 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 RelX that is also a semigroup under relational composition is called a sub-semigroup of RelX. 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 xf 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 xf. If we now apply another action g we'll stir X again, this time moving xf to (xf)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 RelX.

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 aL." Similarly, traversing a path a = a0...an in the FSM is equivalent to applying the action

aL = a0L ... anL ( Equ. 5 )

Regular Languages vs. RelX

Suppose, then, that we've got some alphabet A from which FSM labels will be chosen. In line with Eilenberg's original formulation, certain of the underlying FSM's states are marked out as valid initial states and others as terminal states, and the computation paths of the machine are those that lead from an initial state, through consecutives arrows of the FSM, to end at a terminal state. In traversing a computation path, the arc labels "spell out" a word one character at a time, and we say that the machine recognises the word. The set of all recognised strings is the language recognised by the machine, and we refer to the machine as a finite state recogniser for that language. Languages that can be recognised (or if you prefer, generated) in this way by finite state machines are called regular languages and play an important part in theoretical computer science.

Now just as RelX 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 = a0...an to the action aL 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 LL in RelX.

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 RelX, the operations || and L commute, viz.

|FL| = |F|L ( Equ. 10 )

Labellings of N

Although we've been discussing a particular alphabet A, it should be obvious that the actual identity of A is irrelevant. For suppose B is another set of the same cardinaility as A, and that subst: B ----> A is a 1-1 correspondence. Given an X-machine M = FL, where A = Labels(F), we can construct an equivalent representation of M using the label-set B instead of A as follows. Keeping the same underlying structure of arcs, we construct a new recogniser F~ by replacing every label a of F with the label b = subst-1(a). Similarly, we replace L with L~, where for each b in B,

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 ----> RelX.

X-computable subsets of RelX

We have seen that each labelling L induces a mapping L of regular languages to relations on X. If f = LL for some regular language we shall say that f is L-computable, and for any given L, the set

|L| = { LL | L is a regular language } ( Equ. 13 )

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

The extent to which L-computable subsets of RelX 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 RelX is X-computable.

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

|RelXN| = (2|X|)^|N| = 2|X|


2^|RelX| = 22^|X|

( Equ. 14 )

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

Copyright © 2000-2013 Mike Stannett. All Rights Reserved.