Transcript Slide 1

Natural Algorithms
God,
Physics and the
Natural-Computer
Joshua Arulanandham
Computer Science
The wonders of the world come in two flavours!
How water “finds” the average
l1
l2 l3 (l1 + l2 + l3 ) / 3
Water finds the same level in all limbs due to atmospheric pressure.
How to make a “computer” with beads , rods and
gravity
+
+
=
A “computer” that runs on gravity
4
3
3
4
A “computer” that runs on gravity
3
2
2
2
4
2
3
4
A “computer” that runs on gravity
Sorting {3, 1, 2}
1. Drop 3 beads
(Remember, always from left-to-right)
2. Drop 1 bead
3. Drop 2 beads
1
2
3
A “computer” that runs on gravity
Sorting {2, 4, 3, 2}
1. Drop 2 beads
(Remember, always from left-to-right)
2
2
2. Drop 4 beads
3. Drop 3 beads
3
4. Drop 2 beads
4
The bead-sort computer
The “tilt” operation
900
Calculating shortest path using strings and beads
E (Destination)
Shortest
path
D
A
C
B
(Source)
As the source, destination nodes in the physical graph-model are stretched apart, the shortest path forms a
straight line between them.
A computer made of pipes and pistons
Is (~a + b)(a + b) satisfiable?
(~a + b) (a + b)
(~a + b)
(a + b)
a
b
~a
a
b
b (~a + b) (a + b)
0 0
0
1 0
0
0 1
1
1 1
1
Why natural algorithms?
“Physics is like sex. Sure,
it may give some practical
results, but that's not
why we do it.”
Which is easier: flipping a coin or its numerical simulation?
Which is faster: protein folding or its numerical simulation?
Given a linear sequence of amino acids, into what three
dimensional configuration will the sequence fold?
A new vocabulary
Boolean logic,
automata theory, etc.
Natural physical processes
My Natural-Computer versus your PC !
“It’s not that the bear dances so well, it’s that he dances at all.”