If you look for validation, then go follow the instructions from
and use the file bbdupli.mol
This animation starts with one Turing Machine and ends with three Turing Machines.
Let’s take it slower.
1. Everybody knows what is a TM. Computers are the real thing which resembles most to a TM. There is lot of stuff added, like a screen, keyboard, a designer box, antennas and wires, but essentially a computer has a memory which is like a tape full of bits (0 and 1) and there is a processor which is like a read/write head with an internal state. When the head reads a bit from the tape then the internal state changes, the head writes in the tape and then moves, according to some internal rules.
2. These rules define the TM. Any rule goes, but among them there are rules which make the TM universal. That means that there are well chosen rules such that if you first put on the tape a string of bits, which is like the OS of the computer, and if you place the head at the beginning of this string, then the TM (which obbeys those clever rules) uploads the OS and then it becomes the TM of your choice.
3. From here it becomes clear that these rules are very important. Everything else is built on them. There are many examples of rules for universal TM, the more or less precise estimate is that for a tape written with bits (0 and 1) the known universal TM need about 20 rules.
4. Just a little bit earlier than the TM invention, lambda calculus has been invented as well, by Alonzo Church. Initially the lambda calculus was a monumental formalism, but after the TM invention there was a variant of it, called untyped lambda beta calculus, which has been proved to be able to compute the same things as a TM can compute.
The untyped lambda beta calculus is famous among the CS nerds and much less known by others (synthetic biologists, I’m looking at you) who think that TM are the natural thing to try to emulate with biology and chemistry, because it is obviously something everybody understands, not like lambda calculus which goes into higher and higher abstractions.
There are exceptions, the most famous in my opinion is the Algorithmic Chemistry (or Alchemy) of Fontana and Buss. They say that lambda calculus is chemistry and that one operation (called application) of LC is like a chemical reaction and the other operation (called abstraction) is like a reactive site. (Then they change their mind, trying to fit types into the story, speaking about chemicals as functions, then they use pi calculus, all very interesting but outside of the local goal of this post. Will come back later to that.)
Such exceptions aside, the general idea is: TM easy, LC hard.That is false and I shall prove it. The side bonus is that I can teleport Turing machines.
5. If we want to compare TM with LC then we have to put them on the same footing, right? This same footing is to take the rules of TM and the reductions of LC as rewrites.
But, from the posts about chemlambda, rewrites are chemical reactions!
- LC is actually much simpler than TM, because it uses only one rewrite which is specific to it (the BETA rewrite) instead of about 20 min for the TM
- LC and TM are both compatible with the chemical approach a la chemlambda, in the sense that chemlambda can be enhanced by the addition of “bits” (red and green 2 valent nodes), head move (Arrow element) and TM internal states (other 2-valent nodes) and by some “propagation” rewrites, such that chemlambda can now do both TM and LC in the same time!
In the animation you see, at the beginning, something like
– a tree made of green fanout (FO) nodes (and yellow FRIN and magenta FROUT leaves) and
– a small ring of green (2-valent, bit 0) and pale green (a state of a TM). That small ring is a TM tape which is “abstracted”, i.e. connected to a lambda abstraction node, which itself is “applied” (by an application A node) to the fanout tree.
What happens? Eventually there are produced 3 TM (you see 3 tapes) which function independently.
They are actually in different states, because the algorithm which does all this is random (it does a rewrite if a coin has the fancy to drop in the right state).
The algorithm is random (simulation of asynchronous behaviour) and all rewrites are local (simulation of decentralized).
Only a simulation which shows it is perfectly possible. The real thing would be to turn this into a protocol.