Turing Machines, chemlambda style (I)

UPDATE: First animation and a more detailed version here. There will be many additions, as well as programs available from the gh-pages of the repo.

Once again: why do chemists try to reproduce silicon computers? Because that’s the movie.

At first sight they look very different. Therefore, if we want to compare them, we have to reformulate them in ways which are similar. Rewrite systems are appropriate here.
The Turing Machine (TM) is a model of computation which is well-known as being a formalisation of what a computer is. It is a machine which has some internal states (from a set S), has a head which read/writes symbols (from a set A) on a tape. The tape is seen as an infinite word made of letters from A. The set A has a special letter (call it “b” from blank) and the infinite words which describe tapes have to be such that all but a finite number of letters of that word are different from “b”. Imagine an infinite, in both directions, tape which has written symbols on it, such that “b” represents an empty space. The tape has only a finite part of it filled with letters from A, others than the blank letter.
The action of the machine depends on the internal state and on the symbol read by the head. It is therefore a function of the internal state of the machine (element of S), the letter from the tape which is read (element of A), and outputs a letter from the alphabet A (which is written in the case where previously was the letter which has been read, changes its internal state, and the head moves one step along the tape, to the left (L) or right (R), or does not move at all (N).
The TM can be seen as a rewrite system.
For example, one could see a TM as follows. (Pedantically this is seen as a multi-headed TM without internal states; the only interest in this distinction is that it raises the question if there is really any meaning into discerning internal states from the tape symbols.) We start from a set (or type) of internal states S. Such states are denoted by A, B, C (thus exhibiting their type by the type of the font used). There are 3 special symbols: < is the symbol of the beginning of a list (i.e. word), > is the symbol of the end of a list (word) and M is the special symbol for the head move (or of the type associated to head moves). There is an alphabet A of external states (i.e. tape symbols), with b (the blank) being in A.
A tape is then a finite word (list) of one of the forms < w A w’ > , < w M A w’ > , < w A M w’ >, where A is an internal state and w and w’ are finite words written with the alphabet A, which can be empty words as well.
A rewrite replaces a left pattern (LT) by a right pattern (RT), and there are denoted as LT – – > RT . Here LT and RT are sub-words of the tape word. It supposed that all rewrites are context independent, i.e. LT is replaced by RT regardless of the place where LT appears in the tape word. The rewrite is called “local” if the lengths (i.e. number of letters) of LT and RT are bounded a priori.
A TM is given as a list of Turing instructions, which have the form (current internal state, tape letter read, new internal state, tape letter write, move of the tape). In terms as explained here, all this can be expressed via local rewrites.

• Rewrites which introduce blanks at the extremities of the written tape:
• < A   – – >   < b A
• A >   – – >   A b >
• Rewrites which describe how the head moves:
• A M a   – – >   a A
• a M A   – – >   A a
• Turing instructions rewrites:
• a A c   – – >   d B M c   , for the Turing instruction (A, a, B, d, R)
• a A c   – – >   d M B c   , for the Turing instruction (A, a, B, d, L)
• a A c   – – >   d B c   , for the Turing instruction (A, a, B, d, N)
Together with the algorithm “at each step apply all the rewrites which are possible, else stop” we obtain the deterministic TM model of computation. For any initial tape word, the algorithm explains what the TM does to that tape. < don’t forget to link that to a part of the Cartesian method “to be sure that I made an exhaustive enumeration” which is clearly going down today > Other algorithms are of course possible. Before mentioning some very simple variants of the basic algorithm, let’s see when it works.
If we start from a tape word as defined here, there is never a conflict of rewrites. This means that there is never the case that two LT from two different rewrites overlap. It might be the case though, if we formulate some rewrites a bit differently. For example, suppose that the Turing rewrites are modified to:
• a A   – – >   d B M   , for the Turing instruction (A, a, B, d, R)
• a A   – – >   d M B   , for the Turing instruction (A, a, B, d, L)
Therefore, the LT of the Turing rewrites is no longer of the form “a A c”, but of the form “a A”. Then it may enter in conflict with the other rewrites, like in the cases:

• a A M c where two overlapping rewrites are possible
• Turing rewrite: a A M c   – – >   d M B M c &nbsp which will later produce two possibilities for the head moves rewrites, due to the string M B M
• head moves rewrite: a A M c   – – >   a c A &nbsp which then produces a LT for a Turing rewrite for c A, instead of the previous Turing rewrite for a A
• a A > where one may apply a Turing rewrite on a A, or a blank rewrite on A >
The list is non exhaustive. Let’s turn back to the initial formulation to the Turing rewrites and instead let’s change the definition of a tape word. For example, suppose we allow multiple TM heads on the same tape, more precisely suppose that we accept initial tape words of the form < w1 A w2 B w3 C … wN >. Then we shall surely encounter conflicts between head moves rewrites for patterns as a A M B c.
The most simple solution for solving these conflicts is to introduce a priority of rewrites. For example we may impose that blank rewrites take precedence over head moves rewrites, which take precedence over Turing rewrites. More such structure can be imposed (like some head moves rewrites have precedence over others). Even new rewrites may be introduced, for example rewrites which allow multiple TMs on the same tape to switch place.
Let’s see an example: the 2-symbols, 3-states

busy beaver machine

. Following the conventions from this work, the tape letters (i.e. the alphabet A) are “b” and “1”, the internal states are A, B, C, HALT. (The state HALT may get special treatment, but this is not mandatory). The rewrites are:

• Rewrites which introduce blanks at the extremities of the written tape:
• < X   – – >   < b X   for every internal state X
• A >   – – >   A b >   for every internal state X
• Rewrites which describe how the head moves:
• X M a   – – >   a X   , for every internal state X and every tape letter a
• a M X   – – >   X a   , for every internal state X and every tape letter a
• Turing instructions rewrites:
• b A c   – – >   1 B M c   , for every tape letter c
• b B c   – – >   b C M c   , for every tape letter c
• b C c   – – >   1 M C c   , for every tape letter c
• 1 A c   – – >   1 HALT M c   , for every tape letter c
• 1 B c   – – >   1 B M c   , for every tape letter c
• 1 C c   – – >   1 M A c   , for every tape letter c
We can enhance this by adding the priority of rewrites, for example in the previous list, any rewrite has priority over the rewrites written below it. In this way we may relax the definition of the initial tape word and allow for multiple heads on the same tape. Or for multiple tapes.
Suppose we put the machine to work with an infinite tape with all symbols being blanks. This corresponds to the tape word < A >. Further are the steps of the computation:
• < A >   – – >   < b A >
• <b A >   – – >   < b A b >
• < b A b >   – – >   < 1 B M b >
• < 1 B M b >   – – >   < 1 b B >
• < 1 b B >   – – >   < 1 b B b >
• < 1 b B b >   – – >   < 1 b C M b >
• < 1 b C M b >   – – >   < 1 b b C >
• < 1 b b C >   – – >   < 1 b b C b >
• < 1 b b C b >   – – >   < 1 b 1 M C b >
• < 1 b 1 M C b >   – – >   < 1 b C 1 b >
• < 1 b C 1 b >   – – >   < 1 1 M C 1 b >
• < 1 1 M C 1 b >   – – >   < 1 C 1 1 b >
• < 1 C 1 1 b >   – – >   < 1 M A 1 1 b >
• < 1 M A 1 1 b >   – – >   < A 1 1 1 b >
• < A 1 1 1 b >   – – >   < b A 1 1 1 b >
• < b A 1 1 1 b >   – – >   < 1 B M 1 1 1 b >
• <1 B M 1 1 1 b >   – – >   < 1 1 B 1 1 b >
• < 1 1 B 1 1 b >   – – >   < 1 1 B M 1 1 b >
• < 1 1 B M 1 1 b >   – – >   < 1 1 1 B 1 b >
• < 1 1 1 B 1 b >   – – >   < 1 1 1 B M 1 b >
• < 1 1 1 B M 1 b >   – – >   < 1 1 1 1 B b >
• < 1 1 1 1 B b >   – – >   < 1 1 1 1 B M b >
• < 1 1 1 1 B M b >   – – >   < 1 1 1 1 b B >
• < 1 1 1 1 b B >   – – >   < 1 1 1 1 b B b >
• < 1 1 1 1 b B b >   – – >   < 1 1 1 1 b C M b >
• < 1 1 1 1 b C M b >   – – >   < 1 1 1 1 b b C >
• < 1 1 1 1 b b C >   – – >   < 1 1 1 1 b b C b >
• < 1 1 1 1 b b C b >   – – >   < 1 1 1 1 b 1 M C b >
• < 1 1 1 1 b 1 M C b >   – – >   < 1 1 1 1 b C 1 b >
• < 1 1 1 1 b C 1 b >   – – >   < 1 1 1 1 1 M C 1 b >
• < 1 1 1 1 1 M C 1 b >   – – >   < 1 1 1 1 C 1 1 b >
• < 1 1 1 1 C 1 1 b >   – – >   < 1 1 1 1 M A 1 1 b >
• < 1 1 1 1 M A 1 1 b >   – – >   < 1 1 1 A 1 1 1 b >
• < 1 1 1 A 1 1 1 b >   – – >   < 1 1 1 HALT M 1 1 1 b >
• < 1 1 1 HALT M 1 1 1 b >   – – >   < 1 1 1 1 HALT 1 1 b >
At this stage there are no possible rewrites. Otherwise said, the computation stops. Remark that the priority of rewrites imposed a path of the rewrites applications. Also, at each step there was only one rewrite possible, even if the algorithm does not ask for this.
More possibilities appear if we see the tape words as graphs. In this case we pass from rewrites to graph rewrites. Here is a proposal for this.
I shall use the same kind of notation as in

chemlambda: the mol format

. It goes like this, explained for the busy beaver TM example. We have 9 symbols, which can be seen as nodes in a graph:

• < which is a node with one “out” port. Use the notation FRIN out
• > which is a node with one “in” port. Use the notation FROUT in
• b, 1, A, B, C, HALT, M which are nodes with one “in” and one”out” port. Use a notation Name of node in out
The rule is to connect “in” ports with “out” ports, in order to obtain a tape word. Or a tape graph, with many busy beavers on it. (TO BE CONTINUED…)