A Mechanical Turing Machine:
Blueprint for a Biomolecular Computer
Udi Shapiro
Ehud Shapiro
A Mechanical Turing Machine:
Blueprint for a Biomolecular Computer
Udi Shapiro
Ehud Shapiro
Medicine in 2050
Medicine in 2050: “Doctor in a
Cell”
A genetically modified cell that can
operate in the human body
with an intra-cellular computer
that receives input from signal
transduction pathways
and, based on its program, produces
output to protein synthesis and secretion
pathways
effecting any desired molecular medical
treatment
Medicine in 2050: “Doctor in a
Cell”
Programmable Computer
Programmable Computer
Possible types of molecular
output
Drugs (proteins and small molecules)
synthesized on-command by the cell
Stress signals detectable by external
devices
Encoded “status report” messages
decipherable by external devices
Possible types of molecular
treatment
Simple stimulus-response
Output multiple drugs based on multiple
signals and a decision procedure
Feedback-controlled drug output
(titration, negative control)
Any repetitive, programmable
combination of the above
Possible types of “cellular
doctors”
“Generalists” that circulate in the blood
and lymphatic vessels
“Specialists” that reside in specific
organs (heart, liver, kidney, bone
marrow)
All use the same intra-cellular computer,
each with different “software”
A design for an intra-cellular
computer should be
Implementable from biomolecules
(biopolymers)
that utilize standard operations of
biomolecular machines (polymer
cleavage, ligation, elongation, movement
along a polymer, control via allosteric
conformational changes), and can
sense biomolecular input, and
synthesize biomolecular output
Logical Design for an
Intra-Cellular Computer
1900 Hilbert Posed a Problem
23
rd
: Find a method for deciding the
truth or falsity of any statement of
predicate calculus (decision procedure)
Part of larger program to establish all of
mathematics on solid formal foundation,
by proving every mathematical theorem
mechanically from “first principles” (first
order logic and elementary set theory)
1936 Turing had an answer...
Hilbert’s 23
rd
problem has no solution,
i.e., there is no such procedure
The proof required to formalize the
notion of a procedure
So Turing defined a “pencil-and-paper”
computation device, now called the
Turing Machine
and established its universality (Church-
Turing thesis)
The Turing Machine
D A T A
INFINTE TAPE
Finite Control may be in one of
finitely many states S0,S1,
…,Sn
Read/Write Head may
read and/or write a
symbol, and move one
cell to the left or to
the right
Tape Cell may
contain one symbol
of a given tape
alphabet
S
7
Transitions
If the control is in state S and the
read/write head sees symbol A to the
left [right], then change state to S’,
write symbol A’, and move one cell to
the left [right].
S,A A’,S’ or
A,S S’,A’ where A can be “blank”
Configuration
D
D
C
C
A
A
B
B
S
S
State symbol and location of read/write head
State symbol and location of read/write head
Alphabet tape symbols
Alphabet tape symbols
D
D
C
C
A
A
B
B
S0
S0
Initial configuration
Initial configuration
Accept well-formed expressions over “(“ and
“)“
(), (()), ()(), (())() are well-formed, ((), )(, ()), ()
()(, are not.
States:
•
S0: Scanning right, seeking right parenthesis
•
S1: Right paren found, scan left seeking left paren.
•
S2: Right end of string found, scan left, accept if no
excess parens found.
•
S3: Accept
Example Control Program:
Well-formed
Expressions
Example computation
#
#
#
#
#
#
Scan right to first )
Scan right to first )
Scan left to first (
Scan left to first (
Scan right to first )
Scan right to first )
Scan left to left paren
Scan left to left paren
Stop, not accepting
Stop, not accepting
( ) )
S0
S0,( (,S0
S0,# , #,S0
S0,) #,S1 (erase right paren and enter S1)
S0,blank #,S2 (end of string, enter S2)
(,S1 S0,# (erase left paren and enter S0)
#,S1 S1,#
#,S2 S2,#
blank,S2 S3,# (end of string, enter S3)
Example Control Program:
Well-formed Expressions
A Mechanical Turing Machine
04/04/21
Alphabet monomers
Alphabet monomers
Transition monomers
Transition monomers
Control
Control
Device Components
04/04/21
Alphabet Monomers
Side group representing symbol
Side group representing symbol
Left Link
Left Link
Right Link
Right Link
A
A
D
D
C
C
B
B
Alphabet Polymer
Alphabet Polymer
Alphabet Monomer
Alphabet Monomer
A
A
04/04/21
Transition Molecules
S’
S’
A
A
S
S
Transition Molecule for
Transition Molecule for
A,S
S’,X
One side group representing target state
S’
Three recognition sites: source state S,
source symbol A, target symbol A’
04/04/21
Transition Molecules
S’
S’
A
A
S
S
Transition Molecule for
Transition Molecule for
A,S
A,S
S’,X
S’,X
Transition Molecule for
Transition Molecule for
S,A
X,S’
S’
S’
A
A
S
S
A Loaded Transition Molecule for
A Loaded Transition Molecule for
A,S
S’,A’
A’
A’
S’
S’
A
A
S
S
Example Configuration
D
D
C
C
A
A
B
B
S’
S’
A
A
S
S
04/04/21
Trace polymer
A
A
B
B
C
C
S0
S0
S0
S0
S1
S1
D
D
S1
S1
D
D
E
E
S2
S2
Tape polymer
Current state
Example Configuration
04/04/21
S1
S1
D
D
Example Transition: Before
A
A
B
B
C
C
S0
S0
S0
S0
S1
S1
D
D
E
E
S2
S2
S2
S2
C
C
F
F
S3
S3
The device in operation:
Before
04/04/21
Example Transition: After
A
A
B
B
C
C
S0
S0
S0
S0
S1
S1
D
D
S1
S1
D
D
E
E
S2
S2
S2
S2
C
C
F
F
S3
S3
The device in operation: After
Example Control Program:
Well-formed Expressions
(
(
(
(
S0
S0
S0
S0
#
#
#
#
S0
S0
S0
S0
#
#
)
)
S0
S0
S1
S1
#
#
b
b
S0
S0
S2
S2
#
#
S1
S1
(
(
S0
S0
#
#
S1
S1
#
#
S1
S1
2
2
#
#
S2
S2
#
#
S2
S2
#
#
S2
S2
b
b
S3
S3
Example Trace Polymer
A’
A’
S’
S’
A
A
S
S
A’
A’
S’
S’
A
A
S
S
A’
A’
S’
S’
A
A
S
S
A’
A’
S’
S’
A
A
S
S
A
A
A
A
A
A
A
A
Implementation
Implementation
Alphabet Molecules
Transition Molecules
04/04/21
3
3
5
5
2
2
2
2
4
4
6
6
5
5
3
3
6
6
4
4
1
1
1
1
Before
Before
After
After
A Transition
A Transition
The Device
04/04/21
Device ~ Ribosome
Both operate on two polymers symultaneously
Tape polymer ~ messenger RNA
Transition molecule ~ transfer RNA
Trace polymer ~ Polypeptide chain
Move one cell per transition ~ Move one codon
per transition
04/04/21
Device is unlike the
Ribosome
Read/write tape vs. Read-only tape
Transition molecule with side group vs. transfer
RNA without side group
Move in both directions vs. Move in one
direction
Trace polymer made of transition monomers
vs. Polypeptide chain made of amino acids
Cellular Input
Computer Input
Device suspends if needed molecules are
not available
Non-deterministic choices can be affected by
availability of molecules
Hence device can be sensitive to chemical
environment
Cellular output
Computer Output
Device extended with transition that cleaves the
tape polymer and releases one part to the
environment
Hence device can synthesize any computable
polymer of alphabet molecules
If alphabet monomers are ribonucleic acids, cleaved
segment can be used as messenger RNA
Ultimately...
Ultimately...
Universal programmable computing device
that can operate in vivo
Can interact with biochemical environment
Can be “sent on a mission”
Can diagnose, prescribe, synthesize, and
deliver...
Related work
C. H. Bennett 1970-
•
“Assignment considered
(thermodynamically) harmful”
•
Reversible computation is the answer
•
“Hypothetical Enzymatic Turing machine”
L.M. Adelman et al. 1994-
•
DNA Computing
•
“Biological steps” (outside intervention)
•
Self-assembly (tiling)
S. A. Kurtz et al. 1997
•
Hypothetical modified ribosome implements
string rewriting on RNA
