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

S

S

0

0

(

(

)

)

)

)

Movie

Movie

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

S0

L

R

R

L

L

S0

S0

Example Computation

Movie

Movie

We show only “good” random moves

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