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. 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 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 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 because there are no more rewrites to apply.
Remark also that the priority of rewrites imposes a sequential path of the rewrites applications. The algorithm does not explicitly ask for such a sequential evolution. This is both a good feature of the choice of the tape word (with only one internal state symbol) and a bad feature, in the eventuality we modify the deterministic algorithm into a random one (like in chemlambda, where we use also the random algorithm where the rewrites are applied or not as a function of the result of a coin flip). Indeed, one internal state symbol (one head on the tape) imposes a sequential deterministic evolution, but it is not resilient to randomness.
More possibilities appear if we see the tape words as graphs. In this case we pass from rewrites to graph rewrites.
The previous busy beaver computation appears like this.
I used 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
. "FRIN" means "free in", is borrowed from chemlambda.
> which is a node with one "in" port. Use the notation FROUT in
. "FROUT" means "free out", is borrowed from chemlambda.
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 rules for forming a graph from a tape word are the following:
represent each symbol from the tape word as a node with ports
treat the ports as nodes in a graph as well; connect the main node which represent a symbol with its ports by a bond (link) which is tagged as "internal"
connect by a link which is tagged as "external" the "out" port of a symbol with the "in" port of the symbol which follows (from left to right) on the tape.
Now we can write a tape word as a mol file. Tag the ports with arbitrary names, such that two ports have the same name if and only if there is an external link which connects them. Then the mol notation for the tape word is a list of main nodes and the names of their ports.
Thus for example the tape word < A > appears as the list: FRIN 1 , A 1 2 , FROUT 2. The names used for the ports are in this example 1 and 2, but any name would be as good. The names of the ports are variables which appear twice in any mol file. They will not flow around in the graph, so there is no other management of these variables than making sure that at the start of the computation each of those appear twice in the mol file.
Remark that the LT and the RT of any rewrite are transformed into pieces of graphs which have loose ends (these are the external links which connect a port from the LT or RT pattern with the rest of the graph). In the mol notation they are nothing but lists of nodes with named ports. The rewrite becomes a graph rewrite, which consists into cutting of a small graph (the LT in graphical form), tagging of the loose ends of the LT pattern with the name of the respective ports and replacing it by another small graph (the RT in graphical form), by using the tags of the loose ends of the LT pattern in order to connect the RT pattern correctly.
For example the first blank rewrite < X - - > < b X transforms into
FRIN 1 , X 1 2 - - > FRIN 1 , b 1 w , X w 2 , where w is any fresh port name. The difference between a rewrite and a graph rewrite is that the LT and the RT patterns are not formed by successive elements in a list. If we think about the mol notation for a tape word, then to each symbol from the tape there is a corresponding line in the mol file which represents that symbol. But the order of the lines in the mol file is arbitrary, so the LT pattern for the graph rewrite (from this example) is a set (not a list) of lines from the mol file. The information about the graph is in the repetition of the ports names.
(TO BE CONTINUED...)
References concerning the chemlambda project:
[1] (journal)(arxiv) - M. Buliga, Graphic lambda calculus. Complex Systems 22, 4 (2013), 311-360
[2] (doi)(arxiv) - M. Buliga, Chemical concrete machine (2013).
[7] (doi) M. Buliga, Build a molecular computer. Journal of Brief Ideas, (2015).
[8] (html) M. Buliga, Molecular computers, (2015).
This version: April 16, 2015
Note: I am always glad to be corrected and to learn more, therefore I welcome any informed critic which could enhance this work. The best would be to make such critics in a public way, which moreover can be validated by any external third party, simply from the information you provide in the critic or comment or review, and from the information provided here.