2/20/2022 06:06

A Machine is an Ordered 7-tuple

The classic definition of an abstract computing machine is intellectually intriguing. That is where it gets its power. Nearly everyone who has been involved in computing sciences must surely have been caught up in Alan Turing's definition of a Machine or its variations.

A machine is an ordered 7-tuple consisting of the set S of all possible States, the set T of Tokens, an initial state i₀ which is an element of S, a subset F of S naming the final or terminating states, the subset of states which accept an input token, another subset which emit an output token, and a transition matrix or function built from the other elements (plus some actions like move, write, and erase). Or a variant of that definition to a similar effect.

I was recently reminded of this abstract machine. Half a century after first discovering it the definition still has its hold on me and I've been thinking about it for days.

And yet I find it unsatisfying.

For one thing this definition is inelegant. For example, defining the states and tokens and then building the machine from them makes excellent sense heuristically. Definitionally the result is that the list of states is doubly defined: The states used by the machine can be derived from the transitions. The same is true for the available tokens.

Even while the redundance is only justified heuristically, the definition is heurisitcally impoverished with regard to the concepts of programming. There is no mechanism for describing repetition (looping) or reuse (subroutines) or for partitioning the steps based on the purpose or the effect they accomplish. A mathematically oriented computer scientist can wallow in the transition matrix but anyone who is algorithmically minded will have to leave the 7-tuple for some other comceptualization.

A third dissatisfaction is that the 7-tuple provides no mechanism for our machine to rewrite its transition matrix and so recreate itself. This capability was not within the scope of Turing's original discussion but it is a core feature of general purpose computers. An abstract definition of modern computers needs to include the essential feature that the program is also data.

For days I have been pondering how to replace the old definition of an abstract computing machine with a new definition from which the computer and its programming would spring naturally in some completeness. I may not accomplish that (and who would know if I did?) but the power of Alan Turing's original conception is shown by the fact that the task captured me again a few days ago.