Transcript Slide 1
NATURAL ALGORITHMS
Joshua J. Arulanandham, PhD student.
Prof. Cristian S. Calude and Dr. Michael J. Dinneen, Supervisors.
Department of Computer Science, The University of Auckland, New Zealand.
A passionate affair
I started
it !
Nature and Numbers –
“Friends” for ever!
Describing nature with mathematics
The universe is written in the
language of mathematics, and its
characters are triangles, circles,
and other geometric figures
Describing nature with computation
The universe is written in the
language of Cellular Automata,
and its characters are tiny cells
with discrete states.
How about
describing computation with nature ?
To those who study her, Nature reveals herself
as extraordinarily fertile in devising means …
Joseph Wood Krutch, nature writer
A merry-go-round can “sort”
I too can
sort!
Huh
!
Beads fall down in sorted order
“raw” vector v
The
SORT
“gate”
sorted vector v
Bead-Sort
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
Bead-Sort
Sorting {1, 3, 2, 4}
1. Drop 1 bead
(Remember, always from left-to-right)
2. Drop 3 beads
3. Drop 2 beads
4. Drop 4 beads
1
2
3
4
Bead-Sort: sequential implementation
• Two linear arrays used.
0
• Rod_Count keeps track of
number of beads in each rod.
0
Level_Count 1
• Level_Count records number of
beads in each level.
3
2
1
1
Rod_Count
• Level_Count would contain
sorted data, in the end.
Bead-Sort: digital representation
Flip-flops
0 0 0 0
1 1 1 1
1 1 1 0
1 0 0 0
1 1
0
0
Presence of bead = 1-state
Absence of bead = 0-state
Analog
representation
1 1 1 (no. 3)
1 0 0 (no. 1)
1 1 0 (no.2)
321
Calculating current flow
Resistor chain 1:
I1 = V1/R = 3/(1+2+3) = 1/2 A
Resistor chain 2:
I2 = V2/R = 2/(1+2+3) = 1/3 A
Resistor chain 3:
I3 = V3/R = 1/(1+2+3) = 1/6 A
‘Trim’ Voltage level:
Trim( v ) =
1 if v >= 0.5
0 otherwise
1/2 A
1/3 A
1/6 A
sorted data
Trim
1
0.5 V
Trim
1
0.3 V
V2Trim 2
V1 2
Trim
1
0.2 V
V3Trim 2
Trim
1V
0.7 V
0.3 V
3
3
3
Trim1 V
1.5 V
1
2
3
Trim0.5 V
1
1
2
v1 1 V
1
1
DATA ENTRY
0
0
1
Trim
0
(strings of 1’s similar to balls)
Increase voltage by 1 unit every time a ‘1’ is sent
v2
2V
v3
3V
CA implementation
initial
configuration
{2,1,3}
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
0
0
1
1
0
1
1
0
1
1
1
1
0
0
0
1
1
1
0
1
0
0
0
1
0
0
final
configuration
{1,2,3}
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
2
3
4
5
6
7
8
Simple CA rules
1
A natural computational model
A self-regulating balance
infinite source
x, y
x+y
input pan (fixed weight)
X
Y
X+Y
output pan (adjustable weight)
Subtraction
X - Y = ? X = Y + ? (assume, x > y)
X
Y +?
Average, division & multiplication
a
a
input
x, y
a
a
2a
a = (x + y) / 2
a
a
x, y,
z, w
a
a
4a
a
a
a = (x + y + z + w) / 4
a
a
Solving simultaneous equations
X+Y=5
X–Y=3
Represents X + Y = 5
x
y
5
Represents X – Y = 3
3
y
x
Principles for designing natural algorithms
Principle of Preferred States
A natural system has a set of preferred states due to the presence of
inherent properties and laws, thus restraining the “degrees of freedom” of
the system.
Principle of Automatic Constraint Satisfaction
If the constraints in a problem are “hard-wired” into the natural system
(representing the problem), then, the preferred state is the desired solution
(state) .
Principle of Bilateral Symmetry
Some natural (physical) systems can facilitate both “forward” and
“backward” directions of information-flow, for the same “price”: it is possible
to compute what possible input(s) might lead to a particular output.
The “bias” in nature
Sliders
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
0
0
0
0
1
1
or
0
Automatic constraint satisfaction
- A simple demonstration
l1
l2
l3
(l1 + l2 + l3 ) / 3
Liquids finding the same level due to atmospheric pressure
Combinatorial explosion need not matter
Goal
Start
The problem space
Natural algorithm - shortest path
E (Destination)
Shortest
path
D
A
C
B
(Source)
THANK YOU!
Special thanks are due to
Dr. Alan Creak, Honorary Researcher, Dept. of Computer Science
Prof. Boris Pavlov, Professor, Dept. of Mathematics
Prof. Garry Tee, Research Fellow, Dept. of Mathematics
Mr. Jasvir Nagra, PhD Student, Dept. of Computer Science
Mr. Damien Duff, MSc Student, Dept. of Computer Science
Mr. Andrew Paxie, MSc Student, Dept. of Computer Science
Mr. Dong Qiang, former MSc Student, Dept. of Computer Science
Mr. Philip Chiang, PhD Student, Dept. of Computer Science
Mr. Chi-kou Shu, PhD Student, Dept. of Computer Science
Mr. Ming Li, MSc Student, Dept. of Computer Science
for their invaluable suggestions and comments.
Bead Sort
Sorting {2, 3, 1}
1. Drop 2 beads
(Remember, always from left-to-right)
2. Drop 3 beads
3. Drop 1 beads
1
2
3
Bead Sort
Sorting {1, 3, 2}
1. Drop 1 bead
(Remember, always from left-to-right)
2. Drop 3 beads
3. Drop 2 beads
1
2
3
Bead Sort
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
1 0 1 0 0 0 1
1 0 1 0 0 1 0
...
1 1 0 0 0 1 1
161, 700 degrees of freedom (100 cells with three 1’s)
11 00 11 01
0 00
1 01
0 10
1 0 0
1 1
1 1 1 0 0 0 0
OR
100C3
degrees of
freedom
entropy loss = HUGE !
“squeeze”
0 0 0 0 1 1 1
2 possible
states